★ FEATURED ARTICLE 1. 题目解读与位运算基础先聊点实在的。LeetCode 476“数字的补数”和1009“十进制整数的反码”这两道题放在一起刷是特别聪明的选择——它们几乎共享同一个核心逻辑只是稍微改了改边界条件。如果你刚接触位运算这两道题能帮你把“按位取反”“掩码”“异或”这几个概念彻底拿捏住。我在带新人刷题时经常把这两题作为“位运算入门第一课”因为它们不涉及复杂的算法结构纯粹考察对二进制本质的理解。先说题目本质。所谓“数字的补数”并不是数学里那个“补数”比如十进制补数而是指对一个正整数的二进制表示把每一位的0变成1、1变成0不考虑前导零。举个例子5的二进制是101取反后变成010也就是2。所以476的答案就是2。1009题则稍微改了个说法把“补数”改叫“反码”而且多了个条件如果输入是0输出是1。其实0的二进制可以看作0反码就是1两题的解法在本质上完全一致。为什么这两道题适合用来学习位运算因为它们迫使你去思考“如何只翻转有效位而不动前导零”。直接对整个整数用语言自带的取反运算符比如Python的~num会把所有32位都翻转结果会变成负数显然不是题目要的。你必须要自己构造一个掩码把高位屏蔽掉。这个“构造掩码”的过程就是位运算里最常用的技巧之一。在深入代码之前先把位运算的几个基本操作过一遍。我们日常用的数字在计算机里都是二进制存储的位运算直接对这些二进制位进行操作。常见的有与、或|、异或^、取反~、左移、右移。这里最关键的其实是异或因为异或有一个性质任何数与1异或等于把它取反任何数与0异或等于它本身。也就是说对二进制位做“翻转”操作本质上就是和1做异或。这正是解决问题的那把钥匙。理解了这一点你就会明白为什么这两道题是“基础中的基础”——它们不要求你背复杂模板只要求你建立“位就是开关异或就是翻转开关”的直觉。2. 核心思路拆解从掩码到异或2.1 为什么不能直接用按位取反运算符先把最容易踩的坑摆出来。很多初学者拿到题目第一反应是取反那不就是~num吗在C或Java里这样写返回的却是一个负数。比如~5在32位整数里结果是 -6因为 ~ 会把符号位也一起翻转。Python里~5一样是 -6。但我们想要的是只翻转“有效二进制位”的结果。这里的核心概念是“有效位”。数字5的二进制是101有效位是从最高位的1开始的3位即101。它的前面其实有无数个前导0在存储时被略去了。我们只关心这3位把101翻转成010。所以必须先把这3位识别出来生成一个对应位数的全1掩码这里是111然后用原数跟这个掩码做异或101 ^ 111 010完美得到结果。2.2 构造掩码的两种常见路径如何构造这个全1掩码有两种思路我建议两种都掌握因为它们在后续其他题目中各有应用场景。第一种思路找到最高位的1然后向左扩展。比如数字5最高位1在第2位从0开始数那么掩码就是(1 3) - 1也就是1000 - 1 111。关键在于找到“最高位1的位置”。可以用循环右移判断也可以用语言自带的内置函数如Java的Integer.highestOneBitC的__builtin_clz等。第二种思路从一个数字开始不断将它自己或上它右移一位、两位、四位的结果把最高位1后面的所有位都填成1。这一步得到的数就是掩码。比如num 5二进制101。先num | num 1得到111也就是7。这个方法有个名字叫“Smearing”在算法题里经常用来快速生成掩码。两题都用这个思路就能统一解决。对于1009题唯一要特别注意的就是输入为0的情况。0没有最高位1如果按第一种思路(1 0) - 1会得到0异或后还是0但题目要求答案是1。所以单独判断一下if num 0: return 1。2.3 用“补数”和“反码”理解题目命名的差异顺便把概念厘清。在数字电路里“反码”ones complement是对一个二进制数逐位取反。正数的反码是它自己符号位为0数值位不变其实一般说的是带符号数。但LeetCode这里讲的不是严格的计算机组成原理定义而是“对一个整数的二进制表示翻转所有有效位”。476题叫“补数”Complement of Base 10 Integer1009题叫“十进制整数的反码”Complement of Base 10 Integer实际上1009题英文名就是“Complement of Base 10 Integer”和476一模一样。我当初刷的时候也奇怪为什么两道题名字几乎一样看了描述发现476题明确说输入是正整数1009题补充了0的情况其实这两题在LeetCode上是可以互相转化的。所以刷题时根本不用分开记解法记住一套流程改一行代码两道题直接AC。3. 代码实现与参数细节3.1 最直白的循环解法先写一个最符合直觉的版本用循环找到最高位的位置。以Python为例def findComplement(self, num: int) - int: # 找到最高位的1在哪里 highest 0 temp num while temp 0: temp 1 highest 1 # highest是二进制位数比如num5时最高位是第2位0基位数是3 # 构造掩码1 highest再减1 mask (1 highest) - 1 return num ^ mask注意这里highest计数的是“二进制位数”。比如5循环过程temp5, temp1 2, highest1temp2, temp1 1, highest2temp1, temp1 0, highest3循环结束highest3。13就是8减1得7即111。5^72。1009题只需要在函数开头加一行if num 0: return 1因为0的二进制是0按上面的循环highest0mask0异或结果0不符合题意。3.2 利用语言内置函数的高效版本Java里可以使用Integer.highestOneBit(num)直接得到只保留最高位1的数。比如5highestOneBit(5)返回4二进制100。那么掩码就是highestOneBit(num) * 2 - 1即(highestOneBit(num) 1) - 1。写出来public int findComplement(int num) { int mask (Integer.highestOneBit(num) 1) - 1; return num ^ mask; }简洁到没朋友。C也有类似思路用__builtin_clz计算前导零个数然后构造掩码int findComplement(int num) { int bits 32 - __builtin_clz(num); // 二进制位数 int mask (1 bits) - 1; return num ^ mask; }这里的__builtin_clz是GCC提供的编译器内建函数返回从最高位开始的连续0的个数不适用于num0所以1009题同样要先处理0。我很推荐新手先写循环版本因为你能清晰看到“位数”这个变量是怎么算出来的。内置函数虽然快但如果你不理解背后的位运算原理换个语言可能就不知道怎么用了。3.3 位掩码的边界值与溢出问题讲一个容易忽略的细节当num很大时1 highest会不会溢出如果是C或Javaint是32位有符号整数最高位是第30位从0计数1 30没问题但如果num最大是2^31-1它的二进制位数是311 31在Java里会变成负数因为符号位被置1导致掩码错误。LeetCode的测试用例里num是32位有符号正数最大值2147483647它的二进制是31个1位数是31131在Java中结果是 -2147483648减1后溢出回绕成2147483647这个恰好是正确掩码。虽然侥幸正确但逻辑上并不严谨。更稳妥的写法是用Integer.highestOneBit(num) 1后再处理或者直接使用 long 类型。在Python中则完全没有溢出问题因为整数是任意精度的。我在自己写代码时习惯用“先右移计数再构造掩码”的方式因为从头到尾不需要移位溢出。Python里可以直接用num.bit_length()这个方法一步得到二进制位数mask (1 num.bit_length()) - 1这个在面试的笔试环境里非常好用既清晰又不容易出错。在讲解中我通常会给三种写法让读者根据自己的语言习惯选择。4. 实操过程与核心环节实现4.1 完整解题步骤从读题到AC我把做题的完整流程拆开方便你照着自己走一遍。第一步手工验证。随便选一个数比如10。二进制是1010有效位4位。按题意反转每一位0101也就是5。用公式验证10 ^ ((14)-1) 10 ^ 15 5。对了。多做几个数建立起直觉。第二步处理边界。476题num是正整数不需要考虑0。1009题要考虑num0。另外如果num1呢二进制1掩码1结果0。试一下1^10合理。num2二进制10掩码11结果01即1。没问题。第三步写代码。我建议用你最熟悉的语言先实现循环版本确保逻辑正确。比如Pythonclass Solution: def findComplement(self, num: int) - int: if num 0: return 1 # 计算二进制位数 bits num.bit_length() # 构造全1掩码 mask (1 bits) - 1 return num ^ mask第四步跑测试用例。包括5-2、1-0、7-0111取反0000、10-5、0-11009题。再看几个大数比如1073741823二进制30个1结果应该是0。如果结果不对多半是掩码位数错了。第五步尝试优化。把循环改成位操作技巧体会不同写法的优劣。我当初刷完这两题后把方法总结成一句话“先计算位数构造全1异或收尾。”后来遇到很多类似的题比如“数字范围按位与”“2的幂”等都能从这句话出发。4.2 现场演示从N0到N最大值为了展示边界情况我把几个典型输入输出列出来你可以对照自己的代码验证。输入num二进制掩码输出补数解释001特殊11009题要求11101翻转成02101101(1)有效位2位5101111010(2)标准示例71111110全1翻转全010101011110101(5)多位验证214748364731个131个10最大正整数这里注意对于21474836472^31-1在Java中如果用1 31可能产生溢出但用Integer.highestOneBit安全因为highestOneBit(2147483647)是10737418242^30左移一位才是2^31依然在int范围内其实Integer.highestOneBit(2147483647)返回1301073741824乘以2即131是负数但减1后刚好回绕到2147483647。为了安全可以这样写int mask (Integer.highestOneBit(num) 1) - 1;这行代码在num2147483647时确实会得到正确的掩码因为溢出是定义良好的。但我更推荐在Java中使用无符号右移等更稳妥的方法或者直接处理int mask Integer.highestOneBit(num) - 1; mask (mask 1) | 1; // 等价于最高位1下面全1无论如何理解原理比依赖溢出回绕更重要。我见过不少人在面试时因这个边界被问倒就是没想清楚位移的位宽问题。4.3 不用异或还有哪些解法虽然异或是标准解法但为了加深理解我试过另外几种写法也分享给你。一种是“逐个位翻转”的循环。把num的每一位依次取出来和当前位置对应的1异或然后给答案设置对应位。这个代码比较麻烦但能强化对二进制位遍历的认知def findComplement(self, num: int) - int: res 0 bit 0 while num bit: # 取出第bit位 cur (num bit) 1 # 翻转 flipped cur ^ 1 # 设置到结果 res | (flipped bit) bit 1 return res这个写法的时间复杂度也是O(logN)但额外做的位操作更多。好处是它不依赖构造大掩码因此不会遇到移位溢出的问题。我在讲解时喜欢把这种解法作为“笨方法”展示然后引导读者发现异或掩码更优雅。实际上如果你理解了“取反”就是异或1这个笨方法就是同一个原理的显式展开。另一种思路是先将数字转换成字符串比如Python里bin(num).replace(0b,)然后对每个字符替换。但这样做就完全失去位运算的意义了而且性能也差。如果是在算法训练中我强烈不建议用字符串解法因为它掩盖了计算机底层存储的本质。不过作为头脑风暴可以提一句“如果你能把问题转化成字符串说明你已经理解了什么是二进制表示但下一步一定要回到位级别去解决。”5. 位运算常见坑与排查技巧这一part我整理自己在刷题和实际项目中踩过的坑很多都是文档上不会写的。5.1 坑一按位取反和逻辑取反分不清语言中的~是位取反!才是逻辑取反。在写代码时如果有人不小心把~num当成!num结果完全不是一回事。测试时你输入5期望2结果得到-6就会有点懵。记住~5 -6这在所有现代计算机中都是因为补码存储是符合预期的只是不符合题目预期。所以遇到“取反”需求先问自己真的要对每一位取反吗还是只反转有效位5.2 坑二掩码位数多了一位或少了一位如果mask构造为(1 (bits-1)) - 1那么掩码比有效位少一位比如5对应11101 ^ 011 110结果是6明显不对。很多人在“位数”和“指数”之间搞混。比如位数是3掩码是2^3 - 1不是2^2 - 1。我建议你每次写完都验证一下mask num是否等于num如果正好等于说明掩码覆盖了num的所有有效位。比如5和75 7 5因为101包含在111内。如果mask位数少了5 3 1并非5你立刻就能发现问题。这个自查技巧很实用。5.3 坑三1009题忘记处理0LeetCode 1009之所以单独列出来就是因为在0的处理上和476不同。如果直接把476的代码提交1009的0用例会直接报错。所以刷题的时候我建议把两题放在一起对比并养成一个习惯任何涉及“二进制表示”的题目先考虑0的特殊性。0没有二进制前导1很多东西都跟正常数不一样。例如判断一个数是否为2的幂0要单独排除统计二进制中1的个数0的答案是0。这些都是老生常谈但最容易遗漏。5.4 排查技巧用位移验证思路当你拿到一个数不确定自己的逻辑对不对时可以用笔算一遍二进制过程。比如num 18二进制10010位数5掩码11111异或结果01101即13。然后写一个小脚本输出中间值num 18 bits num.bit_length() mask (1 bits) - 1 print(bin(num), bin(mask), bin(num ^ mask))看到输出0b10010 0b11111 0b01101就非常直观了。我在给学生讲题时经常用这个调试技巧比单看结果更容易定位问题。5.5 另外两个容易忽视的边界第一个是Java的Integer.highestOneBit(0)返回0这时(0 1) - 1是-1异或0得到-1所以1009题必须提前处理0。第二个是C中__builtin_clz对0未定义千万不要传入0。这两种情况都属于“编译器/运行时行为依赖硬件和实现”的细节在跨平台时很容易出毛病。最稳妥的方案是先在语言层面排除0再用内置函数。6. 从补数看位运算的真实应用场景刷题刷到一定程度你可能会想这玩意儿除了考试还有什么用其实位运算在真实开发中非常常见补数或者掩码的思想应用极广。第一个场景是权限系统设计。比如Unix文件权限用三个八进制位表示读、写、执行。如果要临时去掉某个权限就是对对应的位取反后做与操作。比如当前权限是rw-二进制110想去掉写权限就构造掩码101然后110 101 100得到只读。这里构造“只保留某些位”的掩码和LeetCode 476中构造全1掩码的思路一模一样。第二个场景是图像处理。像素的颜色值通常以RGBA四个通道存储每个通道8位。如果要提取红色通道就是pixel 0xFF000000这种掩码操作。反过来如果想清除某个通道就是先取反掩码再做与操作。你在图像库的源码里经常能看到这类位运算效率极高。第三个场景是网络编程中的子网掩码。子网掩码就是连续的全1位计算网络地址时用IP和掩码做与运算。如果你想“翻转”某个网段的位异或掩码也是常用手段。虽然现在的开发框架封装了很多但理解底层逻辑对排查网络问题还是很有帮助的。第四个场景是状态压缩。在算法题中经常用一个整数的每一位代表一个布尔状态比如“哪些灯开着”。翻转某个状态就是state ^ (1 k)。这个操作几乎就是LeetCode这两道题的翻版。如果你状态压缩DP写得顺手这两题其实就是在教你基本的开关操作。就我个人的开发经验来说位运算最大的价值在于可读性之外的高性能。在for循环里一条位运算指令比一次分支判断快得多。对于追求极致性能的基础库位运算就是日常工具。所以别看476、1009是简单题它背后这一片技能树值得你花时间好好点一点。最后分享一个实际操作中的小技巧刷这类位运算基础题时不要只追求AC试着用多种语言各写一遍。比如Python写一遍Java写一遍C也写一遍。你会注意到不同语言对整数的处理细节差异溢出、无符号、内置函数这些差异往往是面试官最喜欢追问的点。我当年就是靠这两道简单的题把bit_length、highestOneBit、__builtin_clz这几个函数全摸了一遍后来再遇到“位运算”标签的题基本都不慌了。如果你也想练习我建议把476和1009放在同一天先手写逻辑再敲代码完成后用num0、num1、num最大值三个边界测试去验证。这两道题做完你会发现位运算不再是一堆抽象的符号而是像开关灯一样自然。
阅读完成 · 觉得有帮助？
