异或变量交换是如何工作的？

有人能解释一下两个变量的异或交换没有临时变量是如何工作的吗？

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

我知道它是做什么的，但是谁能告诉我它是如何工作的？

25627 次浏览
小开

大多数人会用一个临时变量交换两个变量 x 和 y，像这样:

tmp = x
x = y
y = tmp

这里有一个简单的编程技巧，可以在不需要临时值的情况下交换两个值:

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

详情请参阅 使用异或交换两个变量

在第1行，我们组合 x 和 y (使用 XOR)来得到这个“混合”，并将它存储回 x 中。 XOR 是保存信息的一个很好的方法，因为您可以通过再次执行 XOR 来删除它。

在2号线。我们把混合物与 y 异或，这样就抵消了所有的 y 信息，只剩下 x。我们把这个结果保存回 y 中，所以现在它们已经交换了。

在最后一行，x 仍然有混合值。我们再次用 y (现在用 x 的原始值)进行 XOR，以消除混合物中 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 指令来交换两个寄存器。

小开
最佳答案

你可以通过替换看到它是如何工作的:

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开始,

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

因为 x xor 0 == x对任何 x,

y2 = x0
x2 = y0

交换完成了。

小开

下面是一个稍微容易理解的方法:

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

现在，通过理解 ^可以被认为是 + 或者 -，我们可以更容易地理解异或技巧。正如:

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

所以:

x ^ y ^ ((x ^ y) ^ x) == x
小开

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

回到我们使用简单的单周期或多周期 CPU 的时代，使用这种技巧来避免代价高昂的内存解引用或将寄存器溢出到堆栈中会更加便宜。然而，我们现在有了带有大量管道的 CPU。P4的管道在其管道中有20到31个(大约)阶段，在这些阶段中，对寄存器的读取和写入之间的任何依赖都可能导致整个事件停止。Xor 交换在 A 和 B 之间有一些非常严重的依赖关系，这些依赖关系实际上根本不重要，只会在实际中阻碍管道的运行。停滞的管道会导致代码路径变慢，如果这个交换位置在内部循环中，那么移动将会非常缓慢。

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

小开

@ 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
小开

异或方法基本上有三个步骤:

A’= a XOR b (1)
B’= a’XOR b (2)
A”= a’XOR b’(3) < br >

要理解 为什么，首先要注意:

  1. 只有当 XOR 的操作数之一为1，而另一个操作数为零时，XOR 才会产生1;
  2. XOR 是 交换，所以 a XOR b = b XOR a;
  3. XOR 是 联想，所以(a XOR b) XOR c = a XOR (b XOR c) ; 和
  4. A XOR a = 0(从上面的 1中的定义可以明显看出这一点)

在步骤(1)之后，a 的二进制表示只在 a 和 b 有相对位的位位置有1位。也就是(ak = 1，bk = 0)或者(ak = 0，bk = 1)。现在，当我们在步骤(2)中进行替换时，我们得到:

B’= (a XOR b) XOR b
= a XOR (b XOR b) ，因为 XOR 是结合的
= a XOR 0，因为上面的[4]
= a 由于 XOR 的定义(见上面的 1) < br >

现在我们可以用步骤(3)代替:

A“ = (a XOR b) XOR a
= (b XOR a) XOR a 因为 XOR 是可交换的
= b XOR (a XOR a) ，因为 XOR 是结合的
= b XOR 0，因为上面的[4]
= b 由于 XOR 的定义(见上面的 1) < br >

更多详情请浏览此处: 必要且足够

小开

它之所以能够工作是因为 XOR 不会丢失信息。如果可以忽略溢出，那么可以对普通的加减法做同样的事情。例如，如果变量对 A，B 最初包含值1,2，您可以像下面这样交换它们:

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

顺便说一下，在单个“指针”中编码双向链表有一个老技巧。 假设您有一个位于地址 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 代替加法/减法，因此不必担心溢出。

如果你想找点乐子，你可以把它扩展到“链接网络”。

小开

顺便说一句，我在几年前独立地重新发明了这个轮子，以交换整数的形式，方法是:

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

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

小开

我喜欢用图形来表示，而不是用数字来表示。

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

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

现在对我来说，异或是一个反向操作，做两次就是一个镜像:

     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!
小开

我只是想增加一个数学解释，使答案更加完整。在 abc0中，XOR 是一个 阿贝尔集团阿贝尔集团，也称为阿贝尔群。这意味着它满足五个要求: 闭包性、结合性、等式元素、逆元素、交换性。

异或交换公式:

a = a XOR b
b = a XOR b
a = a XOR b

展开公式，用前面的公式替换 a，b:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

交换意味着“ a XOR b”等于“ b XOR a”:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b

结合性意味着“(a XOR b) XOR c”等于“ a XOR (b XOR c)”:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)

XOR 中的逆元素就是它自己，这意味着任何与它相关的值都是零:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
= a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)
= b XOR 0 XOR 0

XOR 中的单位元素是零，这意味着任何值为零的 XOR 都保持不变:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
= a XOR (b XOR b)
= a XOR 0
= a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b
= (b XOR a) XOR (a XOR b) XOR b
= b XOR (a XOR a) XOR (b XOR b)
= b XOR 0 XOR 0
= b XOR 0
= b

你可以在 群论中获得更多的信息。

小开

其他人已经发表了解释，但我认为，如果它伴随着一个好的例子，将更好地理解。

真相表

如果我们考虑上面的真值表，取值 A = 1100和 B = 0101，我们可以交换这样的值:

A = 1100
B = 0101




A ^= B;     => A = 1100 XOR 0101
(A = 1001)


B ^= A;     => B = 0101 XOR 1001
(B = 1100)


A ^= B;     => A = 1001 XOR 1100
(A = 0101)




A = 0101
B = 1100

提交答案