0476. Number Complement¶
题目信息¶
- 题号:
0476
- 难度:
Easy
- 主题:
正整数、有效二进制位、逐位取反、前导零忽略
- 原题:
- 重点:
只翻转从最高有效位到最低位的二进制位、无限前导零不参与、返回取反后的整数
题目重述¶
给定正整数 num,把它的二进制表示中所有有效位逐位取反:0 变为 1,1 变为 0。返回取反后表示的整数。
有效位从原数最高的 1 开始,到最低位结束;更高位置隐含的前导零不参与翻转。num 位于 [1, 2^31-1],因此输入不存在符号位和数字 0 的特殊情况。
自建示例¶
高低位同时翻转:
输入:num = 10
输出:5
解释:10 的有效二进制表示为 1010,逐位取反得到 0101,即十进制 5;最左侧新增的 0 不影响数值。
只有一个有效位:
输入:num = 1
输出:0
解释:二进制 1 取反后为 0。
先构造有效位掩码再取反¶
输入的最高有效位决定了需要翻转的位数。逐次右移 num,同时把掩码左移并补入 1,最终得到与 num 有效二进制位等长、每一位都是 1 的掩码;用 ~num 与该掩码相与,就会只保留有效位的取反结果。
这样不会把无限补在高位的零误认为需要翻转的位,也不需要将二进制表示转换成字符串。
C++ 实现¶
class Solution {
public:
int findComplement(int num) {
int mask = 0;
for (int value = num; value > 0; value >>= 1) {
mask = (mask << 1) | 1;
}
return (~num) & mask;
}
};
代码分析¶
掩码的每个 1 对应输入的一个有效位,按位与去除了更高位的补码结果;正整数输入保证循环至少执行一次。循环处理有效位数,时间复杂度为 O(log num),额外空间复杂度为 O(1)。