Swap two variables using XOR

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.

9 Comments »

Trackbacks & Pingbacks

Pingback by Why is C++ very popular for Game Development? - Page 2 - The ProgrammersTalk Community — July 11, 2007 @ 9:19 pm
Pingback by xor swap « Blog do Lameiro — December 7, 2007 @ 8:09 pm

Comments

Note that in portable C (that is, according to, say, the 1999 C standard), this only works for unsigned integral types. Obviously it won’t work for floating point or pointer or struct/union types. (Portably — if you don’t care about machine-specific code, you could convert pointers to integers on many platforms and it’ll just do what you want. But it’s not guaranteed to work everywhere.)

But also, under some (rare, but allowed) non-2s-complement signed integer representations, an xor might result in a “negative zero” that can be converted to a normal zero before continuing, resulting in the wrong sign bit setting on an output value…

Ken — April 2, 2007 @ 12:18 am
Wow, thanks for the details Ken! Yeah, I imagine there are all sorts of nasty side effects when using a trick like this. Appreciate the background info.

Kalid — April 6, 2007 @ 12:09 pm
Hi! I think the following note will be helpful, since it highlights the properties involved in all these swappings:

http://www.cs.nott.ac.uk/~jff/papers/JFFs/JFF1.pdf

Joao F. Ferreira — June 15, 2007 @ 8:13 am
Thanks Joao, that paper is pretty interesting.

Kalid — June 15, 2007 @ 12:04 pm
Kalid,

I’ve just published a new version of my note on this. You can find it at:

http://www.joaoferreira.org/2007/07/11/swapping-the-values-of-two-variables/

Joao Ferreira — July 11, 2007 @ 8:12 am
there is another way, tho i doubt if it’s faster,

a=10;
b=15;

a=a+b;//a=25 b=15
b=a-b; //a=25 b=10
a=a-b; //a=15 b=10, swapped

zezima — November 27, 2007 @ 8:11 pm
Hi zezima, thanks for the info! That’s a neat trick too — you “combine” a and b in a similar way, and extract them as well.

One thing to watch out for is arithmetic overflow.

Kalid — November 27, 2007 @ 8:21 pm

RSS feed for comments on this post. TrackBack URI

Have a question? Know an explanation that caused your own a-ha moment? Write about it here.