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:

Then we execute *x ^= *y or, to be clearer *x = *x ^ *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

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

Wow! So at this point we have :

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,

Applying similar reasoning to register

That means that now we have:

Voilá! We achieved what we wanted! 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-->**xWow! 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.
## No comments:

## Post a Comment