XOR变量交换如何工作？

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

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

我明白它做了什么,但有人可以告诉我它是如何工作的逻辑吗？

1> Greg Hewgill..：

---

您可以通过替换来了解它的工作原理:

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 xor x == 0任何x,

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

而且因为x xor 0 == x任何x,

y2 = x0
x2 = y0

交换完成了.

2> Patrick..：

---

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

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

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

3> plinth..：

---

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

假设你从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!

4> Matt J..：

---

这是一个应该稍微容易理解的:

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

---

可能值得强调的是,由于大数字溢出,您无法使用加法或减法方法.

5> Mike Dunlave..：

---

它为何起作用的原因是因为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代替加法/减法,所以你不必担心溢出.

如果你想获得一些乐趣,可以将其扩展为"链接网络".

6> VonC..：

---

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

tmp = x
x = y
y = tmp

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

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

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

在第1行,我们将x和y(使用XOR)结合起来得到这个"混合",我们将它存储在x中.XOR是保存信息的好方法,因为您可以通过再次执行XOR来删除它.

在第2行.我们将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 x或y的情况下,ALU可以返回XOR的中间结果,此时CPU将其存储到x的原始寄存器中.

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

---

我明白了,我问它是如何运作的.如何使用独占或值允许您在没有临时变量的情况下交换它

7> kenny..：

---

@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

8> 小智..：

---

基本上,XOR方法有3个步骤:

a'= a XOR b(1)
b'= a'XOR b(2)
a"= a'XOR b'(3)

要理解为什么这有效,请首先注意:

只有当其中一个操作数为1时,XOR才会产生1,而另一个为零;

XOR是可交换的,因此XOR b = b XOR a;

XOR是关联的,因此(一个XOR b)XOR c =一个XOR(b XOR c); 和

一个XOR a = 0(从上面1中的定义可以看出这一点)

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

b'=(a XOR b)XOR b
=一个XOR(b XOR b),因为XOR是关联的
=一个XOR 0,因为上面的[4]
= a由于XOR的定义(参见上面的1)

现在我们可以替换为步骤(3):

a"=(a XOR b)XOR a
=(b XOR a)XOR a因为XOR是可交换的
= b XOR(XOR a)因为XOR是关联的
= b XOR 0因为上面的[4]
= b由于定义异或(见上文1)

更详细的信息: 必要且充分