how can you swap two variables without a temporary variable?

simple! the almost-magical XOR operator!

in C/C++, you can do this:


(addendum, 2001-08-22) ... Well, actually you can not, in fact, do that. Or you can, it's just not 100% guaranteed to work according to the ISO C standard. To use the xor swap correctly, you need something more like this:

a^=b; b^=a; a^=b;
Why? Well, in ISO C, a variable is not allowed to be modified more than once between sequence points. Since a is modified twice in the original expression, the expression is undefined, and thus might not work on all compilers.

(Thanks to scs for pointing me at Question 3.3b in the comp.lang.c FAQ, from which I gleaned this updated information.)

First off, if it was to be parenthesized, it would go:
a ^= (b ^= (a ^= b));
  3     2     1
This just helps visualize the order that things happen in.

Lets take

a = 1001 1011
b = 1100 0110
The first XOR modifies a:
a  = 1001 1011
b  = 1100 0110
a' = 0101 1101
The second XOR then takes a' and b, storing the result into b':
b  = 1100 0110
a' = 0101 1101
b' = 1001 1011
Note that b' now is the same value as the original a. The last XOR then operates on a' and b', storing into a":
a' = 0101 1101
b' = 1001 1011
a" = 1100 0110
The final results stored (a" and b') are the same as the original a and b, except swapped.
Now, the question of why does this work?

Take two values:

c = 1100
d = 1010

e = (c xor d)
e = 0110
(d xor e) == c
(c xor e) == d
In the above example, the 'e' equivalent was stored into a'. The second operation then extracts a from the xor'ed value and stores it into b'. Then operating on the 'e' value again, this time with the original a value (stored in b'), the b value is extracted and stored into a".
As a note, many compilers will complain if you do this math on pointers. Furthermore, this only works with same typed values: swapping a float with an integer is a bad idea.
Why would you use this?

In days of old computers had very few registers and not much memory either. Without the XOR Swap, working from the 8088 processor, to swap 2 memory locations one would have to store the register somewhere in memory, load the meory desired to be swaped into the register, store that memory somewhere, load the 2nd piece of meory into the reigster, store that at the first place, load the saved memory into the reigster, store that at the 2nd spot, and load the register with the original memory - 8 steps and may cycles.

On the other hand, doing a register, memory xor took about the same amount of time as doing a load from memory into the register. Thus the inner 6 steps can be shortened to 4 steps. Load the register with the value, xor it with the 2nd value (destination in register), xor or that with the first value (destination in memory), and xor the register with the 2nd value (destination in memory). This resulted in saving two instructions (actualy quite valueable) and improved performance by about 33% for that operation. This was a valueable operation.

Today, this is more for show and understanding how the compiler works than practical useage. Modern processors have dozens of registers and swaping two values likely has two or three registers that are not being used (if this is even necessary - the values may be in the registers themselves) at which point it is simply load, load, store store.

c code:
as compiled by gcc:
        movl -4(%ebp),%eax
        xorl -8(%ebp),%eax
        movl %eax,%edx
        movl %edx,-4(%ebp)
        movl %edx,%eax
        xorl -8(%ebp),%eax
        movl %eax,%edx
        movl %edx,-8(%ebp)
        xorl %edx,-4(%ebp)
        register int c;
        c=a; a=b; b=c;
as compiled by gcc:
        movl -4(%ebp),%eax
        movl -8(%ebp),%edx
        movl %edx,-4(%ebp)
        movl %eax,-8(%ebp)

All of this code is well and good but, as cadmos so eloquently hinted at, "Premature optimization is the root of all evil." (C.A.R. Hoare). Your clever trick could cost you when the code hits the core.

The cost might not be only an efficiency penalty, either: If you XOR two signed integers in C, the results are, strictly speaking, undefined. It could create a trap value that causes the machine to dump core, for instance. The simpler method using a temporary value is guaranteed to work, no matter what machine your code is heading for next.

And that's the point: The simpler, obvious method is simpler and obvious. It is more human-friendly, which would be a very good reason to prefer it even if the alternative was more machine-friendly. As Knuth maintains, code is meant to be read by humans first, and machines second. C is a notational convenience we layer over machine code, and as such it damned well should be convenient.

Log in or register to write something here or to contact authors.