80

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

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

我了解它的作用，但是有人可以引导我了解它的工作原理吗？

4

11 回答 11

135

您可以通过替换来查看它是如何工作的：

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

并且交换完成。

于 2008-10-30T06:45:44.777 回答
98

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

早在我们拥有简单的单周期或多周期 CPU 的那一天，使用这个技巧来避免代价高昂的内存取消引用或将寄存器溢出到堆栈中会更便宜。但是，我们现在拥有具有大量流水线的 CPU。P4 的流水线在其流水线中有 20 到 31 个（左右）级，其中读取和写入寄存器之间的任何依赖都可能导致整个事情停止。xor 交换在 A 和 B 之间有一些非常重的依赖关系，这些依赖关系实际上根本不重要，但实际上会使管道停滞。停滞的管道会导致代码路径变慢，如果此交换位于您的内部循环中，那么您的移动速度将非常缓慢。

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

于 2008-10-30T07:15:39.600 回答
57

我喜欢用图形而不是数字来思考它。

假设您从 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!
于 2009-02-09T16:51:38.630 回答
36

这是一个应该更容易理解的一个：

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
于 2008-10-30T06:50:43.880 回答
14

大多数人会使用临时变量交换两个变量 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，交换完成！

计算机实际上有一个隐含的“temp”变量，它在将中间结果写回寄存器之前存储它们。例如，如果将 3 添加到寄存器（在机器语言伪代码中）：

ADD 3 A // add 3 to register A

ALU（算术逻辑单元）实际上是执行指令 3+A 的部分。它接受输入 (3,A) 并创建一个结果 (3 + A)，然后 CPU 将其存储回 A 的原始寄存器。因此，在得到最终答案之前，我们将 ALU 用作临时暂存空间。

我们认为 ALU 的隐式临时数据是理所当然的，但它始终存在。类似地，ALU 可以在 x = x xor y 的情况下返回 XOR 的中间结果，此时 CPU 将其存储到 x 的原始寄存器中。

因为我们不习惯考虑可怜的、被忽视的 ALU，所以 XOR 交换看起来很神奇，因为它没有显式的临时变量。有些机器有一个 1 步交换 XCHG 指令来交换两个寄存器。

于 2008-10-30T06:40:07.583 回答
14

它起作用的原因是因为 XOR 不会丢失信息。如果你可以忽略溢出，你可以用普通的加法和减法做同样的事情。例如，如果变量对 A,B 最初包含值 1,2，您可以像这样交换它们：

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

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

如果您想玩得开心，可以将其扩展到“链接网络”。

于 2009-02-09T15:25:31.177 回答
7

@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
于 2008-10-30T08:16:56.933 回答
5

XOR方法基本上有3个步骤：

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

要了解为什么这样做，首先要注意：

  1. 只有当其中一个操作数恰好为 1 且另一个为 0 时，异或才会产生 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）

现在我们可以代入步骤（3）：

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

此处提供更多详细信息： 必要和充分

于 2009-01-05T11:16:13.320 回答
3

作为旁注，几年前我以交换整数的形式独立地重新发明了这个轮子，方法是：

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

（上面以一种难以阅读的方式提到了这一点），

完全相同的推理也适用于异或交换：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

希望这可以帮助。这个解释已经给出了......但不是很清楚imo。

于 2009-02-09T16:32:51.467 回答
3

我只是想添加一个数学解释，以使答案更完整。在群论中，异或是一个阿贝尔群，也称为交换群。这意味着它满足五个要求：闭包、关联性、标识元素、逆元素、交换性。

异或交换公式：

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 中的逆元素是自身，这意味着任何值与自身 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

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

于 2020-04-20T13:38:46.197 回答
0

其他人已经发布了解释，但我认为如果它带有一个很好的例子会更好地理解。

异或真值表

如果我们考虑上面的真值表并取值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
于 2021-01-05T15:37:24.350 回答