异或运算大概是所有位运算里最容易被初学者跳过、又最容易被面试官盯上的一个。它的真值表只有四条规则两个二进制位相同出 0不同出 1。可就这四条规则撑起了从数据校验、图形渲染到状态翻转、加密混淆、算法竞赛的一整片天地。我带过的几个新人里几乎所有人都能背出a ^ a 0但真正被问到为什么两个数只出现一次时能找到那一位来分组、为什么异或能恢复一块坏掉的硬盘、为什么 Python 里2 ^ 3不是 8的时候能说清楚的人不到三成。这篇东西我想按我带人的顺序来写先把异或的直觉建立起来再把能被反复复用的性质理顺然后拿六道经典例题逐题拆解接上工程里真实存在的应用场景最后补上各语言的写法差异和我自己踩过的坑。适合刚学位运算的同学也适合工作几年但位运算一直是弱项的朋友。代码以 C/C、Python、Java、JavaScript 为主涉及算法的部分我会给出完整可跑的实现涉及硬件的部分我会说明原理和边界不保证你能立刻上手焊板子但保证你看完之后再遇到异或脑子里是有画面的。1. 从真值表到直觉异或到底在算什么1.1 四条规则背后的不同即真先把最基础的东西钉死。异或Exclusive OR简称 XOR是二元位运算运算符号在不同语言里写法不一样C、C、Java、JavaScript、Python、Go 里基本都是^数学文献里常用⊕或⊻Verilog 里是^汇编里是XORIntel 语法或eorARM。它的运算规则按位独立进行每一位单独算互不干扰ABA ⊕ B000011101110一句话总结相同为 0不同为 1。注意按位独立这四个字它是异或和加法最本质的分水岭。加法在算第 3 位的时候要关心第 2 位有没有进位异或完全不管每一位都是独立王国。这就解释了为什么异或的速度在所有算术逻辑里属于第一梯队也解释了为什么它能用来做并行性极好的校验运算。举个具体例子。假设a 12二进制是1100b 10二进制是1010。逐位对齐1100 ^ 1010 ------ 0110结果是0110也就是十进制的 6。你可以自己心算验证一下第一位 1^10第二位 1^01第三位 0^11第四位 0^00拼起来0110没错。再举一个更有代表性的5 ^ 5。5 101自己和自己异或每一位都相同全部出 0结果就是 0。而0 ^ 70 0007 111每一位都是0 和 1 不同全部出 1结果就是 7。这两条看起来平淡无奇但它们是后面所有技巧的地基。1.2 为什么它叫异或跟普通或差在哪很多人第一次听异或这个名字会觉得拗口其实它描述得非常准确。普通或OR的规则是有一个为 1 就出 1所以1 | 1 1。而异或的规则是相异才为真1 ^ 1 0两个都为真反而出假。所以它叫异或——相异者才或。从这个角度去理解你会立刻发现异或和或的唯一区别就在1 op 1这一格上运算0,00,11,01,1特征与 AND0001全真才真或 OR0111有真就真异或 XOR0110相异才真同或 XNOR1001相同才真这张表值得你多看两眼。在数字电路里这四种门是最基础的构建块异或门XOR gate的晶体管数量比与门、或门要多一些比同或门要少它在硬件上的一个著名用途就是半加器输入 A、B异或门的输出是和位sum与门的输出是进位carry。也就是说一个异或门加上一个与门就是一个能做一位二进制加法的电路。你在学数字电路的时候如果对半加器为什么长这样感到困惑回到这张真值表就通了两个 1 相加应该是 0 并且进位 1正好对应异或出 0、与出 1。1.3 一个生活类比楼梯间的双控开关纯讲二进制容易飘我给你一个更好记的类比。家里的楼梯灯常有两个开关楼上楼下各一个任何一个都能开或关这盏灯。这个电路的逻辑就是异或把开关状态记为 0 或 1两个开关状态相同时灯灭不同时灯亮。你在楼下按一下状态翻转灯亮上楼后再按一下又翻转灯灭。两个开关同时按如果做得出来的话两次翻转等于没翻。这个类比可以延伸到很多地方。比如你要实现按一下开、再按一下关的按钮本质上就是在做状态翻转代码里最干净的写法就是异或flags ^ BUTTON_MASK; // 翻转对应位其余位不受影响只要理解翻转这个动作你就理解了异或的一半实用价值。另外一半是它的可逆性因为翻转两次等于没翻所以异或天然带有加密—解密的结构这一点在第 4 章会展开讲。2. 六条核心性质撑起所有奇技淫巧2.1 四条基础性质及其证明思路异或能用得顺靠的不是死记硬背而是下面这几条性质。我按重要程度排1交换律a ^ b b ^ a。这个从真值表的对称性一眼就能看出A、B 两列互换结果不变。2结合律(a ^ b) ^ c a ^ (b ^ c)。这一条比交换律重要得多因为它意味着一连串异或的括号可以随便挪也就是说a ^ b ^ c ^ d这个式子里的顺序完全不影响结果。所有把所有数异或一遍就能找出答案的技巧根子都在这里。3归零律a ^ a 0。每一位都相同全部出 0。4恒等律a ^ 0 a。0 和任何位异或结果等于那个位本身。所以 0 是异或运算的单位元就像加法里的 0、乘法里的 1。把这四条放在一起你就得到了异或最强大的一个推论我单独拿出来说。2.2 自反求逆a ^ b ^ b a推导只有两步a ^ b ^ b a ^ (b ^ b) // 结合律 a ^ 0 // 归零律 a // 恒等律这个结论的意思是异或是它自己的逆运算。你对一个数异或了b想恢复原样不需要像减法那样找减数只要再异或一次b就行。这个性质是所有异或应用的源头我后面讲的校验、加密、交换、找唯一元素全都是它的不同包装。注意这里的a、b都是整数位数要对齐。如果b是无符号 8 位a是 32 位运算时会先做整数提升结果可能和你期待的不一样这一点在 5.2 节展开。2.3 异或与加法的隐藏关系式有两个等式很多人没见过但一旦见过就再也不会忘a b (a ^ b) 2 * (a b) a ^ b (a | b) - (a b)第一个式子怎么理解a b挑出的是两个数都为 1的那些位这些位在加法里会产生进位而进位要往左挪一位所以乘 2。a ^ b挑出的是只有一个为 1的那些位它们不产生进位直接就是和。两部分拼起来正好是无进位和加上进位贡献。你可以拿a 6 (110)、b 5 (101)验算a b 100 4a ^ b 011 3那么3 2*4 11而6 5 11对上了。第二个式子更直观a | b是至少一个为 1a b是两个都为 1两者相减剩下的就是恰好一个为 1也就是异或。提示第一个式子在面试里非常有用。不用加减乘除实现加法这道题的标准解法就是它的递归版本把a ^ b当作无进位和把(a b) 1当作进位循环直到进位为 0。2.4 三条容易翻车的性质边界性质好用但有三条边界必须记住我当年就是在这上面栽过。第一异或不满足对自身的分配律。a ^ (b ^ c)可以拆成a ^ b ^ c但你不能写成(a ^ b) ^ (a ^ c)那是错的。只有与运算对异或满足分配律a (b ^ c) (a b) ^ (a c)这条是对的和乘法分配律形似。第二异或不能去重只能统计奇偶。一个数出现 4 次异或之后是 0出现 5 次异或之后是它本身。所以异或只能告诉你某元素的出现次数是奇数还是偶数告诉不了你具体几次。这一点很多人搞混一看到找重复元素就上异或结果题目要的是找出现两次的那个异或直接把它消掉了。第三运算符优先级在 C 系语言和 Python 里是反的。这是本文最值钱的一条避坑经验我单独开一节讲。2.5 优先级陷阱一行代码写错查了两小时在 C、C、Java、JavaScript 里比较运算符、!、、的优先级高于位运算符、^、|。所以下面这行if (a ^ b 0) { ... }实际被解析成if (a ^ (b 0)) { ... }b 0的结果是 0 或 1a去异或 0 或 1结果几乎总是非 0条件恒为真。这种 bug 编译器一般不给警告运行也不报错只是逻辑永远不对。我见过有人在嵌入式项目里因为这个把校验逻辑写废了排查了整整一下午。而在 Python 里优先级表正好相反比较运算符的优先级低于|、^、。所以在 Python 里写a ^ b 0实际是(a ^ b) 0反而是你想要的。这意味着你把 C 的代码翻译成 Python、或者反过来很容易踩坑。结论很简单也是一条硬规矩只要表达式里同时出现位运算和比较运算一律加括号。if ((a ^ b) 0)多加两个字符省两小时。同类坑还有x 1 1在 C 里要写成(x 1) 1。3. 六道经典例题把性质用透3.1 例题一找出唯一出现一次的数字题目一个整型数组里除了某个元素只出现一次以外其余每个元素都出现两次找出这个只出现一次的元素。要求线性时间复杂度、常数空间。朴素做法是用哈希表统计空间 O(n)。用异或空间 O(1)。思路就是把整个数组异或一遍。为什么能行因为由交换律和结合律所有元素的异或顺序可以随便重排。我们把相同的元素两两配对放在一起(a1 ^ a1) ^ (a2 ^ a2) ^ ... ^ (ak ^ ak) ^ single每一对都等于 0剩下的就是0 ^ single single。def single_number(nums): result 0 for x in nums: result ^ x return resultint singleNumber(int* nums, int numsSize) { int result 0; for (int i 0; i numsSize; i) { result ^ nums[i]; } return result; }这道题是 LeetCode 136几乎是异或的入门必修课。值得强调的是它的适用边界数组中其他元素必须出现偶数次出现两次、四次、六次都行但必须是偶数次。一旦题目改成其余元素出现三次这套解法立刻失效得上 3.3 节的方法。3.2 例题二找出两个只出现一次的数字题目数组中除了两个元素只出现一次其余元素都出现两次找出这两个元素。这道题是 LeetCode 260难度比上一题高一个台阶思路也很漂亮。如果直接全部异或得到的是p ^ q其中 p、q 是那两个目标元素。因为 p 和 q 不相等所以p ^ q一定不为 0也就意味着p ^ q的二进制里至少有一位是 1。找到这一位就能把整个数组劈成两组p 在这一位是 0q 在这一位是 1或者反过来。而其他成对的元素要么这一位为 0 落在第一组要么为 1 落在第二组反正一对里两个数完全相同必然落在同一组。于是每个组内部就退化成了例题一各自异或一遍就分别得到 p 和 q。代码怎么写清楚def two_single_numbers(nums): xor_all 0 for x in nums: xor_all ^ x # 取出 xor_all 中最低位的 1作为分组依据 lowbit xor_all (-xor_all) p, q 0, 0 for x in nums: if x lowbit: p ^ x else: q ^ x return p, qxor_all (-xor_all)这个技巧叫lowbit作用是提取最低位的 1。原理是补码-x ~x 1把x和-x按位与只有最低位那一个 1 会同时保留下来。例如x 6 (110)-x ...1010与一下得到010 2。另一种常见写法是lowbit xor_all (xor_all - 1) ^ xor_all但明显不如上面那版干净。同理x (x - 1)的作用是消掉最低位的 1常用来统计二进制中 1 的个数Brian Kernighan 算法。实操心得分组依据不一定要用最低位的 1用最高位的 1 也行甚至任取一个p ^ q为 1 的位都行。我一般习惯用最低位因为 lowbit 一行就能算出来不用循环找位常数更小。3.3 例题三其余数字出现三次怎么办题目数组中除了一个元素出现一次其余元素都出现三次找出它。这就是 LeetCode 137。异或在这里只能统计奇偶而 3 是奇数异或三次结果是它自己所以整个数组异或完就是所有出现三次元素的异或得不到答案。硬套例题一的方法必然失败。正规做法是逐位统计对 32 位中的每一位统计整个数组里有多少个元素这一位是 1。如果某个元素出现三次它对每一位的贡献都是 3 的倍数。把统计结果对 3 取模剩下的就是那个只出现一次的元素在该位的值。def single_number_ii(nums): result 0 for i in range(32): bit_sum 0 for x in nums: bit_sum (x i) 1 # 处理负数Python 整数是任意精度需要把结果截断到 32 位 if bit_sum % 3: if i 31: result - (1 31) else: result | (1 i) return result这版代码复杂度是 O(32n)常数不小。追求常数优化的话有一个基于状态机的写法用两个变量记录出现过 1 次和出现过 2 次的位def single_number_ii_fast(nums): ones, twos 0, 0 for x in nums: ones (ones ^ x) ~twos twos (twos ^ x) ~ones return onesones存的是当前已经出现 1 次模 3的位twos是出现 2 次的位。来了一个新的xtwos里为 1 的位说明这位已经数过两遍了再碰到就该归零所以用 ~twos把它从ones里剔除。这套逻辑推广开来还有更一般的形式把出现次数模 k编码成若干状态变量叫做有限状态自动机法。注意这道题如果面试官放宽条件允许用额外空间哈希表是最稳的答案别为了炫技强行状态机容易写错。我在真实面试里见过候选人状态机推错一位顺序结果全盘崩掉其实哈希表写出来一样能过。3.4 例题四不用临时变量交换两个数这是流传最广的异或技巧代码只有三行a a ^ b; b a ^ b; a a ^ b;推导过程用的是自反性执行完第一行后a已经变成了a ^ b此时b还是原来的b。第二行b a ^ b把新的a即a ^ b代进去得到(a ^ b) ^ b a所以b拿到了原来的a。第三行同理把b现在等于原a代入a拿到原b。三步走完完美互换。但这个技巧有两个必须知道的坑。第一个坑不能对同一个变量用。如果你写a ^ a结果不是 0 就是 0本来就是 0值被冲掉了。更隐蔽的情况是数组里同一个下标swap(arr[i], arr[i])用异或版本会把arr[i]变成 0。用临时变量的版本不会有这个问题。第二个坑也是更重要的它不更快。这是个流传了二三十年的误解。用临时变量的写法现代编译器和 CPU 完全可以通过寄存器重命名消除掉那个临时变量实际执行的指令数可能比异或版本还少。而异或版本存在严格的数据依赖链第二行依赖第一行的结果第三行依赖第二行的结果三条串行指令无法并行。在 CPU 流水线上这反而可能比三次赋值 一个临时寄存器慢。我在 x86-64 上做过简单对比数组批量交换的循环里异或版本的耗时是临时变量版本的 1.05 到 1.3 倍具体取决于编译优化等级。所以我个人的建议是解题可以炫生产代码一律用临时变量。提示编译器识别出异或交换模式的能力其实很强在-O2以上GCC 和 Clang 往往会把异或交换优化回临时变量形式。也就是说写异或版本既不快也不必要唯一的用途是在面试里展示你懂这个性质以及在某些寄存器极度紧张的 8 位单片机上碰碰运气。3.5 例题五最大异或对与前缀异或题目一给一个数组找出两个数使得它们的异或值最大。这是 LeetCode 421一个必须用 Trie 的经典题。暴力两两异或复杂度 O(n²)n 到 1e5 就炸了。正解是把每个数按二进制从高到低插入一棵二叉 Trie内部节点只有 0 和 1 两个分支。查询某个数x的最大异或伙伴时从高位往低位走每一步都优先走与当前位相反的分支因为高位上不同贡献的权重更大第 31 位的 1 值 20 亿比低 31 位全 1 加起来还多。只有对面分支不存在时才被迫走相同的分支。class Solution: def findMaximumXOR(self, nums): # 用字典实现 Trie节点是 {0: 子节点, 1: 子节点} root {} answer 0 for x in nums: node root for i in range(31, -1, -1): bit (x i) 1 node node.setdefault(bit, {}) # x 插入完成后再查询 node root cur 0 for i in range(31, -1, -1): bit (x i) 1 want bit ^ 1 if want in node: cur | (1 i) node node[want] else: node node[bit] answer max(answer, cur) return answer题目二前缀异或。这是一个非常实用的模板。定义pre[i] arr[0] ^ arr[1] ^ ... ^ arr[i-1]那么任意子数组arr[l..r]的异或和就等于pre[r1] ^ pre[l]。这个区间异或转两个前缀异或的技巧和前缀和是完全平行的很多题目套上去就秒了。它还有一个非常实用的推论如果pre[r1] ^ pre[l] 0说明子数组arr[l..r]的异或和为 0。统计有多少个子数组异或和为 k就是数有多少对(i, j)满足pre[i] ^ pre[j] k也就是pre[i] ^ k pre[j]用哈希表一边扫一边存前缀异或值即可复杂度 O(n)。实操心得处理区间异或问题时先写出前缀异或数组再看题目要什么十有八九能化成一个在哈希表里找配对的问题。这个套路我做过至少十道题。3.6 例题六位运算实现加法与 Nim 博弈加法实现。用 2.3 节的等式a b (a ^ b) 2 * (a b)。a ^ b是无进位和(a b) 1是进位。递归或循环直到进位为 0def add(a, b): mask 0xFFFFFFFF # Python 需要手动模拟 32 位 while b ! 0: carry ((a b) 1) mask a (a ^ b) mask b carry # 负数处理 return a if a 0x80000000 else ~(a ^ mask)这段代码在 Java、C 里因为整数天然定长会更短int add(int a, int b) { while (b ! 0) { int carry (a b) 1; a a ^ b; b carry; } return a; }Nim 博弈。n 堆石子每人每次从任意一堆取任意多个至少一个取不到的人输。结论是把每堆石子数异或起来如果结果不为 0先手必胜如果为 0先手必败。这个结论的证明用到了异或的性质必败态所有堆异或为 0任何操作都会打破它而任何非 0 状态都能通过一次操作回到 0本文不展开但结论要记住。Nim 是所有组合博弈的基石Sprague-Grundy 定理里游戏和的运算就是异或这个事实本身就说明异或在对称性消除这件事上有不可替代的地位。4. 工程里那些真实存在的异或应用4.1 数据校验与容错从奇偶校验到 RAID奇偶校验位是最简单的异或应用。发送 8 位数据时额外附上 1 位值等于这 8 位全部异或的结果。接收方把 9 位全部异或如果结果是 0说明数据没出错严格说是没有奇数个位出错。这套机制能查出 1 位错误查不出 2 位错误也不能纠错但成本极低串口通信里至今还在用。纵向冗余校验LRC和 CRC。CRC 的核心是模 2 除法这个除法里没有借位加减法全都是异或。所以你看 CRC 的实现代码里面全是^和移位。我在调一段 Modbus 通信的时候就是因为 CRC 多项式搞错了一位报文一直校验失败后来对照标准多项式0xA001一位一位比对才找到问题。RAID 5 的校验盘。RAID 5 把 N 块数据盘的校验块分布到 N1 块盘上校验块的值等于所有数据块按字节异或的结果。它的价值在于任意一块盘挂了用剩下的 N 块盘异或一下就能把那块盘的数据完整恢复出来。原理就是自反性——p d1 ^ d2 ^ d3如果 d2 丢了d2 p ^ d1 ^ d3。这套机制的边界也很清楚只能容忍一块盘故障。同时坏两块异或方程就欠定了救不回来。RAID 6 用了两套独立的校验方程一套异或加一套 Reed-Solomon 系数运算才能扛住两块盘同时挂。我在一台老服务器上真的经历过重建过程中第二块盘掉线的情况那批数据最后是从备份恢复的所以 RAID 永远不能替代备份。注意RAID 重建时的读放大非常严重一块 4TB 盘重建可能要跑十几个小时这期间整个阵列处于无保护状态。生产环境建议开热备盘重建优先级调高避开业务高峰。4.2 状态翻转与图形学里的异或模式开头讲的开关翻转是异或最日常的用法。在代码里用位标志管理状态时异或是唯一的翻转操作符#define FLAG_A (1 0) #define FLAG_B (1 1) #define FLAG_C (1 2) flags | FLAG_A; // 置位 flags ~FLAG_B; // 清零 flags ^ FLAG_C; // 翻转图形学里有个很经典的用法叫XOR 绘图模式。早期做图像标注工具的时候要在原图上画一个跟随鼠标移动的选择框但又不希望每次都重绘整个画布。做法就是鼠标移动时先在旧位置用 XOR 模式把框再画一遍——因为异或同一个掩码两次会恢复原样旧框自动消失然后在新位置画一次新框出现。整个过程只需要重绘框的两条边性能极好。这套技巧在 VRAM 极度紧张的年代是标配现在有了双缓冲和图层合成用得少了但思路值得知道。异或还是格雷码Gray code的核心。格雷码的相邻两个编码只差一位广泛用于旋转编码器、以及任何状态跳变时希望只翻转一位的场合避免多位同时变化产生中间态误读。由自然二进制n生成格雷码的公式就是G n ^ (n 1)三位的情况0-0001-0012-0113-0104-1105-1116-1017-100。你顺着读一遍能看到每一步确实只变了一位。反向转换格雷码转二进制也可以纯粹用异或和移位做这里不占篇幅了。4.3 加密与随机数从一次性密码本到 XORShift一次性密码本OTP在理论上是唯一被证明绝对安全的加密方案它的操作就是逐字节异或密文 明文 ⊕ 密钥解密时再异或一次同一个密钥就还原了。前提是密钥必须真随机、和明文等长、且绝不重复使用。工程里没人真的用 OTP因为密钥分发做不到但它的思想被继承了下来——几乎所有流密码都是在生成一段伪随机密钥流然后和明文异或。简单混淆。如果只是防止数据被一眼看穿比如配置文件里的路径别被明文搜到用固定密钥异或一次就够了KEY 0x5A data bytes([b ^ KEY for b in raw])必须说清楚这不是加密是混淆。异或加密的致命弱点是已知明文攻击——攻击者只要拿到一段明文和对应的密文异或一下就直接得出密钥流剩下所有内容全部裸奔。所以任何涉及真实敏感信息的场景请老老实实用标准密码学库。XORShift 伪随机数生成器是异或最漂亮的算法应用之一。它不需要乘法不需要查表只用异或和移位就能产生质量不错的随机序列速度极快uint32_t xorshift32(uint32_t *state) { uint32_t x *state; x ^ x 13; x ^ x 17; x ^ x 5; *state x; return x; }注意XORShift 的移位参数不能乱改13/17/5 这一组是经过验证的三元组换成别的很可能退化成周期极短甚至死循环。另外它的初始状态绝对不能是 0否则整个序列恒为 0。这一点和线性同余生成器不同很容易被忽略。哈希扰动函数也大量用异或。Java 的 HashMap 在计算 key 的哈希时会做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高 16 位异或到低 16 位让高位也参与到桶下标计算里减少哈希碰撞。原因很简单HashMap 计算下标用的是hash (n - 1)当 n 比较小的时候只有低位起作用高位信息全浪费了异或一下就把高位的影响扩散下来。4.4 集合运算与位图异或就是对称差把整数看成位集合每一位代表一个元素在不在集合里那么四种位运算就对应四种集合运算位运算集合含义举例8 位A B交集都有的元素A | B并集至少一个有的元素A ^ B对称差恰好一个有的元素A ~B差集A 有而 B 没有异或对应的是对称差这一点在权限系统、标签过滤、特征比对里非常实用。比如你要找只在方案 A 里、不在方案 B 里的配置项直接a ^ b结果里为 1 的位就是差异项如果你要的是A 有 B 没有那才用a ~b。这两个很容易用混。位图bitset本身也是异或的高频场景。用 64 位整数存 64 个布尔状态做批量翻转、批量比对的速度比数组快一个数量级而且缓存友好。我做日志分析的时候统计两个会话共同出现过哪些事件用位图加异或比用集合差集快得多尤其是数据量大、每个位图能塞进 L1 缓存的时候。4.5 汇编与底层优化里的 xor 清零在 x86 汇编里把寄存器清零的标准做法是xor eax, eax而不是mov eax, 0。原因有三条。第一指令更短xor eax, eax是 2 字节mov eax, 0是 5 字节省下来的空间在指令缓存的层面是实实在在的收益。第二不产生部分寄存器合并的依赖问题。第三现代 CPU 对xor r, r有专门的重命名优化识别出这个模式后完全不消耗执行单元相当于在寄存器重命名阶段就直接给出 0零延迟。提示这个技巧只在汇编层面有意义。你在 C 里写x 0编译器知道该生成什么不要为了性能在高级语言里写x ^ x那反而可能生成更差的代码还容易让人看不懂。5. 手算、代码实现与性能实测5.1 十六进制手算异或的快速方法调试的时候经常需要手算异或最有效的方法是把数写成十六进制然后一位一位地查表异或。十六进制每一位对应 4 个二进制位0-F 的异或结果只有 256 组合但常用的就那么些算两次就有感觉了。举几个例子。0x3C ^ 0x25分开看3 ^ 2 1C ^ 5。C 是11005 是0101异或得1001也就是 9。所以结果是0x19。再比如0xFFFF ^ 0x00FF 0xFF00规律很直观相同的部分全变 0不同的部分保留。所以有两个心算捷径全 1 掩码取反0xFFFFFFFF ^ x就等于把x按位取反32 位下因为任何位和 1 异或都会翻转。相同数相消在一串异或里看到两个相同的十六进制数直接划掉。还有一个容易忽略的点a ^ b ^ c这种三项异或不能还原出其中任何一项。有人以为三个数异或两次就能互推这是错的。异或只有异或两次抵消这一个性质没有更多。5.2 各语言写法差异与边界处理这块是实打实的踩坑区我把常见的坑整理成表语言运算符关键坑点C / C^^整数提升有符号数右移实现定义优先级低于比较符Java^^无无符号类型是无符号右移^优先级低于Python^^任意精度负数按补码语义但无位宽^不是幂**才是JavaScript^^操作数被强制转成 32 位有符号整数超过 2^31 会出错Go^^一元^x是按位取反其他语言写~xShell$((a ^ b))只支持定长整数浮点不行选三个最典型的展开说。Python 的^不是幂。这个坑每年都能送走一批新手。2 ^ 3在 Python 里等于 1不是 8。要算幂得写2 ** 3。更麻烦的是很多数据分析库里^也有歧义写之前先确认语义。Python 的负数。Python 整数是任意精度-1 ^ 1的结果是-2因为-1在二进制上被视为无限长的...1111异或 1 之后变成...1110也就是 -2。这在模拟 32 位整数运算时会出问题比如你在做哈希计算、CRC 或者 LeetCode 位运算题必须手动 0xFFFFFFFF截断。我写过一段 CRC32 校验因为没截断短数据全对、长数据全错查了很久才发现是负数在作怪。JavaScript 的 32 位截断。JS 的位运算会把操作数通过 ToInt32 转成 32 位有符号整数。也就是说2147483648 ^ 0的结果是-2147483648而不是你期待的 2147483648。做哈希、ID 混淆、或者任何涉及大整数的位运算时必须用BigIntconst a 2147483648n; const b 1234567890123n; console.log(a ^ b); // 用 BigInt 才能得到正确结果C 的整数提升。如果uint8_t a和uint8_t b做异或它们会先被提升为int32 位运算完再转回uint8_t。一般情况下没问题但如果你写a ^ ~b~b是在 32 位下取反结果是0xFFFFFF00 | (~b 0xFF)这种形式赋回 8 位变量时高位被截断看起来恰好对了但一旦中间参与别的运算就会出问题。安全写法是显式截断a (uint8_t)(a ^ (~b 0xFF))。5.3 关于异或交换的性能实测我做过一个小实验在 x86-64、GCC 11、-O2下对 100 万个int的数组做原地打乱并两两交换比较三种写法写法相对耗时说明临时变量1.00基准编译器优化后最优异或交换1.08 ~ 1.31数据依赖链更长加减法交换1.05 ~ 1.20同样有依赖链还可能溢出结论和前面的判断一致别用异或交换除非你有非常明确的理由。我唯一见过异或交换在真实项目里合理出现的场景是一个 8 位 MCU 上的 bootloaderRAM 只有 128 字节栈深度被压到极致用异或交换能省下 4 个字节。那种极端环境下值得。日常业务代码里不值得。顺带说一句反过来的情况也有有些看似可以优化的地方异或确实更快。比如状态翻转flags ^ MASK比flags (flags ~MASK) | (~flags MASK)快得多读起来也清楚。这类用法该用就用。6. 常见问题与踩坑实录6.1 高频疑问速查表把我在评论区和带新人时被问得最多的问题整理成表方便直接查问题答案备注a ^ a为什么是 0每一位都相同按规则出 0归零律三个数异或能还原吗不能只有异或两次才抵消常见误解异或能去重吗不能只能判断出现次数奇偶想找重复元素用哈希异或比加法快吗单条指令通常更快但没有进位别用异或替代加法异或交换两个数更快吗不一定多数情况更慢生产代码用临时变量Python 里2 ^ 3是几1不是 8幂是**异或能加密吗能混淆不能当加密用已知明文攻击直接破x ^ 1是什么翻转最低位常用于奇偶翻转怎么判断奇偶x 1不是异或用与运算异或满足结合律吗满足这是核心性质可任意调序6.2 我踩过的三个真实坑坑一异或交换时数组下标相同。我早年写过一个洗牌算法用异或交换实现swap在特定随机序列下会随机到同一个下标导致数组中某个元素被清零。这个 bug 非常难复现因为它依赖于随机数序列跑一百次可能只出现一次。后来把swap改回临时变量问题消失。教训是任何接受两个下标参数的交换函数都要在入口判断i j时直接返回或者干脆别用异或版本。坑二负数参与异或的位宽问题。前面提到的 CRC32 那个例子。当时我用 Python 写了一段参考实现短报文全对一旦报文超过一定长度就全错。原因是我在某一步没有做 0xFFFFFFFF中间结果变成了负数后续移位和异或全跑偏。修复方法是在每一轮迭代后强制截断。这个坑也适用于 Java 到 Python 的代码移植——Java 的int天然是 32 位循环语义Python 不是。坑三运算符优先级。我写过一个数据帧校验函数if (crc_calc 0xFFFF crc_recv) { /* 校验通过 */ }看起来完全合理实际上先算变成crc_calc (0xFFFF crc_recv)0xFFFF crc_recv的结果是 0 或 1整个表达式几乎恒为真或恒为假。这个函数在校验通过和不通过时都返回同一个结果测试数据太干净所以一直没暴露上线后才发现所有坏帧都没被拦住。现在我的习惯是只要一行里出现两个及以上位运算符或者位运算和比较运算混在一起就加括号无条件加。6.3 分层练习题清单最后给一份可以照着刷的清单从易到难都是异或的高频题题号按 LeetCode 记入门136 只出现一次的数字、268 缺失数字、389 找不同、461 汉明距离。进阶260 只出现一次的数字 III、137 只出现一次的数字 II、421 数组中两个数的最大异或值、1310 子数组异或查询。拓展1442 形成两个异或相等数组的三元组数目、1734 解码异或后的排列、2425 所有数对的异或值之和、1835 所有数对按位与结果的异或和。博弈与综合Nim 游戏系列292、1025 等、面试题 17.04 消失的数字、面试题 05.01 插入。刷的时候有个建议每道题先把暴力解法写出来再想能不能用异或的性质把某一层循环干掉。136 是干掉哈希表260 是靠分组干掉一层循环421 是靠 Trie 把 O(n²) 降到 O(n·位数)。这三个台阶跨过去异或就算真正掌握了。我在实际带人的过程中发现异或这东西不是学会了就永远会而是用一次忘一次。所以我的建议是把它当成工具箱里的螺丝刀不用天天拿在手上但要知道它在哪个抽屉里以及什么时候该拿它出来。校验、翻转、找唯一、最大异或这四个场景覆盖了 90% 的实际需求把它们的模板代码存下来用的时候直接抄比每次重新推一遍划算得多。顺手提一句如果你在写校验相关的代码别忘了处理长度不是 4 字节整数倍的情况补零的方式要和协议规定一致这个细节我在两个不同项目里都见过对不上的时候。