每次有人让我推荐值得反复琢磨的算法题我几乎都会提到只出现一次的数字这道题。题目本身非常短给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现一次的元素并且要求线性时间复杂度、不使用额外空间。乍一看这就是一道统计频率的题似乎用哈希表就能解决。但不使用额外空间这个限制条件把所有舒适区的解法全部堵死逼着你重新思考数据在二进制层面的表现。等你真正理解异或XOR运算之后你会发现这道题其实不是考会不会用哈希表而是考能不能跳出常规思维用数学性质直接解题。这篇文章我会从题目本身出发讲清楚异或解法背后的原理、多语言实现、边界条件再延伸到几个常见变体比如出现两次的数字变成两个怎么办、出现三次怎么办最后聊聊这类位运算技巧在工程里的实际意义。1. 一道限制条件比题目本身更值得琢磨的题1.1 从数据清洗场景里看这题的原始需求先别急着把它当面试题这道题的应用场景其实很常见。举个最朴素的例子某公司在做日志对账时每条请求都会生成一个唯一的请求 ID正常情况下一次请求会产生两条记录——一条是写入记录一条是确认记录。但由于某些链路问题偶尔会漏掉其中一条导致某个 ID 只出现一次。这时候就需要从几十万条记录里快速找出这个落单的 ID。如果用 Excel 或者写脚本最常见的做法是排序后两两比较或者用哈希表计数。但数据量一旦大起来排序的时间复杂度是 O(n log n)哈希表虽然快但占用 O(n) 的内存。如果这是一台内存紧张的分析机又希望在线性时间内跑完哈希表就不是最优解了。这正是这道题想训练的核心能力当常规的数据结构方案被空间限制卡住时能不能从数据本身的性质找到出路。题目里其余元素均出现两次这个条件不是随便写的它在暗示解题者成对出现的东西一定有某种抵消机制可以利用。你只要找到了抵消机制问题就变成了一个公式推导。1.2 哈希表方案为什么被题目直接ban掉哈希表方案大概是这样的遍历数组把每个数字作为 key 存入哈希表遇到重复就在计数上加一最后再遍历一次找到计数为 1 的那个数字。思路非常直白也是正常人第一反应就能想到的解法。但题目明确要求只使用常量级别的额外空间这个约束直接把哈希表否掉了。为什么因为哈希表占用的空间随数组规模线性增长。数组有 1 万个元素哈希表就要存几千个键值对数组有 100 万个元素哈希表就要存更多的键值对。空间复杂度是 O(n)根本谈不上常量额外空间。有些人可能会说那我可以用一个变量存当前可能的答案遍历过程中不断替换这样不就能做到 O(1) 空间了吗问题在于你无法知道当前这个数字是不是只出现一次除非你事先知道它后面还会不会再次出现。在只遍历一遍的限制下单变量缓存方案没办法保证正确性。这也是为什么哈希表几乎是直观解法的唯一代表而题目恰恰要让你放弃这种最直观的思路去寻找更底层的数学规律。2. 异或运算看起来像魔法其实是数学性质2.1 异或的三种性质以及一个手推过程异或运算XOR在编程里通常写作^它的规则非常朴素两个二进制位相同则为 0不同则为 1。也就是说0 ^ 0 01 ^ 1 00 ^ 1 11 ^ 0 1从这个真值表可以推出三个直接可用的性质归零律a ^ a 0一个数和自己异或结果为 0。恒等律a ^ 0 a一个数和 0 异或结果还是它自己。交换律与结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)。正是这三条性质构成了整个解法的地基。拿一个具体数组来推演[2, 3, 2, 4, 4]。正常思维是数频率但异或的做法是把所有元素从头到尾异或一遍2 ^ 3 ^ 2 ^ 4 ^ 4根据交换律先把相同的 2 和 2 放在一起4 和 4 放在一起 (2 ^ 2) ^ (4 ^ 4) ^ 3 0 ^ 0 ^ 3 3最后剩下的3就是只出现一次的数字。这个推演过程你可以随便换数组试试只要其他数字都恰好出现两次它们就会两两抵消归零最后剩下的必然是那个落单的数字。为什么会这样因为异或本质上是在做二进制位的奇偶校验成对出现的数字在某一位上贡献的 1 的个数是偶数异或会把它清零只有那个只出现一次的数字会在各个位上留下自己独有的 1。这个过程不需要额外空间只需要一个变量存累积结果遍历一遍就完成时间复杂度 O(n)空间复杂度 O(1)完美契合题目限制。2.2 为什么加减法的浪漫解法有隐患还有一类解法也会被新手提出来既然成对出现那我把所有数字加起来然后减去成对数字的总和不就行了吗思路是先遍历一遍得到所有数字的和再想办法得到如果每个数字都成对时的总和两者相减差值就是只出现一次的数字。听起来可行但实现起来有个绕不开的问题你并不知道成对数字的配对基准是什么。比如数组[2, 3, 2, 3, 4]你算出来总和是 14但你不知道基准和是多少除非你额外用一个集合去记录出现过的数字有哪些这就又回到了需要额外空间。哪怕你用数学技巧硬算在极端情况下还会遇到整数溢出的问题——当数组元素很大、数量很多时累加和可能超过语言里整型能表示的范围。异或按位运算每一位只关心 1 的奇偶性天然规避了溢出问题而且在语意上也更加优雅。所以异或不是炫技而是这道题在数学上的本质解。理解了这一点后面所有变体都能顺着同样的思路推出来。3. 多语言落地代码讲清楚了边界也没那么可怕3.1 核心循环怎么写得直观且不易出错原理理解了代码其实短到离谱。Python 版本def single_number(nums): result 0 for num in nums: result ^ num return resultJavaScript 版本const singleNumber (nums) { let result 0; for (const num of nums) { result ^ num; } return result; };C 版本int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; } return result; }三个版本的逻辑完全一致result初始化为 0遍历数组时不断与当前数字异或。为什么初值要设成 0因为0 ^ x x第一个数字进来后结果就是它自己不会影响后续的异或累积。这里有一个写代码时需要留意的点不要为了让代码短而把异或塞进reduce之类的函数里堆一行除非你对这类函数非常熟悉。我见过不少人在面试手写时明明原理讲得很清楚结果写reduce时因为回调参数顺序搞错或者初始化值漏掉导致整个答案从头翻车。老老实实用循环反而显得稳健、可读性强。3.2 负数、大整数与非空数组这些边界有人会担心如果数组里有负数怎么办异或还成立吗结论是完全成立因为负数在计算机里以补码形式存储异或运算直接作用在补码的二进制位上不会出现符号位特殊处理的问题。比如[-1, -1, 2]-1 的补码和自身异或后同样是 0最后剩下 2结果依旧正确。如果有非常大的整数呢在 Java、C 等固定位数整型语言里异或不会产生溢出因为它只是位级别的运算不涉及进位。在 Python 这种整数无限精度的语言里异或同样安全。这是异或相比加减法方案的一个隐形优势。还有一个边界是数组非空这个前提。题目明确说了输入是非空数组所以result 0的初始值不会导致问题。如果题目换成数组可能为空空数组返回 0那代码依然成立因为循环不执行result保持 0可以当作一个合理默认值。这算是这道题里少有的边界条件恰好不会坑人的情况。另外如果你做的是 C 系语言循环里可以用for (int num : nums)这种范围遍历也可以用下标遍历。性能差异可以忽略但可读性上范围遍历更直观。这里值得提一个实际经验数组里元素类型如果是自定义结构体或者大对象异或就不再适用了因为异或操作通常只对基本整型有意义。这道题只讨论整数数组遇到更复杂的对象数组时得回到哈希表的思路上不要盲目套用位运算。4. 变体升级两个单身数字和出现三次的场景4.1 出现两个只出现一次的数字异或结果拆分组学完基础版之后很多资料会接着讲一道变体给定一个整数数组其中恰好有两个元素只出现一次其余所有元素均出现两次。找出那两个只出现一次的元素。先按基础版的思想把整个数组异或一遍。成对的数字全部抵消最后得到的结果是x ^ y其中x和y就是那两个落单的数字。问题来了x ^ y是一个合并后的值怎么把x和y拆开关键观察是x和y不相等所以x ^ y必然不等于 0也就是结果中至少有一个二进制位是 1。这个位上的 1 表示x和y在这一位上的值不同——一个是 0一个是 1。接下来用这个位作为分组依据把原数组分成两组该位为 1 的一组该位为 0 的一组。因为成对出现的数字在某一位上的值一定相同它们会被分到同一组组内依然两两抵消而x和y被这个位严格切分到不同组里。最后分别对两组做一遍异或就能各自得到x和y。具体实现时找某个为 1 的位有一个经典技巧mask x_xor_y (-x_xor_y)可以取出最低位的 1。在整数以补码表示的语言里-x_xor_y等于~x_xor_y 1按位与之后得到的结果一定只包含一个 1。如果你用的语言对负数位运算的处理不太熟悉也可以老老实实循环找从第 0 位开始逐个检查(x_xor_y i) 1找到第一个为 1 的位。两种方法殊途同归前者代码短后者更好读。这道变体非常有意思的地方在于它把基础版的一个变量累积异或升级成了异或 位掩码分组本质上还是在利用异或的相同抵消不同保留性质。你一旦理解了这个套路以后遇到找两个异常元素的场景比如找出数组里两个出现次数为奇数的数立刻就能建立起联想。4.2 出现三次的情况逐位统计取模如果说上面那道变体是异或的延伸那么其余元素均出现三次只有一个元素出现一次这道题就需要换一个角度了。因为三次不是偶数次异或的成对抵消逻辑不再适用。这时候可以考虑更底层的视角统计整个数组在每一个二进制位上 1 出现的次数。如果一个数字出现三次它在任意一位上贡献的 1 的个数一定是 3 的倍数只有那个只出现一次的数字会让某些位上的计数比 3 的倍数多 1。所以只需要用一个长度为 32或 64取决于整数位数的数组统计每一位上 1 的总数最后对 3 取模模 1 说明这一位属于那个落单的数字。举个例子数组[2, 2, 2, 3]。2的二进制是103的二进制是11。统计每一位第 0 位上2贡献了 03贡献了 1总数是 1第 1 位上2贡献了 33贡献了 1总数是 4。对 3 取模后第 0 位是 1第 1 位是 1拼起来就是11正好是 3。成对的重复数字在取模后全部归零落单数字的每一位独立显现最后拼回完整整数。实现上可以写两层循环外层遍历数组内层遍历 32 个位把每一位的计数累加。时间复杂度是 O(32n)常数项虽然比 O(n) 大了不少但 32 对绝大多数场景来说是个固定的、可以接受的小范围依然属于线性复杂度。空间上只需要一个固定长度的数组也算 O(1)。这种按位统计取模的思路比异或更加通用它不依赖偶数次抵消这个特性只要你知道重复次数是几把模数换成几就行。4.3 让它更通用重复 m 次也能解顺着上一节的思路继续推进如果数组里只有一个元素出现一次其余元素都恰好出现 m 次那么最朴素可靠的解法就是按位统计最后对 m 取模。因为出现 m 次的元素在每一位上贡献的 1 的个数都是 m 的倍数取模后归零落单数字的位保留下来。这个通用方案在工程上有一定价值因为它把一道看起来需要灵光一闪的题降维成了一类可复盘的模板遇到找出现频率异常元素的需求先统计每一位的计数再对频率取模。代价是位数是常数所以整个算法依然是线性时间、常量空间。不过要提醒一句当 m 是偶数时异或的简洁方案依然有效当 m 是奇数时就必须回到按位统计。做面试题或者日常排查问题时先判断重复次数是奇是偶再选择套路能省不少时间。还有一种更进阶的优化是用有限状态自动机来模拟每个位上计数对 3 取模的过程只需两个变量就能完成但这属于锦上添花的技巧实际写代码时反而容易混淆感兴趣可以单独练习不建议第一篇就啃这种版本。5. 从这道题带出的工程思维5.1 位运算在真实工程里的常见投影很多人学完这道题觉得异或只是一个面试专用技巧平时写业务代码根本用不上。这个看法其实不完全对。位运算在真实工程里的影子比你想象的多只是它们往往藏在框架和工具链的内部。一个非常经典的场景是奇偶校验位。在数据传输中发送方会把所有数据位的 1 的个数做异或生成一个校验位接收方收到数据后再做一次同样的异或如果不为 0说明传输过程中有奇数个比特位发生了翻转。这和只出现一次的数字的思路完全一致——成对的正确信息互相抵消异常位暴露出来。另一个场景是状态切换。比如某个配置项要在一个布尔值之间反复翻转flag ^ true就是一种极为简洁的写法。把它展开来看本质就是每次出现一次就在状态里累计一次和异或累积结果异曲同工。还有不少一致性哈希、负载均衡方案里会用到同值异或两次恢复原值的特性来做临时加解密或者 token 校验因为异或的逆运算就是它自己密钥相同的情况下(data ^ key) ^ key就能还原出原始数据。所以当你真正理解了异或再回头看这道题会发现它不是一道孤立的算法题而是帮助你建立用数学性质简化编程问题这一思维方式的最小训练单元。5.2 时间空间权衡面试和代码评审里怎么表达这道题还带出一个更通用的话题算法设计中的时间与空间权衡。哈希表方案时间 O(n)、空间 O(n)已经足够快但空间不达标异或方案时间 O(n)、空间 O(1)在时间复杂度相同的情况下省下了成倍的内存。有人可能会问现代机器内存动辄几个 G省这么点空间有意义吗有但要分场景看。在嵌入式设备、实时数据处理管线或者超大规模日志分析里内存可能非常紧张更关键的是O(n) 空间不只是占内存它还意味着需要额外的内存分配与回收、缓存命中率下降甚至可能触发 GC 压力。很多时候一个看起来一样快的 O(n) 空间算法在生产环境里的真实吞吐量反而比 O(1) 空间算法差不少。在代码评审时我一般会这样表达先说明最直观的哈希表方案讲清楚它是怎么做到 O(n) 时间的然后指出空间短板再引出异或方案重点讲为什么异或能在不引入额外存储的情况下达到同样时间复杂度。这种表达方式不是为了显得自己会很多解法而是让听的人明白你是基于约束条件在做取舍不是在背答案。6. 踩坑复盘我给这道题的解法的几条心得最后聊几个我自己学习和带人时踩过的坑希望对你有帮助。第一个坑是只会背异或不理解为什么。有些朋友看完答案代码写得飞起但换一个变体就傻眼。比如我把题改成找出出现次数为奇数次的唯一数字他虽然知道先异或但解释不清为什么异或能把奇数次出现的数字挑出来。实际上异或统计的是每一位上 1 的个数的奇偶性出现偶数次的比特位必然抵消出现奇数次的比特位必然保留。理解到这个层面才能举一反三。第二个坑是过早优化。我刚接触这类题时总想一步到位写状态机版本结果被ones、twos两个变量的循环更新绕得晕头转向。后来发现先写出按位统计取模的版本跑通所有测试用例再去研究状态机优化心理压力会小很多。先正确再优化这个顺序在算法学习里比任何技巧都重要。第三个坑是只在脑子里推不手写验证。异或的抵消过程在脑子里想是挺清楚的但真到面试或者写生产代码时手一抖就容易把result ^ num写成result num或者把循环顺序写错。我的习惯是写完之后拿一个最短的例子比如[1, 2, 2]在心里快速走一遍确认结果是 1 而不是别的值再提交。这个习惯帮我避免过不少低级错误。再分享一个面试小技巧如果被问到这道题不要一上来就写异或的答案哪怕你已经非常熟悉。先讲哈希表方案表示你理解常规解法再讲题目限制了空间引导自己思考位运算然后引出异或并花二十秒解释三个性质。这一套流程走下来面试官看到的不是一个背过答案的人而是一个会从约束条件推导解法的人。这两者之间的差距往往就是拿到 offer 和只是通过之间的差距。最后想说的是这道题虽然简单但它是一个很好的思维转折点。它让你意识到算法的力量很多时候不来自复杂的数据结构而来自对数据本身性质的洞察。希望你读完这篇文章不只是记住了result ^ num这一行代码而是真正理解了异或背后的奇偶校验思想然后把这种思想带到你遇到的下一个找异常数据的问题里去。