我印象里第一次意识到位运算能这么干净利落地解题就是这道 LeetCode 136 题“只出现一次的数字”。题目很短但信息量不小给你一个非空整数数组除了某个元素只出现一次以外其余每个元素都恰好出现两次让你找出那个只出现一次的元素而且要求线性时间复杂度、常数空间复杂度。说白了你可以遍历一遍数组但除了几个变量之外不许用额外容器。我第一次写的时候跟大多数人一样下意识就掏哈希表统计频次——能做但面试官接着问“能不能不用额外空间”就卡壳了。后来我才搞明白这个题的正解是位运算核心就一个异或操作。这篇文章想把这道经典的算法题彻底拆开讲透不仅给代码还把异或为什么能“成对抵消”、变体题怎么玩、面试现场怎么应对都捋一遍。适合正在准备算法面试的人也适合想真正理解位运算而不是背答案的读者。1. 题目拆解先看清它在考什么1.1 题面与约束条件题目原文其实就一句话我贴一下大致意思给定一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现了一次的元素。要求你的算法具备线性时间复杂度并且最好只使用常数额外空间。LeetCode 给的约束是1 nums.length 10^4-3 * 10^4 nums[i] 3 * 10^4。例子有两个输入[2, 2, 1]输出1输入[4, 1, 2, 1, 2]输出4。看着很简单但这个约束里藏着两个信息。一是数组长度上万O(n^2)的暴力双循环虽然能过但不体面碰上要求严格的面试官绝对会被追问优化二是nums[i]可正可负这意味着你的解法要对负数同样有效不能写个只处理正数的版本。1.2 常规解法的代价对比先说说我见过最多、也是最直觉的思路用哈希表统计每个数字出现的次数再遍历一遍找出次数为 1 的那个。时间复杂度能达到O(n)很理想但空间复杂度同样是O(n)需要额外装下一整套映射关系。这跟题目要求的常数空间是冲突的。如果面试官只是把题摆在桌面上、没提空间限制哈希表当然是最稳的答案可一旦把“常数空间”这个约束圈出来这条路就走不通了。排序也是一个容易想到的替代思路。先把数组排好序相同的数会挨在一起再相邻两两比较、步长 2 地扫描就能找到多出来的那个。但问题在于常用排序的复杂度是O(n log n)时间上不满足“线性”的要求。你可能觉得 Python 的内置排序很快但 Timsort 并不是原地排序最坏情况会占用额外内存。无论从哪个角度讲排序都不是这个题的正解。所以把几个方案摆在一起比较正解必须同时满足三个条件一次遍历、O(1)额外空间、不需要知道任何额外信息。三个条件全部指向同一个方向——位运算。方案时间复杂度空间复杂度是否符合题目要求暴力双循环O(n^2)O(1)不符合哈希表统计O(n)O(n)不符合排序后扫描O(n log n)O(1)原地排序不符合异或位运算O(n)O(1)符合2. 异或运算这道题的钥匙2.1 三条性质一次记牢异或运算的符号是^做的事情简单说就是逐比特比较两个位相同结果是0不同结果是1。真值表不用死记记住三条性质就够用了。第一条归零律x ^ x 0。一个数和它自己异或每一位必然相同结果自然是 0。第二条恒等律x ^ 0 x。任何数异或 0等于它自己。第三条交换律和结合律a ^ b b ^ aa ^ (b ^ c) (a ^ b) ^ c。也就是说运算顺序随便换先算谁后算谁结果完全不变。这三条性质合起来能玩出很多花样。比如不用临时变量交换两个变量的值a ^ b; b ^ a; a ^ b就是异或的经典应用。回到 136 题关键就在于把数组里所有数字从头到尾异或一遍成对出现的数字会各自凑成x ^ x直接归零最后剩下的自然就是那个落单的数。这个“两两抵消”的直觉比硬背代码重要得多。2.2 把整个数组异或一遍手推过程以[4, 1, 2, 1, 2]为例。设ans初始为0把数组里每个数依次和ans做异或。先看变形推导4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) # 交换律 结合律 4 ^ 0 ^ 0 4是不是很干净重复的1和2自动抵消。如果你更想看逐步轨迹长这样ans 0 0 ^ 4 4 4 ^ 1 5 5 ^ 2 7 7 ^ 1 6 6 ^ 2 4中间的5、7、6看起来没什么规律但走到最后剩下的依然是4。这说明一个问题异或抵消的是“配对”跟数字出现的先后顺序无关这正是交换律和结合律保证的。代码实现极其简单原理却值得反复琢磨。2.3 从二进制位看“成对抵消”有人会问凭什么重复出现的数字就能相互抵消把视角切到二进制位就清楚了。比如4 01001 00012 0010。在数组[4, 1, 2, 1, 2]里忽略4不看两个1在最低位各贡献一次1两个2在第二位也各贡献一次1。按异或的规则偶数次出现的1会被清零所以两个1和两个2对结果的贡献都是 0。唯一出现一次的数字4独有二进制最高位那个1最终异或结果就是0100也就是4。推广到一般结论对于二进制第k位统计所有数字在这一位上1的个数。如果是奇数答案的这一位就是1如果是偶数答案的这一位就是0。出现两次的数字无论在哪个位上贡献的都是 0 次或 2 次1对 2 取模之后必然归零。剩下的位模式恰好就是落单数字的位模式。这个“计数取模”的视角非常关键后面讲 137 题的时候还会用到。3. 代码实现与细节打磨3.1 多语言核心实现理解了原理代码短得有点不真实。Python 写出来是这样from typing import List def singleNumber(nums: List[int]) - int: ans 0 for num in nums: ans ^ num return ansJava 几乎一样public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }C 也差不多int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }为什么初值一定要是0因为0异或任何数等于那个数本身。如果把初值设成1或-1第一个数就被污染了结果自然不对。这个细节一分钟就能验证但确实有人会在面试现场写错。有些人喜欢用函数式写法一行搞定Python 里是reduce(xor, nums, 0)from functools import reduce from operator import xor def singleNumber(nums): return reduce(xor, nums, 0)但我个人更推荐面试时写那个朴素的for循环。原因很实际reduce版本看起来高级却容易让面试官怀疑你在背答案而且一行代码不好讲解过程。用最老实的循环边写边讲每一步在做什么反而显得底气足。3.2 边界条件与防御性写法LeetCode 本地保证了nums非空不过我的习惯是拿到任何题先想三种边界空数组、单元素、超大值。空数组直接抛异常或返回0都可以取决于业务语义单元素数组很好办遍历完就是它本身超大值数组里所有其他数都成对出现只有目标落单异或也不会溢出。想展示边界意识可以在代码里加上判空def singleNumber(nums: List[int]) - int: if not nums: raise ValueError(nums must not be empty) ans 0 for num in nums: ans ^ num return ans你可能会觉得在刷题平台上多写这几行纯属多余但面试里多写一下展示的是对空输入、异常场景的意识。这题代码本来就短稍微多做点边界思考整体观感会好很多。3.3 复杂度分析与负数问题复杂度很好说清楚时间O(n)一次遍历空间O(1)只有一个变量。面试官如果追问为什么是O(1)你就说无论数组多大额外变量数量恒定不随输入增长。还有一个容易被新手追问的点万一ans越界或者遇到底数是负数怎么办先说 Java 和 Cint位宽固定异或过程中的中间结果严格落在int可表示范围内不会溢出。Python 更省心int是任意精度根本不存在溢出概念。负数也不需要担心——异或是对每个二进制位操作补码表示下的负数和正数同样参与运算。你直接拿[-1, 2, 2]去测异或结果是-1完全符合预期。4. 变体题与扩展思路4.1 每个元素出现三次LeetCode 137 的两种解法136 讲透了面试官十有八九会接着加难度把“其余元素出现两次”改成“出现三次”这就变成了 LeetCode 137。此时直接异或行不通了因为x ^ x ^ x x三个相同的数字异或之后等于它自己抵消不掉。解法一逐位统计取模。出现两次的数字在每个二进制位上贡献偶数次1那出现三次的数字贡献的就是 3 的倍数次1对 3 取模同样归零。于是思路变成统计第i位上所有数的1的个数对3取模余下的就是答案在这一位上的值。def singleNumber(nums: List[int]) - int: ans 0 for i in range(32): cnt 0 for num in nums: cnt (num i) 1 if cnt % 3: ans | (1 i) return ans if ans 2 ** 31 else ans - 2 ** 32这个写法里有一个 Python 专属的坑Python 的int可以无限大如果二进制第 31 位的统计结果是1直接得到的ans会被当作正数但按 32 位有符号整数的规则这一位其实代表负号。所以最后要做一个转换当ans大于等于2^31时减去2^32把它变成对应的负数。我第一次写这个解法的时候漏掉了最后一行拿包含负数的用例一跑就错了排查了大半天才意识到是符号位的问题。解法二状态机掩码。如果觉得逐位统计O(32n)不够优雅可以用三个状态来模拟每一位出现的次数。ones记录出现 1 次的位twos记录出现 2 次的位某位出现第 3 次时ones和twos一起归零。def singleNumber(nums: List[int]) - int: ones 0 twos 0 for num in nums: ones (ones ^ num) ~twos twos (twos ^ num) ~ones return ones这个写法的关键在于更新顺序先更新ones再基于新的ones更新twos并且两者互斥。当某位已经出现两次twos为 1新的num不能让它进入ones当某位刚进入ones也不能让它立刻出现在twos。很多人第一次写会把这两句顺序搞反导致第 3 次出现时无法归零。建议手动拿[2, 2, 2, 3]走一遍比死记代码靠谱得多。4.2 两个只出现一次的数字LeetCode 260再往后加一个维度数组里有两个只出现一次的数字其余都是两次。打个比方现在有两名“落单者”不能像 136 那样一个异或就完事因为a ^ b不是一个数而是两个数的混合结果。核心思路分两步。第一步全部异或一遍得到xor_all a ^ b。因为a和b不相等xor_all肯定不是0所以它的二进制里至少有一位是1。我们取任意一个不为0的位通常取最低位diff xor_all (-xor_all)。这一步利用补码取负的性质把最低非 0 位单独摘出来。第二步按这个位把数组分成两组该位为0的一组该位为1的另一组。关键事实是a和b在这一位上必然不同所以它们被分到不同组而其余成对出现的数字在同一位上取值相同会被分到同一组组内异或后两两抵消。分别对两组做异或就能把a和b拆开。def singleNumber(nums: List[int]) - List[int]: xor_all 0 for num in nums: xor_all ^ num diff xor_all (-xor_all) a, b 0, 0 for num in nums: if num diff: a ^ num else: b ^ num return [a, b]组内为什么也敢用异或因为组内除了落单者其余仍然是成对出现的异或依然能抵消。这个套路比 136 稍微绕一点但底层逻辑一模一样——先异或找到差异位再按差异位分割。4.3 位运算在工程里的延伸有人刷完这题觉得位运算只是面试玩具其实不是。权限系统就很典型Linux 文件权限用三位表示读写执行不同权限之间用 OR 叠加检查权限用 AND取消权限用 NOT 加 AND。再比如布隆过滤器用多个哈希函数把元素映射到位数组上本质上也是位级操作。网络数据校验里常见的 CRC、奇偶校验底层思想和异或密切相关——你要快速判断一组数据有没有被篡改异或和校验几乎是成本最低的方案。所以 136 这个题真正带给我们的不是“背一个异或解法”而是建立一种条件反射当数据出现成对、多对一等结构特征时先想想有没有位运算的解法。这个习惯在系统底层、嵌入式、高性能场景里会很值钱。5. 面试现场从这道题看算法素养5.1 拿到题的正确思考路径面试里最忌讳的就是上来默写代码。哪怕这道题你已经刷过十遍也要从思考路径讲起。第一步复述题目把约束条件中的重要部分点出来“数组非空、除了一个数都出现两次、线性时间、常数空间”。第二步先用最直觉的方案试探“我可以先哈希表数频次时间O(n)但空间O(n)不符合常数空间要求所以放弃。”第三步观察数据特征“出现两次”意味着成对抵消什么运算天然支持抵消异或。第四步回到定义讲清x ^ x 0、0 ^ x x然后说明把全部数字异或一遍为什么只剩落单者。第五步写代码同时口头模拟一个用例。这套流程走下来就算面试官一开始没想过位运算解法也能顺着你的思路走。我练习时会刻意训练自己“先说方案再动笔”哪怕心里已经知道标准答案。因为面试要的不只是结果更是你能不能把决策过程讲明白。5.2 高频追问与应对列表整理一下常见的追问每条都有应对思路追问“如果只有一个数字出现奇数次其余出现偶数次怎么做” 答本质一样偶数次全部抵消逐个异或即可。追问“数组值域很窄但很长有没有更巧的方法” 答值域窄时可以用计数数组但如果值域与数组长度同量级空间就不省了。核心还是位运算。追问“不允许用位运算怎么办” 答哈希表在允许额外空间时是最稳的方案时间O(n)空间O(n)。追问“数组有序的话能不能更快” 答如果数组有序可以用二分通过比较相邻元素定位落单者复杂度降到O(log n)。但 136 本身不保证有序所以线性异或才是更通用的解法。这些追问其实在提醒你刷题不能只为了 AC得适应面试官不断收紧或放宽约束。每一种变体背后都是一种算法思想的取舍。5.3 一场模拟面试的复盘有次模拟练习面试官第一问就是 136。我飞快写完哈希解法后他面无表情地说“你看一下约束常数空间。”那一瞬间我意识到背答案的毛病被看穿了。于是重新捋了一遍写了异或方案。他又追问“为什么这个解法能保证找对”我说因为异或满足交换律和结合律重复元素必然成对抵消。他点点头然后立刻抛出 137 让我续写。复盘时我得到一个结论这题对熟练的刷题者来说根本没有难度真正的分水岭在于能不能把“为什么异或”讲清楚。面试官不会因为你写出 5 行代码就录用你他要听的是背后的算法意识和表达能力。后来我每次练习都会提醒自己算法答案只完成了 50%能讲清原理才算完整的回答。6. 高频疑问与自查清单6.1 高频疑问速查表疑问原因处理方式为什么异或能抵消成对数字x ^ x 00 ^ x x全部元素异或一遍负数会不会破坏结果位运算基于补码与符号无关直接参与异或无需特殊处理为什么不能先排序排序O(n log n)达不到线性时间用异或一次遍历初值为什么是 00 异或任何数等于它本身从 0 开始累加会不会溢出Java/C 的int位宽固定结果必在有效范围内无需额外判断能不能用集合解决可行但不是常数空间面试先说明不符合要求再转位运算其中“负数”这条被问到的概率很高特别是当你提到位运算的时候。我的建议是自己在本地跑几个负用例比如[-1, -1, 2]亲眼确认结果正确面试时才能讲得理直气壮。6.2 写代码前的自查清单动笔之前建议在心里过一遍这几条是否确认了数组大小、数字范围、是否允许修改原数组是否理解“线性复杂度”和“常数空间”的具体含义是否能先口述一遍异或的性质再开始编码是否手动跑过一个真实用例比如[2, 2, 1]是否知道如果再加一个落单者题目会变成 260 的变体这五条如果都能答上来136 基本上就是你的送分题了。与其背十遍代码不如花十分钟把这个思考链打磨顺。6.3 我对这道题的三点个人体会最后记录一点自己的心得算是对这道经典题的一个交代。第一数据特征就是算法线索。“成对出现”这四个字放在眼前解题方向其实已经写了一半。遇到问题时先观察输入的结构规律往往比急着套模板更有用。第二一题多解最有价值的地方在于比较成本。哈希、排序、位运算三套方案分别代表了空间换时间、时间换空间、用数学性质同时优化两者的思路。真正的算法素养就是能在这些方案之间做有依据的选择。第三位运算值得认真掌握越往底层走它的出场率越高。我刷完 137 和 260 再回头读一些系统代码对权限位、状态标志的处理就顺畅了很多。希望这篇文章能帮你把 136 这道题的原理吃透而不是只记住一行异或。