深度剖析 XOR 交换技巧：真有用还是花架子？

什么是 XORXOR 是“Exclusive OR”异或的缩写我们用 X 而不是 EOR是因为 X 更酷。XOR 有个不太知名、也没那么酷的“朋友”——“Inclusive Or”或也叫“同或”IOR。这两个术语源于英语以及其他许多语言中的一个问题即“or”这个词有两种不同的用法。二者的区别在于当有人说“A or B”时是允许同时取 A 和 B还是只能取其中一个在数学和计算机领域我们需要更精确的表达因此将这两种情况分别用 XOR不能同时取和 IOR可以同时取来表示。为了让这一点更清晰我们来看几个现实生活中的例子。我从迪士尼乐园的网站上选了几个例子。先来看迪士尼乐园的一条规定不能“骚扰或伤害野生动物”这听起来很合理如果你一边踢鸭子一边辱骂它那你既骚扰又伤害了野生动物。显然这里的“or”是“包含性”的如果你试图辩解“我不是在‘骚扰或伤害野生动物’我是两者都做了”你还是会被赶出乐园。另一方面在小吃区“全牛肉热狗套餐”搭配“一个橘子或一小袋薯片”。这里的“or”是“排他性”的你可以选橘子也可以选薯片但不能两者都要无论你怎么指着那个因骚扰和伤害鸭子而被赶出乐园的人迪士尼也不会承认他们的规定有矛盾。我们如何判断“or”是包含性还是排他性呢有一些通用规则但很多时候还是要根据上下文来判断。不过在计算机领域为了表达清晰当我们想说“A 或 B但不能同时取”时就会用“XOR”。什么是逻辑 XOR逻辑 XOR 接受两个布尔值真或假当且仅当其中一个为真时返回真。我们可以用一个表格来表示| A | B | A XOR B || --- | --- | --- || false | false | false || false | true | true || true | false | true || true | true | false |有一种理解 XOR 的有用方式A XOR B 等同于问“A 和 B 是否不同”。如果不同结果为真如果相同结果为假。这一点在后面会很重要。什么是按位 XOR 运算符在大多数编程语言中^ 运算符执行按位 XOR 操作。这意味着它会取两个整数将它们的二进制表示对齐然后对每一对位独立应用逻辑 XOR。例如我们对 12 和 10 进行 XOR 运算plaintext12 110010 1010----------^ 0110 6每一列都是一个逻辑 XOR1 XOR 1 01 XOR 0 10 XOR 1 10 XOR 0 0。按位 XOR 有两个对交换技巧很重要的性质1. **自反性**对于任何值 aa ^ a 0。每个位与自身相消。2. **恒等性**a ^ 0 a。与 0 进行 XOR 运算不会改变值。结合这两个性质如果我们计算 a ^ b ^ b两个 b 会相消得到 a。反过来也一样a ^ b ^ a 会得到 b。记住这个结论。什么是 XOR 交换技巧XOR 交换技巧利用上述性质在不使用临时变量的情况下交换两个变量的值。以下是用 C 语言实现的代码ca ^ b;b ^ a;a ^ b;让我们用 a 5 和 b 3 来跟踪这个过程| 步骤 | 操作 | a | b || --- | --- | --- | --- || 开始 | | 5 | 3 || 第 1 行 | a ^ b | 5 ^ 3 6 | 3 || 第 2 行 | b ^ a | 6 | 3 ^ 6 5 || 第 3 行 | a ^ b | 6 ^ 5 3 | 5 |第 1 行执行后a 存储 a ^ b。第 2 行执行后b 存储 b ^ (a ^ b)简化后为 ab 相消。第 3 行执行后a 存储 (a ^ b) ^ a简化后为 ba 相消。值已经交换而且我们没有使用临时变量。这是一个很巧妙的编程技巧在网上很多地方都能看到相关讨论。问题是它真的有用吗让我们一探究竟。用法 1交换局部变量最常见需要交换两个变量的场景是在函数内部使用局部变量。我们来写三个函数看看编译器会如何处理。首先是一个基准函数直接返回 a / bcint div_direct(int a, int b) {return a / b;}现在一个使用 XOR 交换 a 和 b 然后进行除法的版本cint div_xor_swap(int a, int b) {a ^ b;b ^ a;a ^ b;return a / b;}最后一个使用临时变量的普通版本cint div_temp_swap(int a, int b) {int temp a;a b;b temp;return a / b;}XOR 交换和临时变量交换的版本都应该计算 b / a因为我们在除法前进行了交换。让我们用 clang -O2 在 x86 - 64 架构上编译这三个函数看看生成的汇编代码plaintextdiv_direct:mov eax, edicdqidiv esiretdiv_xor_swap:mov eax, esicdqidiv ediretdiv_temp_swap:mov eax, esicdqidiv ediret编译器看穿了这两种交换方式。div_direct 是用 edi 除以 esi即 a / b。div_xor_swap 和 div_temp_swap 都是用 esi 除以 edi即 b / a。生成的代码完全相同——没有 XOR 指令没有临时变量也没有实际的交换操作。编译器只是跟踪哪个值在哪个寄存器中并相应地调整最终的除法操作。实际上对于几乎所有在局部变量上使用 XOR 交换技巧的情况编译器都能轻松识别出你在交换两个值并会重新安排后续操作以处理这种情况。XOR 交换技巧在这里并没有做编译器本身做不到的事情。用法 2通过指针交换那么编写一个真正的交换函数接受两个指针情况会怎样呢我们来试试两种方法cvoid swap_xor(int* a, int* b) {*a ^ *b;*b ^ *a;*a ^ *b;}void swap_temp(int* a, int* b) {int temp *a;*a *b;*b temp;}这里编译器不能简单地重新安排后续操作因为函数的目的就是进行交换。让我们看看生成的代码plaintextswap_xor:mov eax, dword ptr [rdi]xor eax, dword ptr [rsi]mov dword ptr [rdi], eaxxor eax, dword ptr [rsi]mov dword ptr [rsi], eaxxor dword ptr [rdi], eaxretswap_temp:mov eax, dword ptr [rdi]mov ecx, dword ptr [rsi]mov dword ptr [rdi], ecxmov dword ptr [rsi], eaxret使用临时变量的版本有 4 条指令完全符合预期将两个值加载到寄存器中然后以相反的顺序写回。一旦值在寄存器中交换操作基本上是免费的——我们只是将它们存储到相反的位置。XOR 版本有 6 条指令。它执行真正的 XOR 操作加载、存储和重新加载值。显然更差。所谓节省寄存器的说法也就不成立了。为什么编译器没有优化掉 XOR 交换对于局部变量编译器看穿了两种交换方式并生成了相同的代码。那么为什么在这里不这样做呢我们来考虑调用 swap_temp(x, x) 的情况即我们为两个参数传递相同的指针。函数将 *a 加载到 temp 中将 *b相同的值写入 *a然后将 temp原始值写回 *b。没有任何变化这正是我们对“自己和自己交换”的预期。现在考虑 swap_xor(x, x)。第一行 *a ^ *b 计算 x ^ x结果为 0。这个 0 被写回原始值就丢失了。当两个指针指向相同地址时XOR 交换技巧会“破坏数据”。这意味着这两个函数并不等价。编译器不能用一个函数替换另一个因为它们在指针别名的情况下表现不同。它必须忠实地发出 XOR 操作每次存储后都从内存中重新加载因为通过一个指针的每次写入都可能改变另一个指针看到的值。不过在 C 语言中我们可以使用 restrict 关键字告诉编译器两个指针永远不会别名cvoid swap_xor_restrict(int* restrict a, int* restrict b) {*a ^ *b;*b ^ *a;*a ^ *b;}使用 restrict 后我们保证 a 和 b 指向不同的内存。现在编译器知道不会出现别名的情况生成的代码如下plaintextswap_xor_restrict:mov eax, dword ptr [rsi]mov ecx, dword ptr [rdi]mov dword ptr [rsi], ecxmov dword ptr [rdi], eaxret我们又回到了 4 条指令——只有加载和存储操作看不到 XOR 指令。编译器将 XOR 交换优化成了与使用临时变量版本完全相同的代码。这个技巧再次没有带来任何好处。加法交换技巧怎么样XOR 不是唯一具有自反性、可以在不使用临时变量的情况下进行交换的操作。加法和减法也可以实现同样的功能ca a b;b a - b;a a - b;跟踪这个过程第 1 行执行后a 存储 a b。第 2 行执行后b 存储 (a b) - b即原始的 a。第 3 行执行后a 存储 (a b) - a即原始的 b。交换完成。但是对于有符号整数这非常糟糕。加法 a b 可能会溢出而在 C 语言中有符号整数溢出是未定义行为。所以这个技巧不仅毫无意义而且在形式上是错误的。不过在实际中它真的会出错吗我一直在尝试找出未定义行为会导致实际问题的情况但不太确定能否找到。编译器利用有符号溢出未定义行为的典型方式是在比较操作中——如果你写 i i 1编译器会假设这总是为真因为有符号溢出不会发生。但在加法交换技巧中我们从不将溢出的值与任何东西进行比较。我们只是进行加法和减法操作。编译器可能采取以下三种方式1. **局部变量**编译器会从代数上看穿交换操作并完全优化掉就像处理 XOR 交换一样。生成的代码中不会发生溢出。2. **没有 restrict 的指针**编译器会忠实地生成算术运算代码。在补码硬件所有硬件都是并且从 C23 开始是强制要求上溢出和回绕会相互抵消得到正确的结果。3. **代数简化**如果编译器利用无溢出假设进行简化会得到 b a_original 和 a b_original这是正确的交换结果。我能想到的每种情况对于这个特定模式都能得到正确答案。未定义行为是真实存在的你不应该依赖它但我无法构造出编译器为加法交换生成错误代码的情况。如果有人能做到我会非常感兴趣。如果你真的想也可以在浮点数上使用加法交换技巧。我们用 2.0 和 3.0 试试plaintexta 2.0, b 3.0a a b 5.0b a - b 5.0 - 3.0 2.0a a - b 5.0 - 2.0 3.0交换成功。但如果是 1.0 和 1e16 呢plaintexta 1.0, b