language-agnostic - XOR 变量交换如何工作？

Question

有人可以向我解释如何在没有临时变量的情况下异或交换两个变量吗？

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

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

Answer 1

您可以通过替换来了解它是如何工作的:

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)

因为异或是完全结合和可交换的:

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

交换完成。