先看这道题的第一眼你可能会觉得奇怪476 和 1009 不是两道题吗怎么放在一起做实际刷下来你会发现这两道题的内核几乎一模一样都是让你对一个整数的二进制有效位做取反也就是按位求补。但麻烦也恰恰出在这题目长得像双胞胎边界条件却悄悄不一样尤其是 0 的处理。如果你直接复制第一题的代码去交第二题大概率会在那个不起眼的角落翻车。这篇文章就把这两道题放在一起拆透。我会从最基础的定义讲起把为什么不能直接~num、怎么构造全 1 掩码、0 的边界差异、以及延伸到其他位运算题的通用技巧全部理顺。适合刚开始刷位运算、或者被这类“简单题”卡过的人参考。1. 两道题的真正关系同一个内核两种出题套路1.1 题面到底在问什么有效位与补数的定义先说最核心的概念。476 号题“数字的补数”和 1009 号题“十进制整数的反码”说的都是同一件事给定一个非负整数写出它的二进制表示去掉前导 0然后把每一位的 0 变 1、1 变 0再转回十进制。举例最直观5 的二进制是101有效位就这 3 位取反得到010也就是 2。10 的二进制是1010有效位 4 位取反得到0101也就是 5。7 的二进制是111取反得到000也就是 0。这里反复强调“有效位”是因为一个 int 在计算机里通常占 32 位像 5 这种小数字前面其实还挂着一大串 0。我们要处理的只是从最高位 1 开始到最低位的那一段前面的 0 不算数。这就是“补数”和“直接按位取反”之间最本质的区别。1.2 直接取反的陷阱为什么~num不 work很多新手第一反应是取反嘛直接~num不就行了我在初学的时候也这么干过然后被结果教做人了。在 C 里对 5 执行~5得到的是 -6而不是期望的 2。原因在于~是按整个 int 的 32 位全部取反。5 用 32 位表示是00000000 00000000 00000000 00000101全部取反后变成11111111 11111111 11111111 11111010在补码体系下这一串 1 开头的二进制数是个负数算出来正好是 -6。也就是说~把符号位和前面那一大堆前导 0 也一起翻了自然不是题目想要的结果。操作二进制32位视角十进制结果num 50000...0001015~num1111...111010-6期望的补数0000...0000102所以这两道题表面上在考“取反”实际考的其实是“怎么把取反的范围限制在有效位内”。这个认知一旦建立后面所有解法都是围绕它展开的。1.3 两道题的貌合神离0 的答案不一样这才是这个组合标题里最值得玩味的地方。1009 号题在示例里明确给出了0 - 1理由是 0 的二进制有效位就是单个0取反后是1。而 476 号题按照同样的定义推演0 似乎也应该返回 1但我实际按 0 返回 0 去交 476 是可以过的评论区里也普遍认可这种处理。为什么会出现这种差异本质上是因为“有效位”这个概念在 0 身上存在歧义0 没有最高位的 1到底算有 0 位还是 1 位题目没有统一说法于是两个题各自选了不同的答案作为预期输出。这个细节非常隐蔽却直接决定了代码怎么写。如果你写一个“万能”函数想同时通过两题必须在 0 这个位置做显式特判476 传 01009 传 1。后面我会给出具体的兼容写法。2. 476 的三种常规解法从直观到优雅2.1 逐位扫描构造逻辑最朴素边界最安全最直白的方式就是老老实实从最低位开始一位一位检查原数再一位一位构造结果。这个方法不需要预先知道数字的位数也不需要担心前导 0循环天然在最高位处停下来。int findComplement(int num) { int ans 0; int pos 0; long long bit 1; // 用 long long 避免 num 接近上限时 bit 左移溢出 while (bit num) { if ((num bit) 0) { ans | (1 pos); // 原数该位是 0补数该位应该是 1 } bit 1; pos; } return ans; }我故意把bit声明成long long这是有讲究的。如果num接近 2^31 的上限bit会一路左移到 2^31而这个值在 32 位 int 里已经溢出成负数循环条件瞬间失效。很多人在这一步踩坑其实换成长整型就干净了。如果你测试 5过程是这样的bit15 1 1不动bit25 2 0于是ans | 2bit45 4 1不动bit8时循环结束最终ans2。逐个位看原数每一位是 0结果对应位就是 1原始又可靠。2.2 掩码异或一行代码背后的两个步骤第二种解法是主流写法思路更清爽。核心规律是一个二进制位与 1 异或相当于取反。0 ^ 1 11 ^ 1 0。所以只要构造一个和有效位等长的全 1 掩码再让num跟它异或结果就是补数。比如num 10有效位 4 位掩码就是11111010 ^ 1111 0101 5。问题变成了怎么构造这个全 1 掩码最直观的循环方式是int findComplement(int num) { if (num 0) return 0; // 476 实际预期 int mask 1; while (mask num) { mask (mask 1) | 1; } return mask ^ num; }mask从 1 开始每轮左移一位再补一个 11 - 11 - 111 - 1111直到不小于num为止。这个写法对 1009 更友好因为当n 0时循环一次都不进mask保持 10 ^ 1 1正好是 1009 要的答案。2.3 用“扩展法”构造掩码五条右移语句的魔法如果你觉得循环构造掩码还是不够快这里还有一个位运算老手常用的技巧。它利用右移不断把已有的 1 向低位复制最后让从最高位 1 往下的所有位都变成 1。int findComplement(int num) { int mask num; mask | mask 1; mask | mask 2; mask | mask 4; mask | mask 8; mask | mask 16; return mask ^ num; }看个例子。num 10二进制1010mask | mask 11010 | 0101 1111后面的右移 2、4、8、16 都不会改变结果因为掩码已经是全 1 了。这个写法的妙处在于只需要固定 5 次移位跟数字的位数无关。它背后的原理很简单右移 1 位可以把每个 1 都往右“拷贝”一次那么相隔 1 位的两个位置就有 1 了再右移 2 位相隔 2 位的也补齐之后右移 4、8、16相当于用指数级的步伐把 1 传播满整个 32 位整数。对 0 来说mask始终是 00 ^ 0 0所以这个写法天然符合 476 的预期但用在 1009 上就需要单独处理 0。2.4 复杂度对比选哪种看场景解法时间复杂度空间复杂度0 的天然结果主要风险逐位扫描O(位数)O(1)返回 0bit左移溢出需用 long long循环构造掩码O(位数)O(1)返回 1无逻辑最稳扩展法构造掩码O(1) 固定 5 次移位O(1)返回 0需要理解0 需特判三道解法的时间复杂度在这个数据范围里其实没有本质差别因为 int 最多也就 31 个有效位。我更推荐你先掌握循环构造掩码它最容易从原理推导出来。扩展法属于那种“面试时写出来会让人眼前一亮”的技巧但如果你解释不清楚原理建议还是别为了炫技而用。3. 1009 的坑题名误导、边界溢出与通用解法3.1 “十进制整数的反码”是个翻译陷阱1009 号题最坑的地方不在代码而在题名。中文翻译叫“十进制整数的反码”乍一看像是让你对十进制数的每一位做运算比如用 9 去减每一位10 就变成 89。但实际示例给出的答案是 5。这个误区的根源在于原题英文叫 “Complement of Base 10 Integer”。它的意思是“一个十进制整数的补数”而这个“补数”仍然是针对它的二进制表示来算的。也就是说输入是十进制运算在二进制输出又回到十进制。以后看到类似“Base 10 Integer”的表述一定要先确认它说的是“数字的进制”还是“运算的进制”。在 1009 里十进制只是表示输入输出格式真正的操作对象是二进制位。这也是为什么它和 476 能被放在一起本质上就是同一道题。3.2 边界不只有 0当 num 接近 2^31 时掩码会爆1009 的输入上限是 10^9这在 int 范围内很安全。但如果你把它和 476 合并成一个通用函数就得考虑输入接近 2^31-1 的情况。最典型的爆炸点是“最高位定位后再左移一位”。很多人会这么写int highest 1; while (highest num) highest 1; int mask highest - 1; return num ^ mask;当num是 2^30 时highest会左移到 2^31在 32 位 int 里这一下就溢出了highest变成负数mask也跟着错。同样的道理也出现在(1 31) - 1这种写法里。解决办法很简单把highest或者中间量声明成long long算完再转回 int。不要在高位计算上省这一点类型长度溢出问题定位起来比写代码痛苦得多。int findComplementWithLL(int num) { long long highest 1; while (highest num) highest 1; return (int)((highest - 1) ^ num); }3.3 一套兼容两题的最终模板既然两题核心相同、边界不同最稳妥的做法是写一个带“零值规则”参数的函数然后分别包装。这样既不用背两套解法又不会漏掉特判。int complement(int num, int zeroAnswer) { if (num 0) return zeroAnswer; int mask num; mask | mask 1; mask | mask 2; mask | mask 4; mask | mask 8; mask | mask 16; return mask ^ num; } // 476complement(num, 0) // 1009complement(num, 1)这个模板结合了扩展法的简洁和显式特判的安全感。关键点在于num 0必须在构造掩码之前拦截否则扩展法会返回 0永远无法得到 1009 需要的 1。如果用 Python整体会更短def bit_complement(num: int, zero_answer: int) - int: if num 0: return zero_answer mask num mask | mask 1 mask | mask 2 mask | mask 4 mask | mask 8 mask | mask 16 return mask ^ numPython 的 int 是任意精度天然不担心溢出这也是很多人在 Python 里几乎感觉不到 476 和 1009 差异的原因。4. 从这两题延伸出去位运算里高频的掩码与定位技巧4.1 找到最高位 1 的四种姿势这两道题反复在做一个动作找最高位的 1。这个操作在更多位运算题里都会用到值得一次性总结清楚。第一种循环移位找位数int bits 0; int t num; while (t) { bits; t 1; }第二种用内建函数。C 里 GCC 有__builtin_clzJava 有Integer.numberOfLeadingZerosPython 有bit_length()。这些函数直接给出前导 0 的数量用 32 减掉就是位数。int bits 32 - __builtin_clz(num); // num 不能为 0第三种就是我前面写的扩展法把最高位 1 向下传播成掩码然后通过mask - (mask 1)提取最高位。第四种用数学函数log2(num)加 1。但浮点运算在边界值上偶尔会有精度误差我不太推荐在刷题时依赖它。个人建议日常写题用第二种面试讲解原理用第一种想展示位运算功底用第三种。4.2 构造任意掩码的通用方法通过这两道题你应该已经掌握了两个构造掩码的通用套路。第一个是“左移补 1”int mask 1; while (mask target) mask (mask 1) | 1;这个套路适合构造“从低位到最高位连续全 1”的掩码而且它天然适配 1009 的 0 值返回 1。第二个是“右移传播 1”int mask num; mask | mask 1; mask | mask 2; mask | mask 4; mask | mask 8; mask | mask 16;这个套路适合把某个二进制数的最高位 1 以下所有低位填满不依赖数字大小。它的变体在很多位运算题里都能看到比如提取符号位、判断 2 的幂等。还有一个常用技巧是lowbit用来提取最低位的 1int lowbit num (-num);它利用了补码的特性一个数取负后除了最低位的 1 保持不动其余位都取反再加 1与运算之后高位全部清零只留下最低位的 1。这个技巧在树状数组里几乎是每日见面的程度。4.3 这些技巧会在哪些场景重逢位运算基础一旦打通后面做题会顺畅很多。这里列出几个常见的位运算应用场景判断一个数是不是 2 的幂(num (num - 1)) 0。2 的幂只有一个 1减 1 之后高位全变 0与运算结果必为 0。统计二进制中 1 的个数while (num) { count; num num - 1; }。每轮消掉一个最低位的 1循环次数等于 1 的个数而不是位数。数组里找唯一出现一次的数把所有元素做异或。相同的数字会互相抵消剩下的就是落单的那个。子集枚举for (mask 0; mask (1 n); mask)用二进制位表示每个元素选或不选。你会发现476 和 1009 里练的“构造掩码”、“异或取反”、“定位最高位”全部都在这些场景里反复出现。所以这个“位运算-基础”的标签不是随便标的它确实是很多中难题目的地基。5. 复盘做完这套题真正需要带走什么5.1 三个高频翻车点第一直接~num。这是最常见的误区。不是说~没用而是它按整个 int 取反把符号位和前导 0 都算进去了。所有“有效位取反”类题目都必须绕过这个坑。第二把 1009 理解成十进制逐位反码。看到“十进制整数的反码”就下意识用 9 去减每一位结果和示例对不上。做题前先把题面的概念边界划清楚。第三忽略 0 的特殊性。0 的有效位无法按常规方式定义476 和 1009 给出了不同预期。遇到这种情况显式特判比试图写一个“天然兼容”的代码更可靠。5.2 我自己会跑的自测数据刷题时别只盯着示例那三个用例。建议每次写完之后手推一遍这组数据0 - 0 (476) / 1 (1009) 1 - 0 2 - 1 5 - 2 7 - 0 10 - 5 14 - 1 16 - 15 31 - 0 32 - 31 2^30 - 2^30 - 1 2^31 - 1 - 0其中 14 的二进制是1110取反是0001结果是 116 的二进制是10000取反是01111结果是 15。把这类边角数据跑通了函数基本不会有隐藏 bug。5.3 如果输入变成负数会怎样扩展思考一下。如果题目允许负数情况会变得有趣但复杂。负数在计算机里本身就是补码存储对它的“有效位”定义需要换一套规则比如按补码形式逐位取反再讨论符号位。大多数刷题场景不会这么考因为它引出了太多语义歧义。所以 476 和 1009 都限定在非负整数是有意为之。你不需要在这里过度较劲但知道边界在哪里能避免自己把通用解法错误地套到不合法的输入上。最后再分享一个小技巧本地测试时与其直接在提交页面上反复试错不如把这组边界数据写进一个测试函数里一次跑完。位运算题的 bug 往往集中在极值点提前自测比在评测里碰壁省时间得多。这也是我后来刷位运算题效率明显提升的原因。