XOR变量交换是如何工作的？
XOR变量交换是如何工作的？
提问于 2008-10-30 06:37:58
有人能给我解释一下没有temp变量的两个变量的XOR交换是如何工作的吗？
void xorSwap (int *x, int *y)
{
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}我知道它是做什么的，但是有人能告诉我它是如何工作的吗？
回答 8
Stack Overflow用户
回答已采纳
发布于 2008-10-30 06:45:45
您可以通过执行替换来查看它是如何工作的：
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交换就完成了。
Stack Overflow用户
发布于 2008-10-30 07:15:40
其他人已经解释过了，现在我想解释一下为什么这是一个好主意，但现在不是。
在我们有简单的单周期或多周期CPU的日子里，使用这种技巧来避免代价高昂的内存解除引用或将寄存器溢出到堆栈的成本更低。然而，我们现在有了具有大量管道的CPU。P4的流水线在其流水线中有20到31个(或更多)阶段，在这些阶段中，读取和写入寄存器之间的任何依赖都可能导致整个过程停滞。xor交换在A和B之间有一些非常严重的依赖，这些依赖实际上根本无关紧要，但实际上会使管道停滞不前。停滞的流水线会导致代码路径变慢，如果这个交换发生在你的内部循环中，那么你的速度将会非常慢。
在一般情况下，当您使用temp变量进行交换时，编译器可以找出您真正想要做的事情，并可以将其编译为一条XCHG指令。使用xor交换使得编译器更难猜测您的意图，因此不太可能正确地优化它。更不用说代码维护等了。
Stack Overflow用户
发布于 2009-02-09 16:51:39
我喜欢用图形而不是数字来思考它。
假设您从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!页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/249423
复制相关文章
相似问题