整数的补数：位运算掩码解法

题目

对整数的二进制表示取反（0 变 1，1 变 0），再转换为十进制，得到该整数的补数。
例如：5 的二进制是 101，取反后 010 = 2，所以 5 的补数是 2。
注意：不含前导零。给定 1 <= num < 2^31，输出其补数。

思路

直觉是逐位翻转，但更优雅的方法是构造一个掩码 mask：

找到 num 的最高有效位，构造一个同等位数全为 1 的掩码。
num XOR mask 即为补数（因为 x XOR 1 = ~x，x XOR 0 = x）。

例如 num = 5（二进制 101）：

mask = 111（十进制 7）
5 XOR 7 = 101 XOR 111 = 010 = 2 ✓

如何构造 mask？

mask 从 1 开始，不断左移并 OR，直到 mask >= num：
mask = 1
while mask < num:
    mask = (mask << 1) | 1

// 或等价地：
mask = (1 << bit_length(num)) - 1

为什么不能直接用 `~num`

C++ 里 ~ 是按位取反，会翻转整数的全部 32 位（或 64 位），包括前导零。

int num = 5;        // 0000 0000 0000 0000 0000 0000 0000 0101
int result = ~num;  // 1111 1111 1111 1111 1111 1111 1111 1010
// result = -6（有符号整数，补码表示）

题目要求的是只翻转有效位（去掉前导零的那几位），所以 ~5 得到 -6，不是 2。

这就是掩码方案存在的意义：先把无效的高位都遮掉，只对有效位做 XOR。

// num = 5: 有效位是 3 位（101）
// mask = 111 = 7
// num ^ mask = 101 ^ 111 = 010 = 2  ✅
// ~num       = ...11111010 = -6     ❌

实现

C++

class Solution {
public:
    int findComplement(int num) {
        // 构造掩码：找到 num 的最高位，mask 全为 1
        unsigned int mask = 1;
        while (mask < (unsigned int)num) {
            mask = (mask << 1) | 1;
        }
        return num ^ mask;
    }
};

更优雅的写法：用 __builtin_clz（GCC/Clang 内置，Count Leading Zeros）：

class Solution {
public:
    int findComplement(int num) {
        // __builtin_clz(num) 返回 32 位整数中前导零的个数
        // 32 - clz = 有效位数
        // (1 << 有效位数) - 1 就是全 1 掩码
        int mask = (1 << (32 - __builtin_clz(num))) - 1;
        return num ^ mask;
    }
};

例：num = 5（二进制 101）

__builtin_clz(5) = 29（64 位环境是 61，这里按 32 位讨论）
32 - 29 = 3（有效位数）
(1 << 3) - 1 = 7（0111，全 1 掩码）
5 ^ 7 = 2 ✅

注意：__builtin_clz(0) 是未定义行为，题目保证 num >= 1，所以安全。

Python

class Solution:
    def findComplement(self, num: int) -> int:
        # bit_length() 返回二进制表示的位数（不含前导零）
        # 例：(5).bit_length() = 3
        mask = (1 << num.bit_length()) - 1
        return num ^ mask

Python 整数是任意精度，没有 32 位截断问题，bit_length() 天然只算有效位，非常干净。

Java

class Solution {
    public int findComplement(int num) {
        // Integer.highestOneBit 找最高位，构造掩码
        int mask = Integer.highestOneBit(num);
        mask = (mask << 1) - 1; // 例如 highestOneBit(5)=4，(4<<1)-1=7
        return num ^ mask;
    }
}

复杂度

时间：O(log n)，循环次数等于 num 的二进制位数。__builtin_clz / bit_length() 方案是 O(1)。
空间：O(1)。

补数 vs 补码

这两个概念容易混淆：

	定义	例子（8 位）
补数（本题）	二进制取反，不含前导零	5 (`101`) → 2 (`010`)
反码	所有位取反（含符号位）	5 (`00000101`) → `11111010`
补码	反码 + 1，用于表示负数	-5 的补码 = `11111011`

本题的”补数”只对有效位取反，和计算机组成原理里的补码是不同概念。

举一反三：同类位运算题

掌握了掩码 + XOR 的思路，以下题型都是变体：

题目	核心技巧
LeetCode 461 - 汉明距离	`x ^ y` 后数 1 的个数
LeetCode 191 - 位 1 的个数	`x & (x-1)` 循环消最低位
LeetCode 136 - 只出现一次的数字	`x ^ x = 0`，全部 XOR 消掉成对的数
LeetCode 260 - 只出现一次的数字 III	差异位分组，各组 XOR
LeetCode 693 - 交替位二进制数	`n & (n >> 1)` 判断相邻位是否相同
LeetCode 1009 - 十进制整数的反码	本题完全相同，只是描述不同

位运算常用技巧速查

这些技巧在算法题中反复出现，背下来：

操作	表达式	说明
消去最低位的 1	`x & (x - 1)`	用于统计 1 的个数（Brian Kernighan 算法）
取最低位的 1	`x & (-x)`	等价于 `x & (~x + 1)`，lowbit，树状数组核心
判断 2 的幂	`x > 0 && (x & (x-1)) == 0`	2 的幂只有一个 1
交换两数（无临时变量）	`a ^= b; b ^= a; a ^= b`	有趣但不推荐用于生产
相同则为 0	`x ^ x = 0`	XOR 消除相同元素的基础
任何数与 0 XOR	`x ^ 0 = x`	XOR 的恒等元
取第 k 位	`(x >> k) & 1`	判断第 k 位是 0 还是 1
置第 k 位为 1	`x \| (1 << k)`	位掩码 OR
清第 k 位为 0	`x & ~(1 << k)`	位掩码 AND NOT
翻转第 k 位	`x ^ (1 << k)`	位掩码 XOR
算有效位数	`32 - __builtin_clz(x)`（C++）	本题核心

延伸

同类题：LeetCode 1009 - 十进制整数的反码，本质相同，只是题目描述方式不同。

位运算的本质是把整数的二进制表示当作一个布尔数组来批量操作。掌握掩码构造、XOR 的特性（自反、消除）、以及 x & (x-1) 这三个基本操作，80% 的位运算题都能迎刃而解。

题目

思路

为什么不能直接用 ~num

实现

C++