tisdag 28 maj 2013

The XOR swap algoritm.

This is like the geekiest thing ever. Love it. Embrace the geek. Embrace your inner geek.

Swapping places between two values in a computer is a bit more involved than one would first think.
A = B ;
B = A;
doesn't work since in the first line A gets the value from B and in the second B gets the value from A (which is now B) so the value for A is lost. You need a temporary storage. When swapping places in the real world,say two glasses, you simply take one in each hand and swap them. The problem is the computer only has one "hand". So you need to do something like:
C (temporary storage) = A;
A = B;
B = C;

No biggie right ? There's plenty of memory nowadays and C can be reused right after we're done.

But what if you're programming for a really tiny embedded processor like a PIC for example ? Or you have a tightly optimized Assembly loop and you have used all registers ? Memory access is sllooowwww compared to register access and can wreak havoc with performance in critical sections of the code.

Enter you new best friend: the XOR swap algorithm:
A= A xor B;
B = A xor B;
A= A xor B;
or in x86 Assembly
xor eax,ebx
xor ebx,eax
xor eax,ebx

Voila! The value of register a is now in b and vice versa and we only used 2 registers instead of 3.
My inner geek gets all misty eyed and weepy. Love it.

Inga kommentarer:

Skicka en kommentar