位运算这个标签我在算法笔记里反复写过很多次但每次讲“丢失的数字”这一类题还是能挖出一点新东西。题目原型不复杂一个长度为n的数组装着0到n之间的整数按理说每个数字应该出现一次但有一个数字不见了让你把它找出来。第一次见这道题的人本能反应通常是排序、哈希表或者等差数列求和可位运算更准确地说异或提供了一条O(n)时间、O(1)空间的路径还能天然避开求和法在固定位宽语言里的溢出问题。这篇文章是系列里的第二篇上一篇聊了最基础的题目原型和解法思路这次重点放在异或解法的原理拆解、方案对比、进阶变体和实操排坑上。适合看这篇的人有三类刚刷完基础位运算题、想把“异或配对”思路彻底吃透的准备面试、想掌握常数空间解法的被“丢失的数字”各种衍生题绕晕、想系统整理一遍的。我按自己平时排查问题的方式把推导、代码、踩坑都放在一起直接照着用就行。1. 从一道经典题说起数字到底是怎么“丢”的1.1 题目原型与为什么值得单开一篇先把题面完整写出来。给定一个包含[0, n]中n个数的数组nums找出缺失的那个数字。数组可能是乱序的n可以很大要求不能使用额外空间的话常规解法里只有两条路能走到O(1)空间要么先排序再顺序扫描要么用数学公式或位运算直接算。排序会改变原数组很多场景下不可接受公式法有溢出风险于是位运算成了最干净的选择。有人会觉得不就是一道“Easy”题嘛值得单独写一篇吗我的看法是值得因为这道题承载了位运算里非常重要的一个模型——“配对消除”。后面遇到的缺失两个数字、数组中唯一奇数次的数字、重复数字查找全是同一个模型在不同场景下的变体。把这个模型吃透比记住十道题的解还要有用。1.2 位运算解决这个问题的直观逻辑关于异或我常给朋友打一个比方它是一个“消消乐”游戏。两个相同的数字丢进去啪一下互相抵消不留痕迹一个数字单独丢进去它就待在原地。把“0到n的完整集合”和“数组里的实际集合”这两拨数字全部丢进同一个消除场所有正常配对的数字都消掉了最后剩下的那个就是只出现过一次的丢失数字。这个直觉真的很重要。很多人能把解法背下来但遇到变体就不会迁移就是因为没抓住“配对消除”本质。你只要记住异或不在乎数字顺序不在乎数组是否有序它只负责把成对出现的数字干掉把落单的留下来。抓住这一点后面几个变体基本都能自己推出来。2. 异或解法拆解核心原理与编码细节2.1 异或的三个性质与配对消除思想异或运算符号^是按位操作规则很简单两个bit相同结果为0不同结果为1。由此推出三个性质交换律与结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)意味着数字处理顺序完全不影响结果。归零律a ^ a 0同一个数字和自己异或会完全抵消。恒等律a ^ 0 a数字和0异或等于自己“消完剩下谁就是谁”。把这三个性质合在一起就得到“配对消除”的完整解释。0到n所有数字异或一遍得到的是全集X数组里所有数字异或一遍得到实际集Y最终X ^ Y中每个出现两次的数字都消失了缺失的数字只出现一次于是它就是答案。这个推导我建议在纸上写一遍。随便举个小例子比如n3缺失2全集0 ^ 1 ^ 2 ^ 3数组0 ^ 1 ^ 3合在一起算一遍2落单结果2。算完你就对那个神奇的结果毫无怀疑了。2.2 两种实现写法对比与复杂度评估先给最直白的写法def missingNumber(nums): n len(nums) result 0 for i in range(n 1): result ^ i # 完整集合 0..n for num in nums: result ^ num # 实际出现的数字 return result这个写法最大优点是可读性高逻辑和推导过程一一对应。还有一个更紧凑的写法利用数组索引天然覆盖0到n-1、再补一个n作为全集def missingNumber(nums): result len(nums) for i, num in enumerate(nums): result ^ i ^ num return result两种写法都是O(n)时间、O(1)空间。我实际更推荐第二种做面试展示因为它把“全集由索引补齐”这个细节体现出来了显得你真的理解了原理而不是背代码。但自己写工具脚本时第一种更不容易出错怎么选看场景。3. 方案对比为什么位运算比求和法更值得用3.1 求和方法与潜在的溢出问题等差数列求和几乎是人人都能想到的方案完整集合总和是n * (n 1) // 2减去数组总和就是缺失的数字def missingNumber(nums): n len(nums) total n * (n 1) // 2 return total - sum(nums)代码简单到不需要解释但坑藏在平台特性里。在C或Java这种固定位宽的整形语言里如果n接近INT_MAXn * (n 1)在乘法阶段就可能溢出算出来的total直接错乱后面减完得到负值怎么排查都查不出来。你可能要换long long或者先除2再加写起来就不是一行的事了。Python不用担心溢出因为整型无上限但这也容易让人忽略其他语言里的风险。我遇到的真实业务场景里n上亿的情况并不少见求和法在这种量级下必须非常小心。位运算是逐bit运算不存在进位放大问题这也是我后来习惯直接上异或的原因。3.2 位运算方案在边界场景下的优势除了溢出位运算还有几个不太好替代的优势数据流场景。数字一个接一个到达不允许回头重读异或只需维护一个变量边到边算流式处理天然契合。内存受限场景。在嵌入式环境里哈希表空间代价高排序也不现实一个寄存器就能跑完的异或方案优势明显。并行分块。可以先把数据分块每块内部各自异或再把所有块的结果合并异或结果一致便于横向扩展。这里放一个对比表方便日常选型方案时间复杂度空间复杂度是否受固定位宽溢出影响典型适用场景排序后扫描O(n log n)O(1)原地排序否数据量小、不在乎时间哈希集合O(n)O(n)否可读性优先、空间宽裕求和法O(n)O(1)是C/Java明显数字规模小、语言支持大整数异或位运算O(n)O(1)否大规模、流式、嵌入式我不太建议无脑迷信“位运算一定最优”。真正做工程时团队可读性也很重要但如果题目或场景对空间有硬性限制异或通常就是那个最优解。4. 进阶变体缺失两个数字与重复数字问题4.1 缺失两个数字的位运算分组解法从“丢一个”到“丢两个”难度一下子上去不少。全数组异或一次得到的不是某个具体数字而是两个缺失值a和b的异或结果xor_all a ^ b。接下来怎么办关键是要从异或结果里找到a和b的差异点。如果a ^ b ! 0说明a和b至少在某一个二进制位上不同。取这个位通常是取最右边的1即lowbit xor_all (-xor_all)把完整集合和数组集合里的数字都按这个位分组该位为0的进一组为1的进另一组。因为a和b在这一位上一个为0一个为1两人必然被分到不同组其他数字都是成对出现在各自组里自动配对消除。最后两组各自异或得到的值就是a和b。参考实现def missingTwo(nums): n len(nums) limit n 2 # 完整集合应为 0..limit共 limit1 个数 xor_all 0 for i in range(limit 1): xor_all ^ i for num in nums: xor_all ^ num lowbit xor_all (-xor_all) a b 0 for i in range(limit 1): if i lowbit: a ^ i else: b ^ i for num in nums: if num lowbit: a ^ num else: b ^ num return a, b这段代码有个容易写错的地方完整集合的边界是limit n 2而不是n 1。因为缺失两个数字后数组只包含原本0..n2范围里的n个数字补全全集时一定记得把上限写到n2。我刚开始写的时候就是这儿漏了一个1导致测试用例怎么都不过。后来我把上限单独定义成变量每一步都在注释里标注清楚再也没错过。4.2 查找唯一奇数次的数字与重复数字的变式同一种“配对消除”模型还可以迁移到另外几个常见题。先看“查找唯一奇数次的数字”数组里只有一个数字出现奇数次其余都出现偶数次找出这个数字。解法就是把所有数字全部异或——出现偶数次的数字两两抵消剩下的就是那个出现奇数次的数字。有同学问“出现3次算不算奇数次”算但注意x ^ x ^ x的结果是x本身奇数个x异或等价于x一次不影响结论。再看“查找唯一重复数字”给定长度为n1的数组数字范围1到n只有一个数字重复了一次找出它。解法是把数组元素全部异或再额外异或1到n的完整集合。正常数字出现两次直接消除重复数字原本出现两次、补全集合里又出现一次总共三次异或后还是它自己所以结果就是重复数字。这两个变体和“丢失的数字”在本质上是同一道题在一堆成对出现的数字里找出那个落单的。所以面试官问变体时不用慌抓住异或消消乐的核心思路现场推导完全来得及。5. 实操记录代码实现、测试用例与性能表现5.1 参考实现与自测数据我平时写算法笔记有一个习惯不光写理论还得把能直接跑起来的测试代码放进去。下面这套测试脚本我本地经常用覆盖了常规情况、边界情况和大规模随机验证。def missingNumber(nums): result len(nums) for i, num in enumerate(nums): result ^ i ^ num return result # 常规用例 test_cases [ ([3, 0, 1], 2), ([0, 1], 2), ([9, 6, 4, 2, 3, 5, 7, 0, 1], 8), ([0], 1), ([1], 0), ([], 0), ] for nums, expected in test_cases: assert missingNumber(nums) expected, (nums, expected) # 大规模随机验证 import random for _ in range(1000): n random.randint(1, 1000) nums list(range(n 1)) missing random.choice(nums) nums.remove(missing) random.shuffle(nums) assert missingNumber(nums) missing print(all tests passed)注意[]这个用例数组为空说明n0完整集合只有0缺失的就是0。边界条件最好一开始就想清楚不要等测试跑挂了再回来补。性能方面实测百万级数组在普通笔记本上一次遍历通常在几十毫秒量级且耗时随n线性增长没有任何意外的常数波动。对做算法题来说这个方案的时间表现已经是理论下限之一对工程场景来说它不占额外内存非常适合日志流水、上报链路这类“只过一遍数据”的场合。5.2 踩过的坑与调试工具推荐把位运算代码写错的原因绝大多数不是位运算本身而是循环边界、变量语义或语言细节。我整理几个自己踩过的坑第一循环终点写错。写range(n)而不是range(n 1)会让全集少一个数字结果和缺失值搅在一起。建议把“完整集合范围”单独定义成变量比如limit不要直接写n1这种魔法表达式。第二分组法里没有理解lowbit的作用。lowbit xor_all (-xor_all)取的是异或结果二进制下最右边的1。这个1说明两个缺失值在这一位上的值不同是分组依据。如果你随便取一个为1的位也可以但lowbit用位运算写出来最简洁而且要记住-xor_all在Python里是正常的补码取负不要错写成~xor_all 1以外的形式。第三调试时直接看十进制很难发现问题。我写了一个二进制打印的小工具排查时非常直观def bits(x, width16): return format(x, f0{width}b)配合上它你可以把xor_all、lowbit、分组后的a和b都打印成二进制一眼就能看出位模式是否符合预期。尤其是分组异或这种多步操作中间变量可视化比盯着十进制数字猜要快得多。第四不同语言对位运算的支持细节不同。比如Java里^运算符的优先级比低写复杂判断时该加括号就加括号C里int溢出是未定义行为依赖位运算时尽量用无符号类型。这些细节点跨语言踩过一次就会长记性。6. 常见问题排查速查与经验总结6.1 高频报错与思维误区把常见的现象、原因和处理方式整理成一张表遇到问题先查表省得反复试现象可能原因处理方式结果总是差1循环区间漏了终止值n检查range(n1)与索引覆盖范围结果全为0全集和数组集合混算前没确认配对关系先在纸上列出异或表达式再编码空数组返回异常没有考虑n0边界对长度0的输入单独验证分组法拿不到两个缺失值lowbit选错或分组维度没对齐确认xor_all非0并取最低置位C/Java里求和结果异常固定位宽整数溢出换成异或或使用更大位宽类型复杂表达式结果不可预期位运算优先级与其他运算符混淆给关键子表达式加括号思维误区方面我发现最典型的有三个。一是觉得异或只能解决“只丢一个数字”其实它的模型适用于任意“成对抵消后剩一个落单者”的场景。二是认为位运算一定比求和更快更稳实际复杂度级别相同只是常数和边界表现有差异选择时要看平台和场景。三是害怕用求和法只要语言无溢出比如Python求和法反而是最容易写对、最好维护的方案关键是清楚自己的运行环境再选型。6.2 实战心得什么时候不要用位运算分享一段真实经历。有一次团队做数据完整性校验需求是在一批上游数据里找出唯一缺失的序号数据规模很大但离线任务对运行时间并不敏感。我开始想用异或方案后来发现数据需要同时输出缺失序号的前后若干条关联记录用排序后扫描反而能顺便完成上下文收集。最后我选了排序方案异或只作为接口文档里的一行优化备注。位运算不是万能药当业务需求不止“找到数字”这一个目标时把时间和空间复杂度放到整个流程里去权衡才是正解。还有一个小经验对于多人维护的公共代码我倾向于用求和法加注释因为大多数人一看到n * (n 1) // 2 - sum(nums)就能秒懂异或写出来虽然漂亮但理解门槛更高新人接手时容易当成魔法。写代码本质上是在团队认知和运行效率之间找平衡这一点在算法题里往往被忽略。我在实际使用中最大的体会是位运算这套解法最怕的不是代码难写而是“不知道为什么对”。只要把异或的配对消除逻辑吃透丢失的数字、缺失两个数字、唯一奇数次数字、重复数字这些问题全部打通成同一个模型以后再遇到类似题反应快不少。真到面试或写工程代码时你甚至可以现场推一遍而不是依赖记忆里的模板。