1009. 十进制整数的反码
1009. 十进制整数的反码
题目
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
5is"101"in binary and its complement is"010"which is the integer2.
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 。
提示：
0 <= N < 10^9- 本题与 476. 数字的补数 相同
解题思路
理解补数操作：
- 补数的概念是在二进制表示中，将所有的
0替换为1，所有的1替换为0。 - 例如：
n = 5，它的二进制表示为101，其补数为010，对应十进制2。
- 补数的概念是在二进制表示中，将所有的
掩码 (Mask) 的作用：
- 为了将
n中的所有位取反，我们需要使用一个掩码（mask），它的长度与n的二进制表示的位数相同，并且所有位都为1。 - 如果二进制长度为
n，对应的掩码就是111...111（长度为n）。 - 例如：
101的掩码是111。
- 为了将
异或操作实现取反：
- 将
n和掩码进行异或操作，就能将n的所有1变成0，所有0变成1，得到其补码。 - 异或规则：
1 ^ 1 = 0,0 ^ 1 = 1。 - 例如：
101 ^ 111 = 010。
- 将
如何构建掩码：
- 先计算
n的二进制位数：bitLength = n.toString(2).length。 - 然后用位运算
1 << bitLength得到一个只有第bitLength+1位为1的数：- 示例：
1 << 3=1000。
- 示例：
- 再减去
1，得到所有位为1的掩码：- 示例：
(1 << 3) - 1=1000 - 1=111。
- 示例：
- 先计算
特殊情况：
- 如果
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;
};