XOR变量交换是如何工作的？

Question

有人能解释一下如何在没有临时变量的情况下使用异或交换两个变量吗？

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

我明白它做什么，但能有人为我解释一下它的工作原理吗？

- Simucal

---

我认为 XOR 变量交换在乱序执行内核上表现不佳。 每个后续的 XOR 都有一个读-写后依赖性，需要等待答案完成。 对于 x86，最好按正常方式编码。编译器应该会生成合适的代码。 - Calyth

Answer 1

通过进行替换操作，您可以看到它是如何工作的:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

替换操作，

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

由于 xor 完全满足结合律和交换律：

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

由于任何x的异或操作与自身的结果都是0，

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

由于对于任意x，x异或0 == x，

y2 = x0
x2 = y0

交换已完成。

- Greg Hewgill

---

我不知道您是不是会在11年后看到这条评论，但这是最好的解释，非常感谢！ - Cantaff0rd

接近12年后：这对于字符串操作（比如字符串反转）是如何工作的？这是因为你不是在ASCII值上进行操作，而是在保存字符串各个部分的内存地址的二进制表示上进行操作吗？ - bluppfisk

我几乎忍不住想把 y2 改成 y1。你用了 x0 和 x1，但是却用了 y0 和 y2，这让我感到有些不舒服。:-] - Frerich Raabe

Answer 2

其他人已经解释过了，现在我想解释一下为什么这原本是个好主意，但现在不再是。

回到以前我们使用简单的单周期或多周期CPU时，使用这个技巧可以避免昂贵的内存引用或将寄存器溢出到堆栈。然而，现在我们有了具有大规模流水线的CPU。P4的流水线阶段从20到31个不等，任何读写寄存器之间的依赖都可能导致整个流水线停顿。异或交换在A和B之间存在一些非常严重的依赖关系，实际上并不重要，但会导致流水线停顿。停顿的流水线会导致代码执行缓慢，如果这个交换在你的内部循环中，你的执行速度将会非常慢。

一般情况下，当你使用一个临时变量进行交换时，你的编译器可以推断出你真正想做的事情，并将其编译为一条单独的XCHG指令。使用异或交换会使编译器更难猜测你的意图，因此更不太可能正确地对其进行优化。更不用说代码维护等问题了。

- Patrick

---

是的 - 像所有节省内存的技巧一样，在这个廉价内存的时代，这并不是很有用。 - Bruce Alderman

同样地，然而，嵌入式系统的CPU仍然受益匪浅。 - Paul Nathan

@Paul，这取决于你的工具链。我建议先进行测试，确保你的嵌入式编译器没有已经执行了该优化。 - Patrick

值得注意的是，从尺寸角度来看，根据架构不同，三个XOR操作可能比一个XCHG操作更大。如果不使用XOR技巧，可以节省更多的空间。 - Patrick

Answer 3

我更喜欢以图形的方式而不是数字的方式来思考。

假设你从x=11和y=5开始（我将使用一个假想的4位机器），以下是它们的二进制表示：

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

对我来说，异或操作是一个反转操作，连续执行两次则相当于镜像：

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

- plinth

---

非常清晰。在每个位上执行XOR操作后，更容易理解正在发生的事情。我认为理解XOR更困难，因为与&和|操作不同，它更难在脑海中计算。XOR算术只会导致混乱。不要害怕将问题可视化。编译器在那里进行数学运算，而不是你自己。 - Martyn Shutt

Answer 4

以下这篇文章应该较易理解：

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

现在，我们可以更容易地理解异或技巧，因为我们知道 ^ 可以被看作是 + 或 -。就像这样：

x + y - ((x + y) - x) == x 

因此：

x ^ y ^ ((x ^ y) ^ x) == x

- Matt J

---

@Matt J，感谢减法示例。它确实帮助我理解了它。 - mmcdole

可能值得强调的是，由于大数溢出的问题，您不能使用加法或减法方法。 - MarkJ

这是真的吗？在我尝试的小例子中，无论如何都能正常工作（假设下溢或上溢的结果为（result％2 ^ n））。我可能会编写一些代码来测试它。 - Matt J

我认为，假设ADD和SUB指令以最简洁的硬件实现方式实现，即使存在溢出或下溢，这也可以正常工作。我刚刚测试过了。我有遗漏什么吗？ - Matt J

我想，如果你没有针对溢出和下溢的异常处理，那么它肯定可以工作。 - MarkJ

Answer 5

它能够工作的原因是因为异或运算不会丢失信息。如果你可以忽略溢出，你也可以通过普通的加减法来完成同样的事情。例如，如果变量对A,B最初包含值1,2，你可以像这样交换它们：

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

顺便说一下，有一个古老的技巧可以用单个“指针”编码双向链表。假设您有一个地址分别为A、B和C的内存块列表。每个块中的第一个单词分别是：

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

如果你能访问块A，它会给你B的地址。要到达C，你需要用B中的“指针”减去A，以此类推。反过来也一样有效。要沿着列表运行，你需要保留两个相邻块的指针。当然，你可以使用异或代替加法/减法，这样就不必担心溢出问题。如果你想要一些乐趣，可以将其扩展到“链接网络”。

- Mike Dunlavey

---

单指针技巧非常棒，我之前不知道这个！谢谢！ - Gab Royer

@Gab：不用谢，你的英语技能比我的法语好多了！ - Mike Dunlavey

对于 +/- 方法 +1（尽管int溢出是UB） - chux - Reinstate Monica

Answer 6

大多数人会使用临时变量来交换两个变量x和y的值，像这样：

tmp = x
x = y
y = tmp

这是一个巧妙的编程技巧，可以在不需要临时变量的情况下交换两个值:

a, b = b, a

x = x xor y
y = x xor y
x = x xor y

详见使用异或交换两个变量的方法

第一行中，我们使用异或操作将x和y组合在一起得到“混合值”，并将其存储回x中。异或是保存信息的好方法，因为您可以通过再次进行异或来删除它。

在第二行中，我们用y异或混合值，这会取消掉所有y的信息，只留下x。我们将此结果存回y中，现在它们已经交换了。

在最后一行中，x仍然具有混合值。我们再次用y（现在是x的原始值）进行异或操作，以将混合值中所有x的痕迹消除。这让我们只剩下y，交换完成！

---

计算机实际上有一个隐含的“临时”变量，它在将中间结果写回寄存器之前存储这些值。例如，如果您将3添加到寄存器中（在机器语言伪代码中）：

ADD 3 A // add 3 to register A

ALU（算术逻辑单元）实际上执行指令3 + A。它获取输入（3、A）并创建结果（3 + A），然后CPU将其存储回A的原始寄存器中。因此，在得到最终答案之前，我们将ALU用作临时刮擦空间。

我们认为ALU的隐式临时数据是理所当然的，但它总是存在的。类似地，对于x = x xor y情况下的XOR，ALU可以返回中间结果，此时CPU将其存储到x的原始寄存器中。

由于我们不习惯考虑可怜的、被忽视的ALU，所以XOR交换似乎有点神奇，因为它没有显式的临时变量。一些机器具有1步交换XCHG指令来交换两个寄存器。

- VonC

---

我理解，我在问它的工作原理。在一个值上使用异或运算符如何让你在不使用临时变量的情况下进行交换？ - mmcdole

点赞因为这是最清晰和最详细的答案，但要注意使用临时变量进行交换更易读，并因此在代码中具有更多价值。 - eyelidlessness

我喜欢原始答案（带解释），但关于ALU的部分似乎是误导性的。即使在你提到的单周期（非流水线）处理器上，能够在1个指令中执行“x =（涉及x的操作）”更多地与寄存器文件具有输入和输出端口有关。 - Matt J

Answer 7

@VonC 是正确的，这是一个巧妙的数学技巧。想象一下4位二进制数，看看这是否有助于理解。

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

- Kenny

Answer 8

XOR方法基本上有3个步骤：

a’ = a XOR b (1)
b’ = a’ XOR b (2)
a” = a’ XOR b’ (3)

为了理解为什么这个方法有效，首先需要注意以下几点:

1. XOR只在其操作数中恰好有一个为1时产生1；
2. XOR是可交换的，因此a XOR b = b XOR a；
3. XOR是可结合的，因此(a XOR b) XOR c = a XOR (b XOR c)；
4. a XOR a = 0（从上面的1中的定义应该很明显）。

在第一步之后，a的二进制表示将只在a和b具有对立位的位置上具有1位。即(ak=1, bk=0)或(ak=0, bk=1)。现在，当我们在第二步中进行替换时，我们得到：

b’ = (a XOR b) XOR b
= a XOR (b XOR b) 因为XOR是可结合的
= a XOR 0 根据[4]上面的定义
= a 根据XOR的定义（参见上面的1）

现在我们可以将其代入第三步：

a” = (a XOR b) XOR a
= (b XOR a) XOR a 因为XOR是可交换的
= b XOR (a XOR a) 因为XOR是可结合的
= b XOR 0 根据[4]上面的定义
= b 根据XOR的定义（参见上面的1）

更详细的信息请参阅这里： 必要和充分

-

Answer 9

作为一个旁注，我几年前独立发明了这个轮子，通过交换整数来实现：

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

上面提到的内容表述不够清晰。

同样的推理也适用于异或交换：a ^ b ^ b = a 和 a ^ b ^ a = a。由于异或是可交换的，x ^ x = 0 和 x ^ 0 = x，这很容易理解，因为

= a ^ b ^ b
= a ^ 0
= a

and

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

希望这可以帮助您。这个解释已经被提供了...但在我看来并不是很清楚。

- jheriko

---

这里晚了很多，但在 C 和（旧版本的）C++ 中，有符号整数溢出是未定义行为。为了“节省一些空间”而交换变量可能会引发 UB，这真是个糟糕的想法。 - Andrew Henle

Answer 10

我只是想加入一些数学解释，以使答案更完整。在群论中，XOR是一个阿贝尔群，也称为交换群。这意味着它满足五个要求：封闭性、结合性、单位元、逆元和交换律。

XOR交换公式:

a = a XOR b
b = a XOR b
a = a XOR b 

扩展公式，用先前的公式替换a、b：

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

可交换性意味着"a XOR b"等于"b XOR a":

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b

结合律指的是"(a XOR b) XOR c"等同于"a XOR (b XOR c)"：

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b)

在 XOR 中，它的反元素是它本身，这意味着任何值与其自身进行 XOR 操作都将得到零。

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0

在异或运算中，零是其恒等元素，这意味着任何值与零进行异或运算都会保持不变：

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0 
            = a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0 
            = b XOR 0
            = b

你可以在群论中获取更多信息。

- Sungfu Chiu