数字补数怎么算？LeetCode 1009与476的位运算掩码与异或解法

刷题列表里躺着两道编号差着五百多的题——1009 和 476背后却是同一个考点数字的补数。第一次刷到 476 的时候我觉得很轻松无非是把二进制位翻个面等做到 1009才发现这道题把“有效位”的概念、0 的边界、以及不同语言取反行为的差异全搅在一起了。如果你正在准备算法面试或者刚接触位运算想找一道能一次吃透“掩码、异或翻转、最高位定位”的题目这两道题非常合适。下面我会从题目拆解开始把两种主流解法讲透并把实际调试中容易踩的坑一起列出来。1. 题目拆解LeetCode 1009 与 476 到底在问什么1.1 两道题的关系同一考点两种入口从编号上看476 和 1009 之间隔了好几百道题但把英文名摆在一起就很清楚了476 是 Number Complement1009 是 Complement of Base 10 Integer。翻译成中文都是一个意思——给定一个非负整数把它转成二进制后每一位 0 变 1、1 变 0再把结果转回十进制。两题的核心解法完全一致区别主要在题目描述和边界约束上476 的输入通常限定为非负整数但在实际用例和讨论区里经常出现 0所以 0 一定要单独处理。1009 的约束写得很明确输入范围是 0 到 10^9且明确包含 0。10^9 转成二进制大约是 30 位意味着我们最多只需要关心低 30 位的翻转这在 int 范围内非常安全。我见过不少人在 476 上提交通过后直接把代码复制到 1009结果在 num 0 这个用例上挂掉。这不是算法思路错了而是边界感知不够。所以做这类题要养成的第一个习惯就是先看输入范围再想边界测试用例。1.2 补数到底是怎么算的从一个简单例子出发拿 5 来举例子。5 的二进制是 101逐位取反得到 010十进制就是 2。这里有一个很容易被忽略的关键点为什么 5 在计算机里通常是 00000000 00000000 00000000 00000101如果把所有位都取反结果会是一个巨大的数而不是我们期待的 2因为题目定义的“数字的补数”只针对有效二进制位。什么叫有效位就是从最高位的 1 开始一直到最低位为止。5 的有效位是 101 这三位前面所有的 0 都属于“前导零”不需要翻转。这也是整道题最核心的约束必须找到数字的有效位长度然后用这个长度构造掩码。再举一个容易误解的例子1009 这道题的英文名里有 Base 10 Integer有人会误以为要做“十进制补数”比如 10 的补数是 5 这种十进制按位关系。实际上它只是说“输入是用十进制表示的非负整数”计算仍然是在二进制位上完成的。搞混这一点面试时很容易在描述思路上绕半天。1.3 动手前必须搞懂的位运算基础在位运算里有几个关系式是解决这类题的钥匙x ^ 1会让 x 的某一位翻转因为 1 和 0 异或得 10 和 1 异或得 11 和 1 异或得 00 和 0 异或得 0。简单说和 1 异或就是取反。x 0是清零x | 0是保留这两个式子用来理解掩码很直观。一个 n 位全为 1 的二进制数等于2^n - 1。比如三位全 1 是 111就是 7等于 2^3 - 1。如果把一个数的有效位长度记为 len那么它的所有有效位组成的掩码 mask 就是2^len - 1。补数可以直接用一次异或算出来num ^ mask。例如 5 的 len 是 3mask 是 75 ^ 7 2。这个公式可以推导出整道题的所有解法剩下的问题只有一个如何高效地求出 len 或者等价的全 1 掩码。2. 朴素思路逐位翻转的实现与边界2.1 逐位翻转的核心想法与首个版本我第一次做 476 时脑子里冒出的第一个思路是既然要对有效二进制位逐位取反那就一位一位地来。具体做法是准备一个 bit 变量从 1 开始每次把 num 的当前最低位和 bit 做异或翻转这一位然后 bit 左移一格num 右移一格直到 num 变成 0。这个思路的朴素的 C 实现如下class Solution { public: int findComplement(int num) { if (num 0) return 1; int temp num; int bit 1; while (temp) { num ^ bit; bit 1; temp 1; } return num; } };这里有个容易写错的细节循环里我是用 temp 右移而不是直接用 num 右移。因为 num 要保存最终结果如果一边翻转一边右移 num原本的高位会被移丢。用 temp 作为“探针”去探测还有多少有效位需要处理num 本身只管累积结果这样两者的职责互不干扰。对于 5 来说运行过程是最低位 1 和 bit1 异或变成 0bit 变成 2下一位 0 和 2 异或变成 1再下一位 1 和 4 异或变成 0。最终 num 从 101 变成 010也就是 2。整个过程循环了 3 次正好是有效位数。2.2 为什么不能直接对原数取反不少刚接触位运算的人第一反应是用取反操作符~。以 C 为例~5的结果并不是 2而是 -6。原因在于 int 是固定 32 位~5会把 5 对应的 32 位二进制整体取反得到一堆前导 1换算成十进制就是一个负数。这里要区分两个概念按位取反是对变量所有二进制位取反而本题的补数只对有效位取反。有效位之外的部分必须保持原来的前导 0不能参与翻转。所以所有能找到的解法本质上都在做同一件事确定有效位的边界然后把边界之外的多余结果截掉。Python 里更明显~5的结果是 -6因为 Python 的整数是无限精度的。看到这个现象不要慌只要记住不能用语言自带的取反操作符直接完成这道题。实现时一定要先把有效位长度算出来再构造对应的全 1 掩码。2.3 用掩码累积代替逐位异或的改进写法逐位翻转能通过测试但代码看起来还不够优雅。稍微观察一下就会发现我们其实不需要翻转每一位只需要构造出和有效位长度一致的全 1 掩码最后做一次异或即可。C 里的改进版本可以这样写class Solution { public: int findComplement(int num) { if (num 0) return 1; int temp num; int mask 1; while (temp) { mask 1; temp 1; } return num ^ (mask - 1); } };这里有一段非常关键的逻辑mask 从 1 开始每检查完一位就左移一次。当 temp 变成 0 时mask 恰好等于2^len。例如 num 5 时循环结束后 mask 8mask - 1 77 就是三位全 1 的掩码。最后num ^ (mask - 1)一步完成翻转。为什么 mask 要初始化为 1因为只要 num 不是 0它的有效位长度至少是 1mask 至少需要覆盖第一位。这样初始化之后循环里左移的次数恰好等于有效位长度。如果 num 是 0循环直接不执行mask 保持 1此时0 ^ (1 - 1) 0不符合题意所以必须提前特判。这也是所有省事写法里最容易漏掉的点。3. 一次性解决的掩码法如何构造全 1 掩码3.1 找到最高位的 1就能拿到全 1 掩码逐位翻转的改进版已经引入了掩码思想但耗时仍是 O(log n)因为要从最低位一路右移到最高位。换个角度想只要找到最高位的 1 在哪一位就可以直接算出全 1 掩码。比如 5 的二进制是 101最高位的 1 在第 2 位从 0 开始计数那么掩码就是(1 3) - 1也就是 111。再比如 10 的二进制是 1010最高位的 1 在第 3 位掩码就是(1 4) - 1也就是 1111。一旦掩码确定补数就是num ^ mask。这个公式背后的原理并不复杂一个数从最高位 1 到最低位所有位置上的位要么是 1 要么是 0和全 1 掩码异或后原来 1 的地方变 0原来 0 的地方变 1正好满足补数定义。前导零部分没有掩码覆盖不会被翻转。3.2 三种构造掩码的写法对比实际写代码时构造掩码的方法可以有三种我根据自己的习惯推荐排序如下。第一种是循环左移法前面已经写过好处是思路直观坏处是时间复杂度受位长影响不过对数级别在本题范围内完全够用。第二种是位传播法利用右移和或运算把最高位的 1 向右连续传播最终让从最高位到最低位的所有位都变成 1。C 写法class Solution { public: int findComplement(int num) { if (num 0) return 1; int x num; x | x 1; x | x 2; x | x 4; x | x 8; x | x 16; return num ^ x; } };核心思路是x 的最高位为 1 的地方右移 1 位后会把第 2 位也变成 1或运算合起来后最高两位都是 1再右移 2 位能覆盖到第 4 位右移 4 位、8 位、16 位之后32 位 int 中从最高位到最低位就全部变成 1。数字 5 经过这串操作会变成 7数字 10 会变成 15效果和构造全 1 掩码完全一致。第三种是调用语言提供的位长函数。Python 里写法最简洁def findComplement(self, num: int) - int: if num 0: return 1 mask (1 num.bit_length()) - 1 return num ^ maskC20 里也可以用std::bit_width(num)不过兼容性要额外注意。三种写法各有优劣对比起来更清楚写法时间复杂度空间复杂度核心风险备注循环左移法O(log n)O(1)0 时需特判最容易理解位传播法O(1)O(1)0 时需特判32 位需固定右移 16 位常数最优位长函数法O(1)O(1)依赖语言特性0 时需特判代码最简洁3.3 复杂度分析与性能实测的思考从大 O 的角度看所有方法的时间复杂度都不高循环左移法和逐位翻转法都是 O(log n)位传播法和位长函数法都是 O(1)。空间上全部是 O(1)不需要额外数组。实际刷题时单次调用的时间差距微乎其微主要差异体现在代码的可读性和写错概率。但我私下跑过一万次循环对比位传播法确实比循环左移法快一些主要是减少了分支和移位次数。如果面试时想要体现对性能的理解位传播法是个不错的亮点因为它有一个很巧妙的思维路径从“定位最高位”到“让所有低位跟着变 1”这是一个可以迁移到其他位运算题的模型。需要注意位传播法的右移步长序列 1、2、4、8、16 是固定设计好的。32 位二进制需要从第 31 位传播到第 0 位而 1 2 4 8 16 31恰好覆盖全部距离。如果把右移步长写成 1、2、3、4、5低位就无法完全变 1结果会出错。3.4 从 476 到 1009输入范围变化的影响1009 的输入最大是 10^9小于 2^30所以位传播法在 32 位 int 上完全没有越界风险。476 的输入虽然有些版本不明确写上限但通常也在 int 范围内同样的代码可以直接用。唯一的区别还是 0。1009 明确把 0 列为合法输入期待输出是 1。根据 1.2 小节的定义0 的二进制是 0它的有效位长度是 1翻转这一位得到 1。所以在任何实现里函数开头的if (num 0) return 1;都应该作为固定动作写上。不要觉得这是多余的防御代码实测中很多人的提交就是挂在这一点上。另外如果将来遇到扩展版本比如输入范围扩大到 64 位整数位传播法就要额外补一次x | x 32。这也是一个值得在面试中主动提一句的边界考虑能体现你的考虑比标准答案更周全。4. 常见问题与排查技巧实录4.1 数字 0 为什么成了最大的坑0 的补数按题目定义是 1但很多实现天然会返回 0。原因在于0 没有最高位的 1循环类写法根本不会进入循环掩码类写法会把掩码算成 0。看起来都是“因为 0 的特殊性导致无法定位有效位”本质上是题目没有给 0 提供计算起点。我自己的排查方法是写完代码后先跑一遍边界用例集合 0、1、2、3、4、5、8、15、16。0 是最高优先级因为它在所有位运算题里都是最容易出问题的输入。看到返回值是 1 后再跑 2 的幂和 2 的幂减一这类特殊形状比如 8 的二进制是 1000补数应该是 715 的二进制是 1111补数应该是 0。这些用例能同时验证最高位定位和掩码构造是否正确。4.2 负数参与计算会怎样题目的约束是 0 到某个非负上限但面试中偶尔有人会问负数怎么办。这个问题本身就有一定陷阱负数的二进制表示为补码形式前面有无数个 1无法定义“有限长度的有效位”。举一个具体的例子在 C 里-5 作为 int 是 32 位二进制补码表示最高位是符号位 1如果用位传播法去构造掩码计算出来的掩码会覆盖整个 32 位最后得到的“补数”就不再是一个有限范围内的有意义结果。所以遇到负数正确做法不是想办法计算而是先确认输入范围明确这道题不考虑负数。面试时能主动指出这一点通常比强行写一段处理负数的代码加分更多。4.3 不同编程语言下的行为差异同一道题在不同语言里的坑位不一样我用一张表总结一下语言取反操作符行为建议实现方式C~x对 32 位 int 整体取反前导 0 变 1构造掩码后num ^ mask用 unsigned 避免右移扩展Java同样对 32 位 int 整体取反结果可能是负数位传播法注意 int 只有 32 位Python~x等于-(x1)无限精度取反用bit_length()构造掩码最方便Go^x是按位取反不是异或构造掩码后做异或^两边都要注意语义在 C 里右移负数属于实现定义行为虽然题目输入非负并不会碰到但如果面试官追问可以顺带提一句用unsigned int temp num;可以彻底规避符号扩展问题。Java 的逻辑右移是和算术右移要区分好在输入非负时两者结果一样。Python 的bit_length()是个好工具它能直接返回有效位长度让代码最短。4.4 调试位运算的三个实用习惯第一个习惯是打印二进制。C 里用bitset8(num)Python 里用bin(num)Java 里用Integer.toBinaryString(num)。很多位运算错误不用看十进制结果看二进制一眼就能定位是掩码错了还是翻转错了。第二个习惯是使用恒等式验证结果。对于任意非负整数 num它的补数 complement 满足num complement 1 2^len。比如 5 的补数是 25 2 1 8正好是 2 的 3 次方10 的补数是 510 5 1 16正好是 2 的 4 次方。如果算出来的补数不满足这个式子基本可以确定是掩码长度算错了。第三个习惯是固定边界测试顺序。我每次写完位运算题都会按这样测0、1、数字本身、2 的幂、2 的幂减一、随机大数。2 的幂和 2 的幂减一这两个形状特别能暴露边界错误因为它们的二进制要么只有一个 1要么全是 1一旦掩码多一位或少一位结果会偏差得非常明显。5. 从题目到工程补数还能用在哪5.1 状态位的整体反转一个小场景刷题时觉得位运算只是用来对付面试题其实它在实际工程里很常见。拿一个嵌入式场景举例假设一个寄存器用 8 位表示 8 个开关状态现在要求把所有开关全部取反。如果有明确位宽直接对寄存器做按位取反即可但如果只想反转某些有效位就需要像这道题一样先构造对应的掩码再异或。更常见的形态是只反转低 n 位其他位保持不变。这个操作等价于num ^ ((1 n) - 1)。这和本题的num ^ mask是同构的区别只是 mask 的宽度从“有效二进制位长度”变成了“你想要操作的位宽”。理解了掩码的含义从题目迁移到场景只是换一个 mask 的构造方式。另一个直观的例子是图像处理中的反色操作。8 位灰度图里像素值 0 变 255、255 变 0就是pixel ^ 255。如果只对某个颜色通道做反色同样是对应通道位宽的全 1 掩码做异或。这个思路和“补数”一脉相承只不过工程上往往用固定位宽不需要像题目那样动态定位最高位。5.2 位运算训练的价值迁移做完这道题值得把收获沉淀成可迁移的位运算套路。我自己的总结是很多位运算题都可以拆成“定位、构造掩码、异或或与或操作”这三步。比如统计二进制中 1 的个数核心是定位最低位的 1用n (n - 1)消除它比如判断一个数是不是 2 的幂核心是确认最高位的 1 是不是唯一一个 1再比如反转二进制位核心是对称地交换高低位。数字的补数这道题正好覆盖了其中两个关键能力定位最高位的 1以及根据位长构造全 1 掩码。以后再遇到需要“把某些位置翻转”的题目你会立刻想到用一个全 1 掩码去异或而不是傻乎乎地逐位判断。这种迁移能力比单独记住一道题的解法重要得多。顺便提一个比较隐蔽的坑面试时如果把这道题的两种方法都讲出来很容易被追问“位传播法的右移步长为什么是 1、2、4、8、16”。提前想清楚是因为 32 位 int 需要 31 次传播覆盖比临场推导要稳妥得多。能讲清楚这个细节面试官通常会觉得你是真的理解位运算而不是背了个模板。5.3 一点个人刷题体会这道题刷下来我最大的体会是位运算题目往往不是难在代码而是难在你对“有效位”的感知。拿 0 来说它看不到任何最高位的 1但题目仍然要求输出 1因为有效位长度是 1拿 5 来说如果忘了前导零不参与翻转按位取反会得到一个完全无关的负数。位宽、边界、语言特性这三样东西几乎决定了这类题能不能一次写对。最后分享一个我自己的小技巧写完这类题不要急着提交先在草稿纸上写一个二进制对照表比如 5 的二进制 101、掩码 111、结果 010然后对照代码里的每一步走一遍。很多位运算错误在代码层面很难看出来但在二进制层面一目了然。养成这个习惯之后不光是补数题后面遇到的任何位运算变体都会觉得顺畅很多。