How does XOR variable swapping work?

Question

Can someone explain to me how XOR swapping of two variables with no temp variable works?

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

I understand WHAT it does, but can someone walk me through the logic of how it works?

Answer 1

You can see how it works by doing the substitution:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Substituting,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Because xor is fully associative and commutative:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Since x xor x == 0 for any x,

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

And since x xor 0 == x for any x,

y2 = x0
x2 = y0

And the swap is done.