476. 数字的补数
题目描述
输入正整数 num。
取 num 不带前导零的二进制写法，把其中每一位翻转（0 变 1，1 变 0），再把结果当作二进制数读回十进制，就得到 num 的补数。
返回 num 的补数。
示例 1
输入：num = 5 输出：2
解释：5 的二进制是 101，翻转得 010，即 2。
示例 2
输入：num = 1 输出：0
解释：1 的二进制是 1，翻转得 0。
数据范围
1 <= num < 2^31
解题思路
只需要翻转 num 的有效位，所以先找一个刚好覆盖这些位的全 1 掩码：mask 从 1 开始不断左移，直到 mask > num，此时 mask 是比 num 最高位再高一位的 2 的幂，mask - 1 就是与 num 等长的全 1。与全 1 异或就是逐位取反。
为什么正确
循环中 mask 始终是 2 的幂；循环结束时 mask / 2 <= num < mask，所以 mask - 1 恰好覆盖 num 的全部有效位。
复杂度分析
时间 O(log num)，空间 O(1)。
易错点
直接用 ~num 会把前导零也翻成 1，得到负数；另外 num 接近 2^31 时 mask 会到 2^31，C++/Java 要用 64 位整数防止溢出。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findComplement(self, num: int) -> int:
mask = 1
while mask <= num:
mask <<= 1
return (mask - 1) ^ numclass Solution {
public int findComplement(int num) {
long mask = 1;
while (mask <= num) {
mask <<= 1;
}
return (int) ((mask - 1) ^ num);
}
}class Solution {
public:
int findComplement(int num) {
long long mask = 1;
while (mask <= num) {
mask <<= 1;
}
return (int)((mask - 1) ^ num);
}
};func findComplement(num int) int {
mask := 1
for mask <= num {
mask <<= 1
}
return (mask - 1) ^ num
}var findComplement = function(num) {
let mask = 1;
while (mask <= num) {
mask *= 2;
}
return (mask - 1) - num;
};function findComplement(num: number): number {
let mask = 1;
while (mask <= num) {
mask *= 2;
}
return (mask - 1) - num;
}