力扣 268 这道题刷题的人基本都做过。题面很短给你一个包含[0, n]中n个数的数组nums找出那个没出现的数字。第一眼你可能想到排序、哈希、求和但真正让我对这道题刮目相看的是位运算解法——三行代码O(1) 额外空间不需要处理溢出也不用改原数组。这篇文章想把位运算版本彻底讲透异或为什么正好能定位丢失的数字初始值为什么要是n而不是0C 里位运算有哪些特别常见的顺序陷阱搞懂这些你不仅会做这一题之后遇到“出现一次 vs 出现两次”这一类的题思路会顺很多。1. 先看看题目和常规解法1.1 题目真正在说什么LC268 的完整题目是这样给定一个包含[0, n]中n个数的数组nums找出[0, n]这个范围内没有出现在数组中的那个数。示例 1nums [3,0,1]n 3输出2。 示例 2nums [0,1]n 2输出2。 示例 3nums [9,6,4,2,3,5,7,0,1]n 9输出8。这里最容易忽略的是“包含[0, n]中n个数”这句话的潜台词。理论上的全集是0, 1, 2, ..., n一共n 1个整数而数组长度是n说明正好从全集里拿走了恰好一个数字。不管缺的是哪一个数组里的数字一定都落在[0, n]这个闭区间内。理解这一点是所有解法的地基。排序解法靠“下标和值是否对应”来找缺失哈希解法靠“从 0 到 n 逐个查是否存在”求和解法靠“全集的累加和减去数组累加和”。它们推导的前提都是同一个你心里必须有那个完整的n 1个数字的全集而不是只盯着数组里的n个元素。1.2 常规解法的三条路先说排序。把nums排好序然后从头遍历如果nums[i] ! i那i就是缺的那个如果遍历完都没找到说明缺的是n。思路很直白代码也短int missingNumber(vectorint nums) { sort(nums.begin(), nums.end()); for (int i 0; i nums.size(); i) { if (nums[i] ! i) return i; } return nums.size(); }但排序是O(n log n)而且会改变原数组顺序。如果面试题要求不能修改数组或者数据量大到排序不划算这个方案就不够优。再说哈希。用unordered_set把数组里的数存进去然后从0到n逐个查是否缺失第一个查不到的就是答案。也可以用vectorbool marked(n 1, false)标记因为所有值都被限制在[0, n]里桶的大小正好能覆盖。时间O(n)但空间O(n)。int missingNumber(vectorint nums) { int n nums.size(); unordered_setint s(nums.begin(), nums.end()); for (int i 0; i n; i) { if (!s.count(i)) return i; } return -1; }哈希的问题是为了找缺失的那个数把整个数组都存了一份额外的常数开销不低还有哈希冲突的风险。第三种是求和法也是比较多人能想到的。用等差数列公式算出全集的和再减去数组累加和差值就是缺失数字int missingNumber(vectorint nums) { int n nums.size(); long long total 1LL * n * (n 1) / 2; long long sum 0; for (int x : nums) sum x; return (int)(total - sum); }求和法时间O(n)、空间O(1)已经很好。但有个隐患n * (n 1) / 2这个中间结果增长很快如果用int直接算到n 65535附近就可能溢出实际还得看平台。所以代码里必须用long long或者1LL强转否则结果可能是负数。把三种常规解法放一起看解法时间复杂度空间复杂度主要缺点排序O(n log n)O(1)慢且会改变原数组哈希O(n)O(n)额外空间大有哈希开销求和O(n)O(1)中间和可能溢出需要类型兜底1.3 为什么位运算值得单独说位运算解法的代码量是这里面最少的时间和空间也都做到了最优一趟遍历常数个变量。它不需要排序不分配额外内存也完全没有溢出的顾虑。我看过不少人在求职时把这道题的哈希写法背得滚瓜烂熟但问一句“求和会不会溢出”就开始犹豫。相比之下位运算版本没有任何大数中间态。异或过程中结果始终维持在原值域附近不会像求和那样数字越滚越大。这种“数值自锁”的特性在系统编程里有实际意义——你写内核代码、写网络协议、写嵌入式状态机时位运算通常是成本最低且行为最可控的操作。更关键的是思想价值。位运算解法背后的“成对抵消”模型可以原封不动迁移到好几道经典题目上比如第 136 题“只出现一次的数字”、第 260 题“只出现一次的数字 III”。把这些题放在一起看你会发现它们用的是同一个套路。2. 异或运算LC268 位运算解法的原理2.1 异或的规则与四条性质异或XOR的运算规则是两个位相同结果为0两个位相异结果为1。真值表就四行aba ^ b000011101110从真值表可以推出四条非常重要的性质位运算解题全靠它们x ^ 0 x任何数和 0 异或结果还是它自己。x ^ x 0任何数和自身异或结果为 0。交换律a ^ b b ^ a。结合律(a ^ b) ^ c a ^ (b ^ c)。由这几条可以推出一个特别有用的推论a ^ b ^ a b。因为先异或b再异或a相当于(a ^ a) ^ b 0 ^ b b。这个“成对抵消”的推论就是本解法的心脏。如果你觉得抽象可以这样类比异或就像一盏只有两种状态的开关键。你按一次开关状态改变再按一次相同的开关状态又变回去。同一个开关连续按两次等于没按。对应到数字上同一个数字异或两次等于没异或。换成生活的画面就好像舞池里的配对两个相同的人同时出现会互相抵消离场最终剩下的那个人就是落单的那个。2.2 配对抵消如何定位丢失的数字现在回到题目。假设缺失的数字是m那么全集是0, 1, ..., n数组里包含的则是除了m之外的所有数字。我们把两类东西全部异或在一起第一类是数组里的n个数字第二类是全集里的n 1个数字。对任何一个非缺失的数字x它在数组里出现了一次在全集里也出现了一次总共两次异或后归零。唯独m只在全集里出现一次数组里没有它所以不会成对抵消最后会原样留下来。于是有公式missing 0 ^ n ^ (0 ^ 1 ^ ... ^ (n-1)) ^ (nums[0] ^ nums[1] ^ ... ^ nums[n-1])代码上可以这样实现用变量ans从0开始先把数组所有元素异或进去再把0到n全部异或进去最后ans就是m。换成手动走查拿示例nums [3,0,1]所有数字参与异或0 ^ 3 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3其中3出现两次抵消1出现两次抵消2也出现两次0出现两次由于缺的是2数组里2只出现了一次没有配对的另一份因为全集中有它所以最后留下来的是2从位级视角看更深刻异或是每一位独立运算的。把所有数字异或在一起等价于在每一个二进制位上做奇偶统计——某一位上出现奇数次的数字最终该位为1出现偶数次该位为0。所以异或结果记录的其实是“哪些位出现了奇数次”而缺失数字正是那个在所有位上都“落单”的值。2.3 初始值为什么选 n 而不是 0这是初学者最容易踩的坑也是讨论位运算解法时最值得展开的细节。数组nums的长度是n循环里通过下标遍历只能访问到0到n - 1。但题目要求的全集是0到n一共n 1个数字。这意味着如果只在循环里异或下标i和数组元素nums[i]你漏掉了数字n本身。举个例子nums [0, 1]正确的缺失数字是2。如果代码写成int ans 0; for (int i 0; i nums.size(); i) { ans ^ i ^ nums[i]; }走一遍ans 0 ^ (0 ^ 0) ^ (1 ^ 1) 0结果是0但正确答案是2。问题就出在没把数字2纳入异或集合。所以解法里必须找一个方式把n带上。常见做法有两种写法一初始值直接设成nint ans nums.size(); for (int i 0; i nums.size(); i) { ans ^ i ^ nums[i]; } return ans;写法二循环结束后再补一次异或int ans 0; for (int i 0; i nums.size(); i) { ans ^ i ^ nums[i]; } return ans ^ nums.size();两种写法本质完全一样。当你理解了“为什么必须带上n”再看别人的代码就不会觉得那行ans nums.size()是魔法。它不是什么玄学只是在补齐那最后一个全集的成员。3. 实操C 代码实现与过程走查3.1 完整可运行的 C 解法把上一节的思路落成完整代码最简洁的版本是int missingNumber(vectorint nums) { int ans nums.size(); for (int i 0; i nums.size(); i) { ans ^ i ^ nums[i]; } return ans; }逐行解释int ans nums.size();这里存的是n它代表全集里最大的那个数字。为什么不是0前面已经说过了不加它就会漏算。循环里ans ^ i ^ nums[i];一次同时异或两个数。i是全集中的下标恰好等于0到n-1的所有数nums[i]是数组里实际出现的数字。每轮迭代这两个数分别和ans做一次异或。return ans;所有成对的数字都抵消干净剩下的就是缺失的数字。如果觉得一次异或两个数不好理解也可以拆开写成int missingNumber(vectorint nums) { int n nums.size(); int ans 0; for (int i 0; i n; i) { ans ^ i; ans ^ nums[i]; } ans ^ n; return ans; }拆开后每一步都很直白先把下标异或进去再把数组当前元素异或进去循环结束补上n。我建议新手先写这种等完全理解了再压缩成一行三段式。3.2 手把手走查一遍过程光看代码可能还不够直观我拿nums [3, 0, 1]完整跑一遍第一版代码。ians异或i之后ans再异或nums[i]之后000 ^ 3 313 ^ 1 22 ^ 0 222 ^ 2 00 ^ 1 1循环结束后ans ^ n(3)也就是1 ^ 3 2正好是缺失的数字。再看第二版ans初始为n的写法ans 3i 03 ^ (0 ^ 3) 0i 10 ^ (1 ^ 0) 1i 21 ^ (2 ^ 1) 2结果同样是2。边界用例也要过一遍。我自己写这道题时验证过这些输入输入数组n期望输出位运算结果[]000[0]111[1]100[0,1]222[1,2]200[0,2]211尤其注意空数组这种情况n 0全集是{0}数组里什么都没有缺失的就是0。第一版代码里ans 0循环不执行最后ans ^ 0结果0正确。这说明只要理解了“全集数量比数组多一个”边界用例也不会出错。3.3 复杂度和性能分析位运算解法的时间复杂度是O(n)空间复杂度是O(1)。和排序法比少了一个log n因子和哈希法比省掉了整个哈希表的空间和求和法比没有溢出风险。在常数层面这个版本也很快。循环体内做的事情是一次数组访问和两次异或操作。异或在 CPU 层面是单周期的位级操作没有分支、没有哈希计算、没有内存分配天然适合大数组场景。再加上对nums的访问是顺序遍历缓存命中率很高。哈希表虽然也是O(n)但随机访问和潜在的 rehash 会让常数大不少。实际工程里虽然很少有人为了“找缺失数字”专门写位运算但这种“不分配内存、单遍扫描、位级操作”的思路在嵌入式、网络协议解析、性能敏感的日志系统里非常常见。这也是为什么面试官愿意在这道题上追着问位运算——他们想确认你不只是会背 API而是理解底层的数据操作逻辑。4. C 位运算的坑位与避坑指南4.1 按位运算顺序运算符优先级血泪史C 位运算符的优先级很容易弄混这是“按位运算顺序”这个关键词背后真正的痛点。在 C 里相关运算符从高到低大致是这样 ! 相等运算符高 按位与 ^ 按位异或 | 按位或 逻辑与 || 逻辑或低注意一个很多人记反的点、^、|这三个位运算符优先级全都低于和!但又高于和||。换句话说位运算符夹在比较运算符和逻辑运算符中间。这个优先级顺序会带来什么后果看这句代码if (ans ^ i 0) { ... }你以为它表示if ((ans ^ i) 0)但 C 实际按运算符优先级把它解释成了if (ans ^ (i 0)) { ... }因为比^优先级高先计算i 0得到0或1然后再和ans做异或。写代码的人想判断“异或结果是否为 0”实际程序判断的却是“ans和(i 0)异或后是否为 0”逻辑完全变形。所以我的建议很直接凡是位运算和比较、赋值混在一个表达式里一律给位运算加括号。不要嫌括号丑不要秀运算符优先级熟练度。项目代码里可读性永远比少两个字符重要你也不想三个月后回看代码自己都搞不清当初想表达什么。4.2 按位或赋值 | 与异或赋值 ^ 的一字之差按位或赋值运算符|也是位运算里的高频操作但它和异或赋值^的行为有本质区别。^的特点是“可逆”同一个值异或两次等于什么都没做。|的特点是“累积”某一位一旦被置成1之后无论如何都不会自动变回0。这两个运算符在功能上差之毫厘谬以千里。很多初学者刷这道题时手上打着ans ^ i心里想的却是“把 i 合并进 ans”一不小心就敲成ans | i。拿nums [3,0,1]测试把正确的ans ^ i ^ nums[i]改成ans | i ^ nums[i]结果会变成这样ans 3i 00 ^ 3 33 | 3 3i 11 ^ 0 13 | 1 3i 22 ^ 1 33 | 3 3最终返回3而正确结果应该是2。因为|不会抵消已经出现的位它只会不断把更多的位“点亮”配对抵消的逻辑自然就失效了。区分这两个运算符可以记住一句口诀异或适合做“消消乐”按位或适合做“状态标记”。权限系统里把读、写、执行权限拼成一个位掩码用|是合理的而找缺失、找落单、判断奇偶出现次数必须用^。4.3 边界条件、负数与类型问题边界条件方面最容易漏的是空数组。nums为空时n 0唯一可能缺失的数字就是0。代码里只要正确初始化这个 case 会自然通过。另一种情况是缺失值恰好是n比如nums [0, 1]缺失2或是nums [0]缺失1。如果没有把n纳入异或集合缺失最大值时就会算错。还有个常被忽略的点数组里的数字可能包含负数吗LC268 的约束下不会但如果你想把这个套路用到更广义的场景要明白负数在 C 里是按补码存储的。异或操作对补码负数照样正确因为异或只看位模式不看正负语义。-1 ^ -1结果是0-1 ^ 0结果是-1完全符合“成对抵消”的规律。所以这个算法对任意整型数组都成立只要满足“全集和数组的差集大小为 1”这个前提。类型方面不需要太担心。LC268 的n上限是10^4数值很小。但如果将来遇到更大的输入位运算版本依然比求和安全——异或的结果不会像累加和那样产生超出单个int表达范围的中间量。这个特性让它在大整数场景下依然稳。5. 从一道题到一类题位运算缺失类题型的延伸5.1 LC136只出现一次的数字第 136 题是这道题的“原型”一个非空整数数组每个元素都出现两次只有一个元素出现一次找出它。解法比 LC268 更简单把所有数字从头到尾异或一遍int singleNumber(vectorint nums) { int ans 0; for (int x : nums) ans ^ x; return ans; }因为除了那个落单的数字其余所有数字都恰好出现两次异或后全部归零剩下的就是答案。LC268 和 LC136 的关系可以这样理解LC136 是“数组内部本身成对”LC268 是“数组元素和全集形成配对”。两者本质都是异或的“成对抵消”性质在不同场景下的应用。5.2 LC260只出现一次的数字 III第 260 题稍微进阶一点数组里有两个数字各出现一次其余数字都出现两次找出这两个数字。思路也很经典三步走把所有数字异或一遍得到a ^ b其中a、b就是那两个落单的数字。找到a ^ b中任意一个为1的二进制位通常取最低位的那个1可以用lowbit x (-x)快速得到。按照这个位是0还是1把数组分成两组。a和b必然分居两组因为它们在那个位上不同其他成对出现的数字会被分到同一组内组内异或后抵消干净。两组各自异或的结果就是a和b。这里面lowbit x (-x)又是另一个位运算的经典技巧它能在O(1)时间内取出一个整数最低位的1。这个技巧在树状数组、状态压缩 DP 里也经常出现。5.3 更多同套路题目一览顺着“异或 奇偶统计 成对抵消”这条线可以串起不少题题目特点位运算切入点LC136 只出现一次的数字单落单全员异或LC137 只出现一次的数字 II一个落单其余出现三次逐位统计模 3LC260 只出现一次的数字 III两个落单全员异或 lowbit 分组LC389 找不同两个字符串差一个字符所有字符异或这些题不用全部做但至少可以跟着思路手写一遍。你会发现只要抓住了“异或按位独立、奇偶统计、成对抵消”这三个关键词很多曾经的“奇技淫巧”都变成了有迹可循的套路。最后再分享个我面试时的实际体会。拿 LC268 当开场题时大多数人会先给出哈希或求和的解法能主动写下位运算版本的不超过三成。位运算解法不是炫技它把一个具体问题抽象成了“奇偶配对”模型这种抽象能力在系统编程、协议处理、状态机设计里都非常值钱。如果你只是背代码下次见到 LC260 还是会懵但如果你把“异或 二进制下的奇偶统计”这个视角烙进脑子里很多看似巧妙的位运算题其实都是同一道题。我的建议是找张纸把这道题写三遍第一遍故意把n漏掉第二遍故意把^写成|第三遍故意省略括号然后对照本文的检查点逐个修正。亲手踩过这些坑比看十遍博客都管用。