Static Zero

Swapping variables has always been a bit of an annoyance while programming. It doesn’t matter whether you code in C, Java, MIPS, or any other language, you’ve really only had one way to swap variables. Take, for example, the C function below. This is a pretty standard swap function:

void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}

So what does it do? Exactly what you would expect. Variable temp gets the value in x, then x gets the value in y, and finally y gets the value in temp. What does that accomplish? The variables have been swapped. (Try it if you don’t believe me.)

There is another solution to this problem that doesn’t use a temporary variable. It uses your programming language’s XOR operation to swap the variables, and I’ll show you how to do it below. (If you already know how to do this, this article isn’t written for you, sorry.) This trick can be very useful, especially on embedded systems or devices with very limited memory.

So how do we swap the variables without a temporary? Simple. XOR three times.

For anyone who doesn’t know, a xor a = 0 while a xor b = 1. If you have no idea what that means, here’s a simple truth table of the XOR operation:

|-------------XOR-------------|
|    a    |    b    |   xor   |
|    0    |    0    |    0    |
|    0    |    1    |    1    |
|    1    |    0    |    1    |
|    1    |    1    |    0    |
|-----------------------------|

You can perform an xor three times on two values, alternating overwriting a and b each time, and they will swap.
The pseudocode for an XOR swap is:

a = a XOR b
b = a XOR b
a = a XOR b

Let’s see how this actually works. Take a look at what would happen using the following 8-bit values.

a = 01011010
b = 11000110

First, a = a XOR b:
01011010
11000110
--------
a = 10011100 (by truth table)

Now, b = a XOR b
10011100
11000110
--------
b = 01011010 (by truth table) (look, it matches the old a)

Finally, a = a XOR b
10011100
01011010
--------
a = 11000110 (by truth table) (look, it matches the old b)

So there you go, xor two values three times (storing them correctly in between) and they’ll be swapped. This is very easy to implement. Here is the source for C and MIPS assembly. You should be able to slightly modify this to use it in whatever language you like.

C (swap function only; download complete working file at the end of this post):

/*
* Swap values pointed to by x and y
*/
void swap(int *x, int *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}

MIPS assembly (assume values are in $t0 and $t1):

# Swap values in $t0 and $t1
# only using XOR
xor $t0 $t0 $t1
xor $t1 $t0 $t1
xor $t0 $t0 $t1

That’s all there is to it. But before you go and change all the code you’ve ever written, there are a couple things you should know:

• Most compilers for higher-level languages will actually make this code slower than if you had done a swap using a temporary. Why? This code does three assignments and three operations, meaning at the very least, 6 cycles. Doing a swap using a temporary variable only does 3 assignments (no operations), meaning at least 3 cycles. Your compiler will probably take many more cycles than this for either type, but the xor swap will usually end up taking more cycles and therefore being slower.
• Many people will complain (rightfully or not, I don’t care. I am only presenting the material) that this code is much more unreadable, especially in higher level languages. Of course you know what it does because you coded it, but if someone else looks at your code they may have trouble deciphering what you were up to.

Good luck.

Want a full, working version? xor_swap.c