Most people would swap two variables x and y using a temporary variable, like this:
tmp = x
x = y
y = tmp
Here’s a neat programming trick to swap two values without needing a temp:
x = x xor y
y = x xor y
x = x xor y
Don’t believe me? Try it out – write in any initial value for x and y:
It almost seems like magic – the the same statement is repeated 3 times and voila – the values magically swap? Let’s take a closer look.
How it works
To understand this trick, break the statements into unique values:
x1 = x xor y
y1 = x1 xor y
x2 = x1 xor y1
According to our code, x2 should have y’s original value. Let’s work out the details for the last step:
x2 = x1 xor y1
x2 = x1 xor (x1 xor y) // replace y1
x2 = (x1 xor x1) xor y // regroup parenthesis - order does not matter for XOR
x2 = 0 xor y // a xor a => 0
x2 = y // 0 xor a => a; x2 now has y's original value
Wow – x2 really does equal y! The swap happened. Now let’s try it out for y1:
y1 = x1 xor y
y1 = (x xor y) xor y
y1 = x xor (y xor y)
y1 = x xor 0
y1 = x // y1 == x's original value
And tada the trick worked again. x2 and y1 have the swapped answers.
Intuitive Understanding
Ok, sure, the boolean algebra works out great — but that’s not satisfying. I want to understand it deep down and have it make sense, not be some artifact of the properties of XOR. Let’s take another look:
1: x = x xor y
2: y = x xor y
3: x = x xor y
On line 1 we combine x and y (using XOR) to get this “hybrid” and we store it back in x. XOR is a great way to save information, because you can remove it by doing an XOR again.
So, this is exactly what we do on line 2. We XOR the hybrid with y, which cancels out all the y information, leaving us only with x. We save this result back into y, so now they have swapped.
On the last line, x still has the hybrid value. We XOR it yet again with y (now with x’s original value) to remove all traces of x out of the hybrid. This leaves us with y, and the swap is complete!
Would you really use this?
No way. This is a cool trick, but don’t write this as an actual swap function. If you have to debug it in 6 months you’ll be in for some fun. Let me show you why:
Suppose x and y are pointers or references to objects, and both point to the same location. We’d expect our swapping function to just switch the values around, with no net change, right?
Well, take a look at what happens if we expand out line 1:
x = x xor y
x = x xor x // x and y are equal
x = 0
Wow! So x becomes 0 right at the get-go. That’s ok by itself, but because x and y are at the same location, we just made y zero as well! We’ve lost the original values, a problem known as aliasing: changing one variable has an indirect effect on another.
So, would you have caught this bug? I wouldn’t have, and it would have been a nightmare figuring out why an innocuous swap function was causing data loss. Cute tricks like these can be pretty dangerous. As Brian Kernighan said:
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
This applies so well here – we wrote the code pretty much as cleverly as we could :). So, treat this as an intellectual exercise that brings up a few points:
- XOR is a great way to combine information and later extract it. XOR-based encryption uses this technique. Also, XOR can combine N items together, not just 2.
- There are new ways to perform even the simplest operations.
Even more hairy details
Now, how does this work on a CPU-level?
The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example, if you add 3 to a register (in machine-language pseudocode):
ADD 3 A // add 3 to register A
The ALU (Arithmetic Logic Unit) is actually what executes the instruction 3+A. It takes the inputs (3,A) and creates a result (3 + A), which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer.
We take the ALU’s implicit temporary data for granted, but it’s always there. In a similar way, the ALU can return the intermediate result of the XOR in the case of x = x xor y, at which point the CPU stores it into x’s original register.
Because we aren’t used to thinking about the poor, neglected ALU, the XOR swap seems magical because it doesn’t have an explicit temporary variable. Some machines have a 1-step exchange XCHG instruction to swap two registers.
Further reading: