力扣 1009 题解析与 C++ 代码
一、问题解析
题目描述：每个非负整数 N 都有其二进制表示。例如， 5 的二进制表示为 "101"，其补码为 "010"，即十进制中的 2。对于给定的十进制整数 N，返回其二进制表示取反（即补码）所对应的十进制整数。注意，二进制表示中不包含前导零，因此补码的二进制表示也不包含前导零。
核心要点：
算法思路：
时间复杂度：O(1)，因为整数位数固定（例如32位）。 空间复杂度：O(1)。
二、C++ 代码实现
方法一：位运算（异或掩码法）
这是最直接和高效的方法。
class Solution {
public:
int bitwiseComplement(int n) {
// 处理边界情况：n为0时，其有效位长度为1，掩码为1，补码为1
if (n == 0) return 1;
// 步骤1：计算有效位长度 L
int length = 0;
int temp = n;
while (temp > 0) {
temp >>= 1; // 右移一位 length++;
}
// 或者使用内置函数： int length = floor(log2(n)) + 1;
// 步骤2：构造全1掩码 mask = (1 << L)1
int mask = (1 << length) – 1;
// 步骤3：计算补码 n ^ mask return n ^ mask;
}
};
方法二：位运算（循环取反法）
通过循环直接逐位翻转，逻辑更直观。
class Solution {
public:
int bitwiseComplement(int n) {
if (n == 0) return 1;
int result = 0;
int bitPosition = 0; // 当前处理的位位置
while (n > 0) {
// 取n的最低位，并翻转 (0->1, 1->0)
int currentBit = (n & 1) ^ 1;
// 将翻转后的位放到结果的正确位置
result |= (currentBit << bitPosition);
// n右移一位，准备处理下一位
n >>= 1;
bitPosition++;
}
return result;
}
};
方法三：利用 bitset（辅助理解）
使用标准库 bitset 可以更清晰地展示二进制操作过程，但效率略低。
#include <bitset>
class Solution {
public:
int bitwiseComplement(int n) {
if (n == 0) return 1;
// 确定需要的位数，32位足够 const int MAX_BITS = 32;
std::bitset<MAX_BITS> bs(n);
// 找到最高位1的位置
int highestBit = MAX_BITS1;
while (highestBit >= 0 && !bs.test(highestBit)) {
highestBit–;
}
// 翻转从最高位到第0位的所有位 for (int i = 0; i <= highestBit; i++) {
bs.flip(i);
}
// 转换回整数 return static_cast<int>(bs.to_ulong());
}
};
三、算法对比
| 时间复杂度 | O(log N) | O(log N) | O(log N) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 核心思想 | 构造全1掩码后异或 | 逐位翻转并重组 | 使用标准库位集操作 |
| 代码简洁性 | 简洁 | 较简洁 | 直观但稍冗长 |
| 推荐度 | 推荐 | 推荐 | 适用于教学演示 |
四、关键点与示例
测试示例：
int main() {
Solution sol;
cout << sol.bitwiseComplement(5) << endl; // 输出: 2 (101 -> 010)
cout << sol.bitwiseComplement(7) << endl; // 输出: 0 (111 -> 000)
cout << sol.bitwiseComplement(10) << endl; // 输出: 5 (1010 -> 0101)
cout << sol.bitwiseComplement(0) << endl; // 输出: 1 (特殊处理)
return 0;
}
参考来源
- 1009. Complement of Base 10 Integer*
- 阶乘求和全解析：从 Python 秒过到 C++ 手写高精度
- 力扣 476. 数字的补数 C++
- Leetcode 476. 数字的补数 C++
- leetcode-1009. 十进制整数的反码刷题笔记（c++）
