The XOR swap (Programming hacks)

Okay, it is a well-known (and not a very useful) trick, but I must write about it because I’ve never heard about before, and it seems like some kind of magic. Each programmer knows that if he want to swap two variables then he needs to use a third, temporary variable (or temp variable), which stores the value of the first variable while you copy the content of the second variable into the first variable. It is the general case, it works for strings, objects, it works for anything:

void swap(Something& a, Something& b) {
  Something temp;
  temp = a;
  a = b;
  b = temp;
}

I remember I was thirteen when I read first time about this technique. I found it in an old Hungarian Commodore64 programming book and this book had a chapter about sorting algorithms like selection sort, insertion sort, bubble sort and quicksort. (The details about the famous radix sort in linear time wasn’t written, just a short reference to that.) Examine the picture below!

Figure 1: The good old swap algorithm from a Hungarian book, highlighted in green. (Hartányi-Lengyel-Obádovics-Reményi: Számítástechnika C64, 1989)

It was pretty interesting. Later, I learnt that swap is a cool technique when you want to develop exception-safe C++ applications (see copy-and-swap), so swap and me became the best friends. And up until yesterday, I’ve thought it is a such easy story. Yesterday I’ve been looking for job interview questions, and I’ve founded something very interesting.

Write a C program to swap two variables without using a temporary variable.

I never thought that swap is possible without a temp variable. It is the so-called xor swap algorithm, it has also a page on the Wikipedia. Strange, but this method isn’t based on xor or addition-subtraction, it is based on group theory. Let S be a set of elements, let f(s,t) be a function and let s,t be elements of S. Suppose (S, f) is an abelian group and g is the inverse function of f in this group. The key idea, that g(f(s,t),t) = s and g(f(s,t),s) = t are always true. (These equations are simple, the definition of the inverse function and the commuativity were used. g(f(s,t), s) = t true iff the group is commutative, examine the equations g(f(s,t),s)=g(f(t,s),s) and f(s,t)=f(t,s)!) In other words, we can combine the values of s and t with the function f and we can extract the s from the combined value with g and t. Here is the pseudocode:

void swap(Something& s, Something& t) {
  t = f(s,t); //combined value
  s = g(t,s); //combined value unlocked with s, the result is t
  t = g(t,s); //combined value unlocked with t, the result is s
}

It seems cool, doesn’t? (Z,+) and (Z, xor) are abelian groups (Z is the set of integers), in the xor case, f = g = xor, which makes the xor swap more attractive. (Z, and) is not an abelian group, because N and 0 is always 0. There are only two binary connectives that are appropriate to construct a tricky swap functions, the xor and the logical biconditional (== NXOR).

(Okay, there is a small cheat in the last paragraph. Instead of Z we must use a cyclic set, because a 64 bit integer variable cannot store any possible integer values …)

Advertisements

About vrichard86

I'm Richard and I'm an enthusiastic coder. I want to be better and I think a professional journal is a great self improvement tool. Welcome to my blog, to my hq, to my home on the web!
This entry was posted in Hacks and tagged , , , . Bookmark the permalink.