| title | 1009. 十进制整数的反码 | ||||||
|---|---|---|---|---|---|---|---|
| description | LeetCode 1009. 十进制整数的反码题解，Complement of Base 10 Integer，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。 | ||||||
| keywords |
|
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;
};