During a lunch interview, my interviewer wrote the following
line of C/C++ code on a napkin:
a ^= b ^= a ^= b;
He then asked me what it does. It was a bad question. While we might expect it to swap the contents of a and b, the code
relies on the results of intermediate subexpressions. According to Stroustrup,
The C++ Programming Language (2nd
Ed.), section 6.2.2, “The order of evaluation of subexpressions within an
expression is undefined.” This is,
in fact, a hold-over from Kernighan & Ritchie’s original definition in The
C Programming Language (of which I don’t
have a copy on hand, or I’d look it up—so the exercise is left for the
It’s important to note that the compiler’s behavior is undefined as opposed to implementation defined, which means that you may well get the behavior you
expect some times, yet there will be times when the behavior is something
else. For example, Metrowerks’
compilers give the expected results when both variables are allocated in
registers, but produce a different result when the variables are allocated on the
You’ll have to ask a compiler writer to get the details of the
underlying reason for this, but it has to do with modern compiler issues like
instruction scheduling, pipelining and attempting to get two processor
instructions to execute simultaneously.
The important thing for programmers to understand is that different
behaviors for the same line of code is not
a compiler bug when the behavior is undefined.
We can resolve the undefined issue by using the comma
^= b, b ^= a, a ^= b;
But that doesn’t completely remove the stupidity of this
programming trick. It’s still
obscure. We could comment it
whenever we use it, but that gets tedious. One way to remove the obscurity is to use a macro:
Swap(a, b) (a ^= b, b ^= a, a ^= b)
While that removes the obscurity of the code, there’s still
one more problem with it.
Compilers have advanced to the point where the use of inline functions
and global optimizations render this kind of programming trick completely
unnecessary. Worse yet, it can
actually result in slower code than if you’d been more direct in your intent.
For example, consider the C++ way of doing this:
template <typename T>
inline void Swap (T &a, T &b)
c = b;
The actual code generated by the Metrowerks PowerPC compiler
completely optimizes out both the call semantics and the use of any temporary
variable. In fact, the compiler
merely makes any subsequent references to the location for variable a refer to the
location that had originally been allocated for variable b, and vice-versa. As far as the generated code is
concerned, the call to the inline Swap function becomes a complete no-op.
So, not only is the XOR swap stupid because it’s obscure, it’s stupid
because, with modern optimizing compilers, the eventual result often ends up
being contrary to the intended result of using the coding trick in the first
place. The only benefit of the XOR version of
macro is in C programs where we don’t have the benefit of templates. The Swap macro provides a type-independent
way of expressing the idea. The
price, however, would suggest that writing separate inline routines for each
integral type for which it is needed would result in smaller, and faster, code.
The moral is, before you consider using some obscure coding
trick for the sake of performance, write up some sample code, and take a look
at the actual code your compiler generates. More often than not, you’ll find that the less obscure
method results in better code.