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
|a||b||a ⊕ b|
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
b's bits were
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
] denote bit values).
Essentially, the magic going on is actually just mathematics. The first time we reassign
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
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?
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.