Thursday, February 07, 2013

Swapping Values The Tricky Way

Last week my friend Tom Indelicato who talking to his Advanced Placement Computer Science students about sorting. As is necessary this involved talking about how to swap one value for another. This is typically done with the use of a temporary variable with code that looks something like this:
            temp = x;
            x = y;
            y = temp;
This is as you would if you were moving a liquid between two classes. You’d empty one glass into an empty glass then pour the contents of the second glass into the first glass. Finishing by pouring from the third glass into the second. Works great. Just takes having an empty space to hold things temporarily.

Tom showed me a different way. A tricky way. A way that only really works with integer values.

 y = y ^ x;
 x = y ^ x;
 y = y ^ x;

The caret ( ^ ) is the symbol for an Exclusive Or for those of you not current in C#. image

It’s Truth table looks something like  the image on the right. Of course when Tom showed me this I had to try it out. I used the values X = 10 and Y = 3. In Binary the results looked something like this: image

Naturally I had to write a program to double check my math. Smile

image

This is all fun and interesting in a geeky sort of way. But is it a good idea? No so much. For one thing it is tricky, unusual and can easily confuse people.  For another there is no speed gain. In fact the XOR operation is actually slower than the copy to another location operation. Not by a lot. They can both be register operations which are the fastest sort of CPU operations. But without a good performance gain there is no real reason to use the XOR method (even if it being confusing were not enough reason) over the swap operation. Lastly the fact that this is not as general purpose as the swap method is the nail in the coffin as far as I’m concerned.

But it sure is cool. In a geeky sort of way. Smile

2 comments:

Anonymous said...

Ah but you need 3 registers for the swap method and 2 for the other. In days gone by when processors had less registers this was possibly a deciding factor.

http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_use_in_practice

These days though... not important and just an annoying interview question

Alfred Thompson said...

I thought about the three registers issue when I was doing this. There was a time when that was a lot more important than it was today. A lot depends on the specific hardware, microcoding and a lot of other things that are more hardware dependent than software. One could imagine a design that made swapping faster but I don't imagine anyone optimizing for that these days.