Swapping Values Without a Temp Variable

It’s been a long time since I’ve done any C programming (the only C I ever really did was in school 10+ years ago) and I’ve never done it outside of school. I figure since I look at and study languages that are pretty esoteric, it’s only fair to throw in a language that is really widely used. It should make my Objective-C better (which probably isn’t saying much). It also gives me a chance to go “a little closer to the metal” I guess. Hey look, a Bus Error!

Anyway, one of the things that I love/hate about C are the little tricks that people often use. Sometimes they’re really fun but often they take a bit of thinking to understand if you’re not familiar with them. One of those that I ran across again was swapping values without a temp variable.

How Normal People Swap Values

The simplest way of swapping two values is ususally accomplished using a temp variable to hold one of the values for a moment.

int a = 2;
int b = 5;
int temp = 0;
 
temp = a;
a = b;
b = temp;

And Another Way

But you can accomplish the same thing using an Exclusive Or (XOR) operation.

To review bitwise operations:

& AND
  0101 (5)
  1100 (12) 
  ----
& 0100 (4)

| OR
  0101 (5)
  1100 (12) 
  ----
| 1101 (13)

^ XOR
  0101 (5)
  1100 (12) 
  ----
| 1001 (9)

The ^= just combines the XOR with an Assignment.

int a = 2;
int b = 5;
 
a ^= b;
b ^= a;
a ^= b;

Now isn’t that totally intuitive? Yeah, not to me either. Technically once you know this piece of trivia, you don’t really need to think about it. You’ll just recognize the pattern and understand what’s going on. But understanding why it works is probably a good thing.

So, I just came up with an example that shows what’s happening:

int a = 2;  // 0010
int b = 5;  // 0101
 
a ^= b;     // 0111 = 0010 ^ 0101
b ^= a;     // 0010 = 0101 ^ 0111
a ^= b;     // 0101 = 0111 ^ 0010

What are some of the principles in why this works?:

a ^ b == b ^ a

XOR is a reversible binary operation.

a = a ^ b  // now a is some other value
b = a ^ b  // now b is the original value of a
a = a ^ b  // now a is the original value of b

This isn’t a proof of any sort, but hopefully it will help you understand why it actually works. If you want even more of an explanation, and a proof, check out the article on Wikipedia: XOR Swap Algorithm