如果你刷过一阵子算法题大概率见过这道经典题目一个整数数组里除了两个数字只出现一次其他数字都出现了两次要求找出这两个只出现一次的数字。第一次看到这题的时候我其实挺不屑的心想这不就是哈希表一遍扫过去的事吗直到某次面试对面让我在白板上写最优解我写了哈希表版本对面问了一句“能不能不用额外空间”我才意识到这道题的真正考点不在“找出来”而在你懂不懂位运算。这道题的通用解法确实非常漂亮先用全员异或拿到两个目标数字的异或结果再从这个结果里挑出任意一个为 1 的二进制位把数组分成两组每组再做一次全员异或两个目标数字就分头落网了。整个过程只需要 O(n) 时间和 O(1) 空间代码不超过二十行。听起来简单但里面每一个细节都藏着位运算的核心功底比如为什么异或能抵消成对元素、为什么取最低位的 1 就能完成分组、为什么分组之后其他成对数字依然会被消掉。这篇文章我就以这道题为主线把位运算的底层逻辑拆开揉碎讲清楚。不光是给你 AC 代码更重要的是把每一步的“为什么”讲明白让你下次遇到变种题也能自己推出来。适合刚接触位运算的初学者也适合想把这题彻底吃透再去面试的人。1. 题目还原与三种解法的演化路径先把原题明确一下给定一个非空整数数组除了某两个元素只出现一次以外其余每个元素均出现两次。找出这两个只出现一次的元素。要求时间复杂度 O(n)、空间复杂度 O(1)。很多平台上的描述会强调“结果顺序不限”这是为了方便判题不用纠结先输出谁。我第一次做这题时第一反应当然是哈希表。遍历数组把每个数字出现的次数记录下来最后筛出次数为 1 的两个数字。这个方案很直观也绝对正确但空间复杂度是 O(n)。如果面试官只是考“会不会做”哈希表已经足够如果考“会不会最优解”那就必须上位运算。还有一种思路是用集合Set。遍历数组时如果当前数字已经在集合里就删掉否则加入。因为成对出现的数字会先加入再删除最终集合里剩下的就是那两个只出现一次的数字。这个方案的平均时间复杂度也是 O(n)很多语言里 Set 底层是哈希表所以空间复杂度同样是 O(n)。它的思路比字典更轻巧但依然没有摆脱额外空间。位运算解法则是完全不同的路子。它不借助任何容器只靠异或运算的数学性质就把两个目标数字从一堆成对数字里“过滤”出来。核心思想分三步第一全员异或把成对的数字全部消掉剩下两个目标数字的异或值第二从这个异或值里找一个为 1 的二进制位这个位说明两个目标数字在该位上取值不同第三用这个位把原数组分成两组两个目标数字必然分到不同组再对每组做全员异或就能分别拿到它们。这三个步骤每一步都值得展开讲。接下来我就按这个顺序把位运算的底层机制一点点拆开。2. 异或运算的“抵消魔法”成对元素的自动过滤机制异或运算的符号是^它的运算规则是“相同为 0不同为 1”。在二进制层面它的本质是按位比较两个 bit 一样就输出 0不一样就输出 1。比如5 ^ 35 的二进制是1013 的二进制是011逐位异或得到110也就是 6。从这个规则能直接推出几个重要性质。第一a ^ 0 a任何数和 0 异或都等于它自己。第二a ^ a 0任何数和它自己异或都等于 0。第三异或满足交换律和结合律也就是说a ^ b ^ c和a ^ c ^ b结果完全一样括号怎么加都不影响最终结果。这三个性质组合起来就构成了位运算解法最核心的“抵消魔法”。假设数组是[1, 2, 1, 3, 2, 5]我们从头到尾做全员异或1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5因为交换律可以重排成1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 51 ^ 1 02 ^ 2 0所以式子变成0 ^ 0 ^ 3 ^ 5 3 ^ 5也就是说全员异或的结果跟数组中其他成对数字完全无关只等于两个目标数字的异或值。这就像把所有成对的物品放上秤互相抵消最后剩下的就是那两个没有配对的东西。这里有个容易忽略的细节为什么数组中其他数字一定成对出现不会出现三四个相同的数字因为题目条件里写死了“其余每个元素均出现两次”。如果题目改成“大部分出现两次少数出现三次”那异或就不能直接消掉奇数次出现的数字了。所以审题要仔细位运算解法的成立是建立在题目限制条件之上的。在实际面试中如果题目条件稍有变化位运算的思路也要跟着调整这一点在后面的扩展部分会专门讲。理解了全员异或的作用之后你已经迈出了关键一步。现在你手里有一个非常关键的值x ^ y。但这个值是两个目标数字的异或结果你没法从3 ^ 5 6反推出3和5分别是多少。怎么办下一步就是从这个异或值里找线索把那两个数字分开。3. 从 x xor y 里定位差异位选对分组依据x ^ y的结果里每一个为 1 的 bit 都意味着什么回到异或的定义两个 bit 不同则结果为 1。所以异或结果中某个 bit 为 1就说明x和y在这一位上一个是 0 另一个是 1。换句话说这个 bit 就是x和y之间的一个“差异标记”。反过来如果x ^ y的某个 bit 是 0说明x和y在这一位上相同可能是都为 0也可能都为 1。这样的 bit 对我们区分两个目标数字毫无帮助。所以要分组我们必须找一个x和y不一样的位也就是在x ^ y中为 1 的位。拿前面的例子继续算3 ^ 5 66 的二进制是110。注意这里有个容易掉的坑3的二进制是0115的二进制是101如果只写三位的话3 ^ 5 110 6没问题。但实际在计算机里整数通常用 32 位存储最高位前面全是 0。这些高位 0 异或出来还是 0不影响结果但在做位运算时脑子里要把符号位和补码的规则想清楚尤其是负数的时候后面会单独讲。回到 6 的二进制110从低到高看第 0 位是 0说明 3 和 5 的最低位相同第 1 位是 1说明它们在第二位不同3 的第二位是 1 而 5 的第二位是 0第 2 位是 1说明它们在第三位也不同3 的第三位是 0 而 5 的第三位是 1。所以我们可以选第 1 位也可以选第 2 位作为分组依据。那具体选哪一个位呢最经典的写法是取“最低位的 1”也就是lowbit x ^ y -(x ^ y)。这个式子很多初学者第一次看到会懵其实它利用了补码的一个特殊性质一个数的负数在二进制表示里等于它的反码加一。x (-x)的结果恰好能提取出 x 的最低位 1 所在的位置其余位全部变 0。举例说明x 12二进制是1100。-x在补码表示下是0100假设只写四位实际是 32 位里有符号数的补码。12 (-12)等于1100 0100 0100也就是 4正好是 12 的最低位的 1 所在的位置。这个技巧在树状数组Fenwick Tree里也经常用是位运算里的一个经典小工具。回到我们的场景x ^ y 6二进制110。6 (-6)6 的补码负数二进制表示中最低位的 1 也在第 1 位所以6 (-6) 2对应二进制010。这个 2 就表示“第 1 位是分组依据”。有些读者可能会问为什么一定用最低位的 1用其他位置的 1 行不行答案是完全行。只要这个位在x ^ y中是 1就能把两个目标数字分到不同组。选最低位的 1 只是工程上最方便、最不容易出错的写法因为它只需要一行代码x -x就能算出来。如果你想选一个更高的位可以用循环从低位往高位找或者用一些内置函数如__builtin_ctz等但那样代码会更长。面试时我建议直接用x (-x)简洁又好解释。还有一个必须讲的细节为什么分组依据确定之后数组里的成对数字不会“捣乱”假设我们选择第 k 位作为分组标准把数组中所有第 k 位为 1 的数字分到 A 组第 k 位为 0 的数字分到 B 组。那么对于任意一个出现了两次的数字z它在第 k 位上的值当然是固定的要么是 0 要么是 1所以它的两次出现一定会被分到同一个组里。然后在组内做全员异或时这两个相同的z就会相互抵消就像它们在原数组里做全员异或时一样。换句话说分组的操作不会破坏成对元素的抵消特性它只把不同组的数字隔离开让两个目标数字分别成为各自组里唯一“落单”的元素。4. 分组后的全员异或两个目标数字如何分头落网一旦分组依据确定剩下的操作就机械而清晰了。拿到lowbit之后再次遍历整个数组对每个数字num判断num lowbit是否为 0如果为 0说明num在分组位上取 0归入 B 组如果不为 0说明取 1归入 A 组。A 组和 B 组各自做全员异或最终得到的两个值就是x和y。这里要注意一个细节num lowbit的结果不是非 0 即 1而可能是 lowbit 本身或者更大的值所以判断条件写(num lowbit) 0还是(num lowbit) ! 0才能正确区分不要写成(num lowbit) 1这是初学位运算时最容易犯的错误。因为lowbit是 2 的幂num lowbit的结果要么是 0要么就是lowbit这个值本身永远不可能是 1除非lowbit就是 1。这个细节如果写错了测试用例很容易暴露问题。整个算法的代码可以写成这样我用最经典的写法def singleNumber(nums): xorsum 0 for num in nums: xorsum ^ num lowbit xorsum (-xorsum) a 0 b 0 for num in nums: if num lowbit: a ^ num else: b ^ num return [a, b]同样的事情用 Java 写也是一样的逻辑public int[] singleNumber(int[] nums) { int xorsum 0; for (int num : nums) { xorsum ^ num; } int lowbit xorsum (-xorsum); int a 0, b 0; for (int num : nums) { if ((num lowbit) 0) { a ^ num; } else { b ^ num; } } return new int[]{a, b}; }以nums [1, 2, 1, 3, 2, 5]为例跑一遍完整流程全员异或1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 6。取 lowbit6 (-6) 2。按第二位分组1的二进制是0011 2 0进 B 组。2的二进制是0102 2 2进 A 组。1再次出现还是进 B 组。3的二进制是0113 2 2进 A 组。2再次出现还是进 A 组。5的二进制是1015 2 0进 B 组。A 组异或2 ^ 3 ^ 2 3。B 组异或1 ^ 1 ^ 5 5。返回[3, 5]正好是两个只出现一次的数字。算法的时空复杂度其实非常清晰两次线性遍历时间是 O(n)额外变量只有几个整数空间是 O(1)。这也是这道题能拿满分的原因。写到这里我忍不住想提醒一个很多人容易踩的坑如果你在某个在线判题平台上提交平台要求返回的数组里两个数字的顺序不限那没问题。但如果面试官说“请按升序输出”你就需要在返回前做个比较把小的放前面。这个不是算法层面的难点但实际写代码时容易漏掉导致面试表现打折扣。5. 代码边界检查与位运算易错点排查代码只有十几行但边界情况和易错点其实不少。我把实际刷题和面试过程中踩过的坑、还有很多人常犯的错误集中列出来你在自己写的时候可以对着检查。第一个坑是“只有一个元素只出现一次”的数组。题目明确说了有两个只出现一次的元素所以数组长度至少为 2。但如果你拿到一个长度只有 2 且两个元素不同的数组比如[1, 2]全员异或等于3lowbit 等于1按最低位分组1 进 B2 进 A返回[2, 1]依然正确。所以算法在长度较小的合法输入下也能工作。第二个坑是负数。位运算在负数上的表现跟正数不同因为负整数在计算机里用补码表示取反加一之后最高位符号位参与运算。x (-x)这个技巧对负数依然成立因为补码的设计目的就是让加减法在二进制层面统一运算。比如x -6它的补码在很多位上都是 1x (-x)依然能提取出最低位的 1。所以算法处理负数是没问题的但如果你用打印二进制的方式来验证可能会被一堆 1 吓到心里要有数。第三个坑是比较分组条件时写错判断式。前面已经讲过num lowbit的结果要么是 0 要么是lowbit本身所以判断(num lowbit) 1是逻辑错误。还有一个变体有人会写(num lowbit) 0这是对的因为lowbit是正数非 0 即代表num在该位为 1。第四个坑是取lowbit的两种写法的理解差异。除了x (-x)也有人写x (~x 1)这是因为-x在补码上正好等于~x 1两种写法完全等价。千万不要写x (~x)那会得到 0因为一个数和它的反码按位与每一位都相反结果全是 0。第五个坑是数组里存在 0 的情况。0 和任何数异或都等于那个数本身所以 0 不会影响全员异或的结果。但是分组时 0 在任意位上都是 0它只会进入 B 组对结果也没有影响。只要目标数字不是 0 且数组中 0 是成对出现的算法一样正确。如果目标数字本身就是 0题目通常会允许因为“只出现一次”也包括 0此时全员异或结果就是另一个数lowbit 也能正常计算算法依然成立。还有一个很有意思的思维实验为什么全员异或完得到的结果x ^ y一定不为 0因为如果它是 0说明x y但题目说这两个数字是不同的。所以x ^ y至少有一个 bit 是为 1 的。这也保证了lowbit一定存在不可能出现找不到分组依据的情况。这个逻辑链条可以用反证法来讲给面试官听会显得你思路很清晰。6. 变种题与工程场景中的位运算延伸思考这道题的思路不止能解这一道题。面试官特别喜欢在“只出现一次的数字”系列上做文章最常见的就是第二题和第三题也就是其他数字都出现三次只有一个出现一次或者有两个出现一次但你得从三个里区分。这些变种虽然都叫“只出现一次的数字”但解法思路完全不同。先说说“其他数字出现三次只有一个出现一次”的情况。全员异或在这里帮不上忙因为三个相同的数字异或的结果是它自己而不是 0抵消不了。正确思路是统计每一位上 1 的出现次数然后对 3 取余。因为其他数字都出现三次它们的贡献在每一位上都能被 3 整除剩下的余数就是那个只出现一次的数字在这一位上的值。这个解法需要按 32 位逐位统计时间和空间都很固定属于位运算的另一种典型应用用按位计数来找出“不按套路出牌”的元素。我曾经在一次模拟面试中把这道变种讲给一个同学听他听完感叹说原来位运算不只是异或还能当计数器用。再说一个变种如果把题目改成“有两个数字出现一次其他数字出现两次但要求两个数字必须按升序输出”你需要做的只是在返回前加上排序判断算法主体不变。工程里会不会用到这种位运算技巧说实话工作中直接写这种代码的频率不高但位运算的思维无处不在。比如在处理权限系统时一个整数的不同 bit 可以代表不同的权限位判断用户是否有某个权限就是检查某一位是否为 1设置权限就是按位或、取消权限就是按位与取反。做网络协议解析时一个字节的高 4 位和低 4 位可能分别代表不同的字段提取字段就得用移位和掩码。再比如做 Bloom Filter 时多个哈希函数要对同一个 bitmap 做置位操作底层也是位运算。所以别看题目花哨背后的“用 bit 表示状态”“用掩码隔离信息”的思想在真实项目里非常常见。还有一类比较偏的面试题会考察lowbit的变体应用。比如统计一个整数二进制里有多少个 1经典做法就是不断用x (x - 1)消掉最低位的 1每消一次计数加一。这个写法的原理跟x (-x)刚好互补一个是提取最低位的 1一个是直接消掉最低位的 1。掌握这两个技巧很多二进制计数的题目都能迎刃而解。回到这道“只出现一次的数字 III”如果你想在牛客或力扣上把位运算的功力再往上提一个台阶我建议你做三件事。第一把本题的哈希表解法和位运算解法都写一遍对比两种写法的速度差异在数据规模大的测试下位运算的速度优势会非常明显。第二把“出现三次”的变种题也实现一遍然后思考如果题目变成“其他数字都出现四次有两个数字出现一次”该怎么处理这个思考过程比记答案重要得多。第三试着用位运算去解一些看起来毫不相关的题目比如判断一个数是不是 2 的幂n 0 (n (n - 1)) 0或者在没有临时变量的情况下交换两个整数a ^ b; b ^ a; a ^ b这些都是在锻炼你对二进制本质的理解。我现在回头看这道题它最打动人的地方不是那个精妙的 lowbit 技巧而是一种思维方式当常规的“统计”手法碰到空间限制的时候能不能换一个角度从数的本质属性——二进制表示——出发把“是否相同”变成“异或为 0”把“是否不同”变成“某个位上的 1”。这种从表象到本质的切换正是位运算的魅力所在。引申开去很多看似需要额外空间的问题只要你能从数据本身的二进制特征入手都有可能被简化为常数空间的解法。这也是为什么很多面试官明知道候选人能答出哈希表方案还是坚持追问一路问到位运算的原因。