476. 数字的补数

🟢   🔖  位运算  🔗 力扣 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 num, return its complement.

Example 1:

Input: num = 5

Output: 2

Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: num = 1

Output: 0

Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints:

• 1 <= num < 231

Note: This question is the same as 1009. Complement of Base 10 Integer

题目大意

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

示例 1：

输入： num = 5

输出： 2

解释： 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：

输入： num = 1

输出： 0

解释： 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

提示：

• 1 <= num < 231

注意： 本题与 1009. 十进制整数的反码 相同

解题思路

1. 理解补数操作：

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

2. 掩码 (Mask) 的作用：

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

3. 异或操作实现取反：

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

4. 如何构建掩码：

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

5. 特殊情况：

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

复杂度分析

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

代码

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

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

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

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