Favorite Algorithms: Swapping Data Cells without Using Extra Memory

Favorite Algorithms: Swapping Data Cells without Using Extra Memory

We all know that the most typical way to swap data stored in two different variables involves using a temporary variable to store information:

// our initial values
let a = 4;
let b = 6;

// swap the values by using a temporary variable
let temp = a;
a = b;
b = temp;

// see that the values were swapped
console.log(a); // --> 6
console.log(b); // --> 4

That's all fine and dandy, but let's say for some reason you were in a situation that you could not use any extra memory. How would you do it?

XOR, the magic function of the bitwise operators

Before I get to the application, I think it would be wise to review how the XOR function works, since not everyone uses it in their day to day programming. (If you already know how XOR works, go ahead and skip to the next section, or read this part anyway. Do whatever you want, I don't care.)

XOR is a bitwise function that answers to the following.

Given bits a and b: return true if a does not equal b, else return false  
aba ⊕ b
000
011
101
110

The term bitwise means that the XOR function is applied across each of the individual bits of its arguments in parallel. Meaning that if a's bits were 101 and b's bits were 011, then a ⊕ b = 110.

Harness the magic of the XOR to swap data

I keep using the term magic. That's because the first time I saw this, that's how it seemed to me. If you've never seen this before, be prepared to have your mind blown as well!

One of the most interesting properties about the XOR is that anything that is XOR'd to itself is always zero (a ⊕ a = 0). This is called the Self-inverse Property. Keep this in mind as you walk through each line of code and read the comments (note that the things between [ and ] denote bit values).

// our initial values, same as before
let a = 4; // [ 1 0 0 ]
let b = 6; // [ 1 1 0 ]

// swap the values by using three XOR's (the '^' operator in JavaScript)
a = a ^ b; // a is now [ 0 1 0 ]
b = a ^ b; // b is now [ 1 0 0 ]
a = a ^ b; // a is now [ 1 1 0 ]

// see that the values were swapped, because of witch craft
console.log(a); // --> 6
console.log(b); // --> 4

Essentially, the magic going on is actually just mathematics. The first time we reassign a with a ⊕ b, we are essentially establishing a parity signature of the two values. We can then exploit the Self-inverse Property to cancel out the parts of that signature we don't want. If we do that in a clever way, then we get the above results and successfully swap data without the use of another variable.


Notes about using this method

Don't

Despite this being once of the coolest things in Computer Science, just don't use it in your work. Most of your coworkers won't care for the fancy math, especially since you'd be hard pressed to find a real situation that you can't just use another temp variable. Memory is cheap, and the number of instructions is exactly the same on your processor as doing it the traditional way.

Why'd I tell you about this then?

According to the NFL Theorem, this algorithm is useful somewhere. Even if it is not, the reason I wrote up this article is for mental exercise. Maybe you will never use this, but I hope you saw that even in the most trivial of situations there are alternative solutions to solving the same problem. And that's a good enough reason for us to talk about it.

Well you think it's awesome so who's gonna stop you from using it?

Probably JavaScript. Though my example above works great, it only works if both variables are numbers because of how the language handles Objects. Play around, give it a shot and you'll quickly see what I mean.

If you use a bare bones language like C++ – or even better, x86-64 – then you can always use this method to swap pointers to anything, which is pretty nice.