Friday, January 15, 2016

XOR swap - or how to swap two numbers

It used to be explain in multiple books that I read in university, but I do not see a clear and easy to follow explanation in the internet.

Let's say that we have two variables:
x = 5
y = 7
and we want to change the value of these numbers w/o using additional variable. We can achieve it by using using simple basic operation:
x := x + y = 5 + 7 = 12
y := x - y = 12 - 7 = 5
x := x - y = 12 - 5 = 7
But there is a different technique that is more efficient in IT because all the data is kept in binary format, it make sense to take advantage of a simple xor operation to do the work.
x= 101 in binary = 5 in decimal
y= 111 in binary = 7 in decimal


x=101
y=111
------ x xor y
x=010

x=010
y=111
------ x xor y
y=101 = 5 in decimal

x=101
y=010
------ x xor y
x=111 = 7 in decimal
One more note. You don't want to code it, because compile should optimize it for you - even when you use additional variable to swap the values compiler should use xor technique to do the job.

No comments: