Puzzle 2

Let’s examine how to swap things.

We all remember learning swapping from cs1 when we were learning some type of sorting algorithm - swapping allowed us to sort arrays in place (constant space) rather than constructing a new array.

It goes something like the following:

int temp = array[0];
array[0] = array[1];
array[1] = temp;

Boom-eth! Thou art impressed with my swapping-eth of array positions 0 and 1.

Hmm. As it turns out, I’m not impressed. Not at all. What if I don’t want to use these intermediary variables like temp? After all, if you needed to use extra memory, is it really in place?

How would you do this without that variable?

If you guessed bit-wise operations, you’d be right. In this case, we’ll use the exclusive-or (xor) operator ^.

Xor has two key properties:

  1. Anything xor-ed with 0 is itself

  2. Anything xor-ed with itself is 0.

So how would we do it?

int a = 5;
int b = 4;

b ^= a;
a ^= b;
b ^= a;

Huh? That’s it? Yes, that’s it. Let’s take a look as to what’s going on here.

b ^= a expands to b = b ^ a. So now b = 4 ^ 5, and a = 5.

The second statement a = a ^ b expands to a = 5 ^ 4 ^ 5. Using the above two properties, that simpliefies down to a = 4 ^ 5 ^ 5 = 4 ^ 0 = 4. So now, a = 4.

The final statement then simplifies to b = 4 ^ 5 ^ 4 = 5 ^ 0 = 5.

And we’ve successfully swapped the two integers!