XOR变量交换如何工作？

Question

XOR变量交换如何工作？有人可以向我解释如何在没有临时变量的情况下对两个变量进行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 xor x == 0任何x，

y2 = x0 xor 0

x2 = 0 xor 0 xor y0

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

y2 = x0

x2 = y0

交换完成了。

Answer 2

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

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

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