Sunday, March 15, 2009

How can you swap two integer variables without using a temporary variable?

A: The reason that this question is poor is that the answer ceased to be interesting when we came down out of the trees and stopped using assembly language.

The "classic" solution, expressed in C, is

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

Due to the marvels of the exclusive-OR operator, after these three operations, a's and b's values will be swapped.

However, it is exactly as many lines, and (if we can spare one measly word on the stack) is likely to be more efficient, to write the obvious

int t = a;
a = b;
b = t;

No, this doesn't meet the stipulation of not using a temporary. But the whole reason we're using C and not assembly language (well, one reason, anyway) is that we're not interested in keeping track of how many registers we have.

If the processor happens to have an EXCH instruction, the compiler is more likely to recognize the possibility of using it if we use the three-assignment idiom, rather than the three-XOR.

By the way, the even more seductively concise rendition of the "classic" trick in C, namely

a ^= b ^= a ^= b

is, strictly speaking, undefined, because it modifies a twice between sequence points. Also, if an attempt is made to use the idiom (in any form) in a function which is supposed to swap the locations pointed to by two pointers, as in

swap(int *p1, *p2)
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;

then the function will fail if it is ever asked to swap a value with itself, as in

swap(&a, &a);


swap(&a[i], &a[j]);

when i == j. (The latter case is not uncommon in sorting algorithms. The effect when p1 == p2 is that the pointed- to value is set to 0.)

No comments: