Swap values experiments on using different approaches
Folks, we all know one typical interview question around swapping values for two variables. And maybe all of us remember by heart that there are multiple ways to do so.
The most straightforward way which everyone must know during school is using a temp variable.
int a = 10, int b = 5;
int tmp = a;
a = b; b = tmp;
The second way is to use arithmetic operations such as addition/subtraction or multiplication/division
Code is like
int a = 10; int b = 5;
a = a + b; b = a – b; a = a – b;
The good thing is we don’t need to use a temp variable here and it means less memory/register used.
Same logic goes for multiplication and division. However, another interesting way which is often asked is using XOR.
a = a ^ b; b = a ^ b; a = a ^ b;
Three assignments with same expression. Nothing easier to remember.
But it seems few people have ask which one is better except the memory assigned for the extra variable. I did some simple benchmark today and would like to share with you guys. In a block of 100k “swap” operations, I increment it one block at a time and measure the time it takes using three different above approaches.
System: runs on a Intel Core i5 3Ghz x 4, 64 bits, Java 7
Input are all primitive integers, time measure in nano second. Before running, did some “warm up” for JVM to be ready.
What I found out is there are no significant difference between using a tmp variable and using arithmetic operation. The time taken fluctuates around 300 ns regardless of the number of block of operation (be it 100k swap or 50 times more).
Using XOR, a clearly linear trend in the time taken can be observed. Approximately 230k ns is needed for one block (100,000 swaps). This is 1000 times as slow as other traditional methods.
Conclusion: Using XOR approach is a crappy theory which is only valid in interview/text book context!
Attaching a graph of the result swap_experiment
Welcome any comments or question.