Blood Sugar Xor Magik

Last June in my computer architecture class I learned a neat little trick: how to swap two variables in place by xor'ing them together three times:

int x = 5, y = 7;
x = x ^ y;        // x = 2, y = 7
y = x ^ y;        // x = 2, y = 5
x = x ^ y;        // x = 7, y = 5

It was cool! And it bothered me, because what the #^$& is going on here? Who came up with this? I'm not a huge fan of tricks. I don't like to hear "it's weird but it just works." It's not like there are little math fairies living in the processor, sprinkling pixie dust on everything. I mean, probably not.

So I spent the next few weeks with this piece of trivia stuck in the back of my mind. Festering. Until one day (when my time really would have been better spent studying for the midterm) I decided to confront the mystery head on. I sat down with some paper and wrote out example after example, in binary, not thinking so much as seeing, just letting my eyes watch what happened with all the 1's and 0's.

And there it was.

The "trick" is that the first time you do the xor, you are temporarily storing aggregate information about the values of the two variables. With each bit, x now stores information about which of three possible outcomes occurred when we compared the original values at each position: either we saw two 0's, two 1's, or a 0 and a 1.

Then the following xor operations extract information from that aggregate.

First we look at y and the aggregate in order to recover the original x value. If the aggregate contains 0 in a particular position, we know the original values of x and y matched in that position, so x's bit was the same as whatever we have for y there. But if the aggregate contains 1, x's bit was the opposite of what y's is.

Since we can always disaggregate the information as long as we have one of the original values, we can go ahead and store the recovered, original value of x in y, completely throwing out the original value of y. Because we don't need it. We'll just turn around and compare the aggregate with original-x-current-y to get the original value of y back again in the next step. And then store that original y value in x.

And that's how our values get 100% non-magically swapped without using any temporary variables.

int x = 5, y = 7;
x = x ^ y;        // After assignment: x = aggregate,  y = original y
y = x ^ y;        // After assignment: x = aggregate,  y = original x
x = x ^ y;        // After assignment: x = original y, y = original x

Information is bits + context

All semester long (and since then, too) we kept returning to the idea that information is bits + context. Signed vs unsigned integers, the IEEE standard for floating-point representation, character encodings, structs, and on and on.

The xor "trick" gave me a deeper appreciation of why we emphasize bits-plus-context. What's happening here is that the context of x changes subtly with the first xor. It starts out representing a plain old integer, but then right off the bat it switches to an aggregate value whose meaning is logical, not arithmetic. Completely different semantics! This is a "type" that C doesn't define, and that we have no good English name for. Our inability to name it is what makes it seem like a trick.