数字的补数如何用位掩码求解？为什么不能直接对整数取反？

简化版

数字补数只翻转有效二进制位，不翻转前导零。先构造一个和 num 有效位数相同、低位全为 1 的掩码 mask，答案就是 mask ^ num，或者 mask - num。

详细版

不能直接用 ~num，因为计算机整数通常是固定 32 位或 64 位，取反会把所有高位前导零也变成 1，得到负数或不符合题意的结果。题目只要求翻转从最高有效位到最低位之间的位。

例如 num=5(101)，有效位掩码是 111，补数是 010=2。构造 mask 可以不断左移加 1，直到 mask >= num。时间复杂度 O(log num)。

完整版教学

一、题目里的“补数”翻转哪些位

数字 5 的二进制通常写作：

101

补数是把这 3 个有效位翻转：

101 -> 010

结果是 2。前面无限多个或固定宽度里的 0 不参与题目定义。

二、为什么不能直接写 ~num

在 Java 里，int 是 32 位。~5 实际翻转的是 32 位：

00000000 00000000 00000000 00000101
变成
11111111 11111111 11111111 11111010

这是一个负数，不是题目要的 010。

易错点：题目补数只翻有效位，语言里的 ~ 会翻固定宽度的所有位。

三、掩码 mask 是什么

我们需要构造低有效位全为 1 的 mask。对于 num=5(101)：

mask = 111

然后：

num  = 101
mask = 111
xor  = 010

mask 限定了取反范围，只翻题目关心的位。

变量	二进制	含义
num	101	原始有效位
mask	111	覆盖全部有效位
mask ^ num	010	只在有效位内翻转后的结果

四、如何构造 mask

一种简单方式：

mask = 1
while mask < num:
    mask = (mask << 1) | 1

例如 num=5：

mask=1
mask=3(11)
mask=7(111)

当 mask 覆盖到 num 的最高位时停止。

五、代码模板

int findComplement(int num) {
    int mask = 1;
    while (mask < num) {
        mask = (mask << 1) | 1;
    }
    return mask ^ num;
}

也可以返回 mask - num，因为在 mask 全 1 的范围内，异或翻转等价于用全 1 减去原数。

六、边界例子

num=1：

mask=1
1 ^ 1 = 0

num=10(1010)：

mask=1111
1010 ^ 1111 = 0101 = 5

如果题目允许 num=0，要单独看定义；有的题认为 0 的补数是 1，有的题输入保证正数。

七、常见误区与追问

• 误区：直接返回 ~num。 会翻转固定宽度高位，结果不符合有效位补数。
• 误区：mask 少一位。 mask 必须覆盖 num 的最高有效位。
• 误区：忽略 num=1。 1 的有效位翻转后是 0。
• 追问：为什么 mask ^ num 可行？ mask 为 1 的位会翻转，mask 为 0 的位保持不变。
• 追问：mask - num 为什么也行？ 全 1 范围内减法效果等价于逐位取反。
• 追问：复杂度是多少？ mask 位数随 num 二进制长度增长，是 O(log num)。

八、加强记忆

数字补数的核心是“只翻有效位”。直接 ~ 会把高位也翻掉，所以先做一个低位全 1 的 mask，再 mask ^ num。看到补数题，脑子里先画 num=101, mask=111, ans=010，这个图比公式更抗忘。