Massive Algorithms: XOR swap algorithm - Wikipedia, the free encyclopedia

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

Number Swapper: Write a function to swap a number in place (that is, without temporary variables).

1 // Example for a= 101 (in binary) and b = 110

2 a = a ^ b; // a 101A110 011

3 b = a ^ b; // b = 011A110 = 101

4 a = a ^ b; //a = 011A101 = 110

This code works by using XORs. The easiest way to see how this works is by focusing on a specific bit. If we

can correctly swap two bits, then we know the entire operation works correctly.

Let's take two bits, x and y, and walk through this line by line.

1. x = x ^ y

This line essentially checks if x and y have different values. It will result in 1 if and only if x ! = y.

2. y = X ^ y

Or:y = {0 if originally same, 1 if different} A {original y}

Observe that XORing a bit with 1 always flips the bit, whereas XO Ring with O will never change it.

Therefore, if we do y = 1 A { original y} when x ! = y, then y will be flipped and therefore have

x's original value.

Otherwise,ifx == y,then we doy = 0 A {original y}and the value ofy does notchange.

Either way, y will be equal to the original value of x.

3. X = X A Y

Or:x {0 if originally same, 1 if different}" {original x}

At this point, y is equal to the original value of x. This line is essentially equivalent to the line above it,

but for different variables.

If we do x 1 A { original x} when the values are different, x will be flipped.

If we do x = 0 " { original x} when the values are the same, x will not be changed.

This operation happens for each bit. Since it correctly swaps each bit, it will correctly swap the entire number

Labels