XOR变量交换如何工作？

Question

有人可以向我解释如何在没有临时变量的情况下对两个变量进行XOR交换吗？

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

我明白它做了什么，但是有人能引导我了解它是如何工作的逻辑吗？

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的 x xor x == 0 ，

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

由于任何x的 x xor 0 == x ，

y2 = x0
x2 = y0

交换已完成。

Answer 2

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

在我们拥有简单的单周期或多周期CPU的那一天，使用这个技巧避免昂贵的内存解除引用或将寄存器溢出到堆栈是更便宜的。但是，我们现在拥有带有大量管道的CPU。 P4的管道范围从他们的管道中有20到31个（或左右）阶段，读取和写入寄存器之间的任何依赖可能导致整个事情停滞。 xor交换在A和B之间有一些非常重的依赖关系，它们实际上并不重要，但在实践中会使管道停顿。停滞的管道会导致代码路径变慢，如果在内部循环中进行此交换，则移动速度会非常慢。

在一般实践中，当您使用temp变量进行交换时，编译器可以弄清楚您真正想要做什么，并且可以将其编译为单个XCHG指令。使用xor swap使编译器更难以猜测您的意图，因此更不可能正确地优化它。更不用说代码维护等了。

Answer 3

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

假设你从x = 11和y = 5开始 在二进制文件中（我将使用假设的4位机器），这里是x和y

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

现在对我来说，XOR是一个反转操作，做两次是镜像：

     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!

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

现在，通过了解 ^ 可以被认为是 + 或 ，可以更容易理解XOR技巧 - 。就像：

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

，所以：

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

Answer 5

为什么它起作用的原因是因为XOR不会丢失信息。如果你可以忽略溢出，你可以用普通的加法和减法做同样的事情。例如，如果变量对A，B最初包含值1,2，则可以像这样交换它们：

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

BTW有一个老技巧，用于在单个“指针”中编码双向链表。 假设你有一个地址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，依此类推。它同样适用于倒退。要沿列表运行，您需要保持指向两个连续块的指针。当然你会使用XOR代替加法/减法，所以你不必担心溢出。

您可以将其扩展为“链接网络”。如果你想玩得开心的话。

Answer 6

大多数人会使用临时变量交换两个变量x和y，如下所示：

tmp = x
x = y
y = tmp

这里有一个巧妙的编程技巧，可以在不需要temp的情况下交换两个值：

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

使用XOR交换两个变量的更多细节

  

在第1行，我们将x和y（使用XOR）结合起来得到这个＆＃8220; hybrid＆＃8221;然后我们将它存储在x中。 XOR是保存信息的好方法，因为您可以通过再次执行XOR来删除它。

     

在第2行。我们将y与杂交进行异或，取消所有y信息，只留下x。我们将这个结果保存回y，所以现在他们已经交换了。

     

在最后一行，x仍然具有混合值。我们再次使用y（现在使用x＆＃8217;原始值）对其进行异或运动以从混合中移除所有x的痕迹。这给我们留下了y，交换完成了！

---

  

计算机实际上有一个隐含的＆＃8220; temp＆＃8221;在将中间结果写回寄存器之前存储中间结果的变量。例如，如果将3添加到寄存器（在机器语言伪代码中）：

ADD 3 A // add 3 to register A

  

ALU（算术逻辑单元）实际上是执行指令3 + A的。它接受输入（3，A）并创建一个结果（3 + A），然后CPU将其存储回A＆＃8217的原始寄存器。因此，在得到最终答案之前，我们使用ALU作为临时临时空间。

     

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

     

因为我们不习惯考虑可怜的，被忽视的ALU，所以XOR交换看起来很神奇，因为它没有明确的临时变量。有些机器有一步交换XCHG指令来交换两个寄存器。

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

Answer 8

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

A＆＃8217; =一个XOR b（1）
B＆＃8217; = a＆＃8217; XOR b（2）
一个＆＃8221; = a＆＃8217; XOR b＆＃8217; （3）结果，

要理解 为什么 ，请先注意：

1. 只有当其中一个操作数为1且另一个为零时，XOR才会产生1;
2. XOR 可交换所以XOR b = b XOR a;
3. XOR是关联所以（一个XOR b）XOR c =一个XOR（b XOR c）;和
4. 一个XOR a = 0（这应该从 1 以上）

在步骤（1）之后，a的二进制表示仅在a和b具有相反位的位位置具有1位。即（ak = 1，bk = 0）或（ak = 0，bk = 1）。现在，当我们在步骤（2）中进行替换时，我们得到：

B＆＃8217; =（一个XOR b）XOR b
    = XOR（b XOR b），因为XOR是关联的
   由于上面的[4]，因此是一个XOR 0    = a由于XOR的定义（参见上面的 1 ）


现在我们可以替换为步骤（3）：


A＆＃8221; =（一个XOR b）XOR a
    =（b XOR a）XOR a因为XOR是可交换的     = B XOR（XOR a），因为XOR是关联的
    由于上面的[4]，因为= b XOR 0     =由于XOR的定义（参见上面的 1 ）


更多详细信息： 必要且充足

Answer 9

作为旁注，我几年前以交换整数的形式独立地重新发明了这个轮子：

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

（以上以难以阅读的方式提到），

完全相同的推理适用于xor互换：a ^ b ^ b = a和a ^ b ^ a = a。由于xor是可交换的，x ^ x = 0且x ^ 0 = x，因此很容易看到

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

和

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

希望这会有所帮助。这个解释已经给出了......但不是很清楚imo。