logo标签列表

XOR变量交换是如何工作的？

language-agnosticbit-manipulationxor
86

有人能解释一下如何在没有临时变量的情况下使用异或交换两个变量吗？

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

我明白它做什么，但能有人为我解释一下它的工作原理吗？

10
我认为 XOR 变量交换在乱序执行内核上表现不佳。 每个后续的 XOR 都有一个读-写后依赖性，需要等待答案完成。 对于 x86，最好按正常方式编码。编译器应该会生成合适的代码。 - Calyth
12个回答
0

其他人已经发表了解释，但我认为如果有一个好的例子来说明会更容易理解。

XOR 真值表

如果我们考虑上面的真值表，并取值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
0

我知道这个问题已经被问了很长时间，也有很多答案。不过，我有自己的“语言”技巧来理解位运算的奇妙之处。也许对某些人会很有用。

XOR（异或）只有在其两个操作数中有一个是1且另一个是0时才会产生1。因此，XOR 是两个数字之间的差异。

  1. 通过 *x ^= *y; 我们将这个差异存储在 x 中。
  2. 如果我们知道第二个数字和 x 与 y 的差异，那么我们可以通过 *y ^= *x; 找出第一个数字。
  3. 如果我们知道 x 与 y 的差异，并且我们知道第一个数字，那么我们可以通过 *x ^= *y; 找出第二个数字。

我翻译成英文有些困难，所以我会添加一个图形表示：

x = First number;
y = Second number;

After *x ^= *y
x = Difference between first and second number
y = Second number

After *y ^= *x
x = Difference between first and second number
y = First Number

After *x ^= *y
x = Second number
y = First number

我使用这个工具，因为我不想在脑海中尝试想象很多数字。这就是为什么我的答案中没有数字表示。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接