XOR变量交换如何工作?
有人可以向我解释如何在没有临时变量的情况下交换两个变量的作用?
void xorSwap (int *x, int *y)
{
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
我明白它做了什么,但是有人能通过它如何工作的逻辑来引导我?
你可以通过替换来看看它是如何工作的:
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
x,
y2 = x0
x2 = y0
交换完成。
其他人已经解释过,现在我想解释为什么这是一个好主意,但现在不是。
早在我们使用简单的单周期或多周期CPU时,使用这种技巧便宜得多,以避免代价高昂的内存失效或将寄存器溢出到堆栈。 但是,我们现在拥有拥有大量管道的CPU。 P4的管道范围从他们管道中的20到31个(或多个)阶段,在这些阶段中,读写寄存器之间的任何依赖可能导致整个事件停滞。 xor swap在A和B之间有一些非常重要的依赖关系,实际上根本没有关系,但是在实践中会拖延管道。 停滞的管道会导致代码路径变慢,如果这个交换在你的内部循环中,你将会非常缓慢地移动。
在一般情况下,编译器可以确定当你使用temp变量进行交换时你真正想要做什么,并且可以将它编译为单个XCHG指令。 使用xor swap会使编译器难以猜测您的意图,因此不太可能正确地对其进行优化。 更不用说代码维护等了。
我喜欢用图形而不是数字来思考它。
假设你以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!
链接地址: http://www.djcxy.com/p/9979.html