Swapping two variables without using a temp variable

That is something I learned yesterday and I found it very cool. Thus it is something I must share.

I remember the swap algorithm was taught  in the very first days of college. It is very basic algorithm, but it is used in the foundations of several other algorithms. Until now,  it seemed  to me pretty obvious that its implementation would be inevitably (in C++03):

template<typename T>
void swap(T& x, T& y){
        T temp = x;
        x = y;
        y = temp;
}

In other words, it would always require at least 3 registers for the exchange.

If you are working in a pretty limited environment, a micro-controller for instance, you may not have 3 registers available for use. Therefore you cannot do the swap.

Well, that was I thought until yesterday. Then, I found I should review some material from my old "reduction of logical circuits" class  instead of playing Doom3 (It's kind of old game now, but it is only 10 bucks at iTunes!).

If your data is suitable for bitwise operations then you can do the follow (in C):

void swap(int* x, int* y){
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}   

Why does it work ?

Explanation can be found at Wikipedia, but I intend to be more didactic here. Firstly, we need to remember some properties of the exclusive-or (xor) operation:

• P1 - Commutativity  x^y = y^x
• P2 - Associativity      (x^y)^z = x^(y^z)
• P3 - x^x = 0
• P4 - x^0 = x

So let's step through the algorithm. We are going to use two registers: A which initially will hold the value for x, and B which will hold for y. Thus, we have before the call to swap:

A x
B y

Then we execute *x ^= *y  or, to be clearer *x = *x ^ *y :

A x^y
B y

Okay, we still cannot apply any of the properties above. So let's move to the next line *y = *y ^ *x . But remember that x in the code does not refer to the value  that variable x hold before swap was called. It in fact points to our register A. So that line really means  B <-- B xor A. So the registers are now modified to :

A x^y
B y^(x^y)

Now we have something interesting. Let's apply the properties to the register B:

y^(x^y) --P1--> y^(y^x) --P2--> (y^y)^x --P3--> 0^x --P1--> x^0 --P4--> x

Wow! So at this point we have :

A x^y
B x

We are closer to our goal. Now we execute the last line  *x = *x ^ *y which in fact mean to us, using our register definitions, A <-- A xor B :

A (x^y)^x
B  x

Applying similar reasoning to register A:

(x^y)^x = (y^x)^x = y^(x^x) = y^0 = y

That means that now we have:

A y
B x

Voilá! We achieved what we wanted! Registers A and B were swapped  only  with the  help of exclusive-or operations. No extra temporary register was needed.