Archive for January, 2009

Swap with out the tmp

Tuesday, January 27th, 2009

When swapping variables most people use

tmp = a
a = b
b = tmp

This requires using an extra variable tmp to store A while it is overwritten with b.  Wouldn’t it be great if you could swap the two without using an extra variable?  The XOR swap algorithm is just what you need

a^=b^=a^=b

This ends up with A and B swapped.  Still 3 assignments but with out the extra variable.  If you want a good explaination of how that works read the wikipedia article.

A word of warning though, the above code only works in C/C++.   It will not work in an VM language like Java or .NET.    This has to do with how the languages are implemented.  Java and .NET are stack based VMs where as C/C++ is register based (and not a VM).  This means that values are pushed onto the stack and then poped off to calculate values.

For example

int a = 1;
int b = 1;
int c1 = (a++) + a;
int c2 = b + (b++);

c1 will be set to 3 and c2 will be set to 2.   Written in C/C++ both will give the answer of 2.  The operator a++ will increment a by 1 but return its original value.  With a stack base, the 1st part of the equation, (a++), is calculated and the answer ( 1 ) push onto the stack.   The next part of the equation (a) is calculated and the answer (2) and push onto the static.   Why is the 2nd part of the equation 2?  When the add operation is run, it retrieves the actual values of the variable one of which is the returned ‘original value’ of a and the other is the current value of A.

An alternate way of writing the XOR swap that works on stack based (and non stack based) VMs is as follows.

a^=b
b^=a
a^=b

Note:  This does not work if A and B are the same object.  You shouldn’t be swapping in the case any ways.

The short moral of the story is dont use shortcut code to put a bunch of commands on the same line.  It may not do what you think it will.