1009. 十进制整数的反码

🟢   🔖  位运算  🔗 力扣 LeetCode

题目

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer n, return its complement.

Example 1:

Input: n = 5

Output: 2

Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7

Output: 0

Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10

Output: 5

Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints:

• 0 <= n < 10^9

Note: This question is the same as 476. Number Complement

题目大意

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

输入： 5

输出： 2

解释： 5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

输入： 7

输出： 0

解释： 7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

输入： 10

输出： 5

解释： 10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

提示：

1. 0 <= N < 10^9
2. 本题与 476. 数字的补数 相同

解题思路

1. 理解补数操作：

   • 补数的概念是在二进制表示中，将所有的 0 替换为 1，所有的 1 替换为 0。
   • 例如：n = 5，它的二进制表示为 101，其补数为 010，对应十进制 2。

2. 掩码 (Mask) 的作用：

   • 为了将 n 中的所有位取反，我们需要使用一个掩码（mask），它的长度与 n 的二进制表示的位数相同，并且所有位都为 1。
   • 如果二进制长度为 n，对应的掩码就是 111...111（长度为 n）。
   • 例如：101 的掩码是 111。

3. 异或操作实现取反：

   • 将 n 和掩码进行异或操作，就能将 n 的所有 1 变成 0，所有 0 变成 1，得到其补码。
   • 异或规则：1 ^ 1 = 0, 0 ^ 1 = 1。
   • 例如：101 ^ 111 = 010。

4. 如何构建掩码：

   • 先计算 n 的二进制位数：bitLength = n.toString(2).length。
   • 然后用位运算 1 << bitLength 得到一个只有第 bitLength+1 位为 1 的数：
     • 示例：1 << 3 = 1000。
   • 再减去 1，得到所有位为 1 的掩码：
     • 示例：(1 << 3) - 1 = 1000 - 1 = 111。

5. 特殊情况：

   • 如果 n == 0，补数应为 1，需要单独处理。

复杂度分析

• 时间复杂度：O(1)，计算二进制位数和掩码都是常数时间操作。
• 空间复杂度：O(1)，仅使用了常数级别的额外变量。

代码

/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function (n) {
	if (n == 0) return 1; // 处理特殊情况：输入为 0

	// 计算二进制的位数
	const bitLength = n.toString(2).length;

	// 构建掩码：所有位都是 1
	const mask = (1 << bitLength) - 1;

	// 通过异或操作计算补数
	return n ^ mask;
};