XOR - The Magic Swap
Written by Alex Armstrong   
Article Index
XOR - The Magic Swap
XOR Hashing

We all know that if you want to swap the contents of two variables you need a third temporary variable to do the job - but it can be done with just two with the magic XOR swap.

The Joy Of Swap 

One of the first serious problems any budding programmer comes up against is how to swap the contents of two variables.

The standard, almost laughable, error if you are an experienced programmer is to write:

A=B
B=A

The mistake is of course that both variables end up equal to B because the contents of A are lost in the first assignment.

This is one of the first simple examples a beginner is shown of the way that the order of execution of a program affects its meaning, i.e. the result of

A=B
B=A

is not the same as

B=A
A=B

This may seem obvious but beginners find it hard because in algebra it simply means that A is equal to B and B is equal to A. They are not used to the idea that there is a time sequence implied in the instructions - this is why you are a programmer and they are a non-programmer.

The Cereal Bowl Algorithm

If you ever have to teach a beginner how to get over this problem then the best way to do it is give them two bowls of cereal - one cornflakes and one muesli say - and ask them to swap the contents. It helps to make them real bowls with real cereal rather than a gedanken experiment. 

Without an additional empty bowl the result is usually very messy table as bowl A is emptied on the table to make way for the contents of bowl B. It really can take time for a beginner to realize that they do need a third bowl. There is something about the starting configuration being two bowls with cereal and the ending configuration being two bowls of cereal that makes them assume that the problem can be solved with just two bowls. And in this case they are absolutely right but a two bowl solution requires more sophistication than they usually have at this stage. 

The correct, and obvious once you know it, algorithm is to tip the contents of bowl A into the empty bowl C, then B into A and finally C into B. In a more compact form this is just

C=A
A=B
B=C

and this is the basic swap algorithm, so deep in every programmer that we hardly notice that it is an algorithm at all.

But there is a way to swap two variables without using a temporary third variable and it isn't just a matter of swapping labels or using a high level swap statement that hides the implementation - and this is what we are about to examine. 

One word of warning.

Any beginner who refuses to solve the problem using an additional bowl because you could simply swap the A and B labels over needs to be promoted to learning Lisp at once. 

The problem with this solution, swapping labels, is that when it comes to implementing it you still have to swap something real over. In computing terms the label on the side of the bowl is a reference i.e. an address and swapping two addresses over is the same problem as swapping two values over. That is in this case A holds the address of the first bowl and B holds the address of the second bowl. To swap the addresses over you still need a temporary storage for one of the addresses.

Some irritating languages have come up with statements such as SWAP A,B which perform the  swap without need for the extra bowl or the trouble of working out how the swap is done.

It is said that the average IQ of drivers fell by five points when automatic transmission became common because they didn't have to think about gear shifts - I can't help thinking that if a SWAP statement ever becomes common currency the same will happen to the programming community!

The Additive Swap

Less obvious is trick that still moves data but does so without any intermediate storage. There are a number of versions of the method, the simplest being based on arithmetic.

The key to the idea is to notice that if you add the value in B to A then you can still recover the original value in A by subtracting B. If you add to this the idea that you can also get B by subtracting A then you have the start of an idea. 

Using this fact it isn't difficult to see that you can swap the contents of A and B by a three stage process:

Instruction Value in A     Value in B
               A              B
A=A+B         A+B             B
B=A-B         A+B             A
A=A-B          B              A

This really does fulfil the beginners intuition that if you have two bowls of cereal at the start and two at the end you should be able to swap them over using just two bowls.

Notice that what is going on is the fact that as you proceed with the swap you make sure that both values are recoverable at every step. When you add B to A you still have B so you can undo the process by subtracting B. At the second step you can get back B by subtracting A. At no point have you lost the values of A and B just mixed them up in a reversible way. Ah if only it was possible with cereal. 

This still looks like magic; is there any drawback to the method?

The answer is that it can all go wrong if the value of A+B is larger than a variable can hold. In a sense we are making use of the full range of values that a variable can store to hold A+B in a single variable and using -B or -A as decoding keys to get the original values back.

However, if you replace the operation of addition with any operation that combines the two values so that they can still be separated using the original values then you have another swapping method.

The XOR Swap

The operation with most promise is the exclusive OR operation - often denoted as XOR. The A XOR B operation takes each bit in the binary representation of A and combines it with the corresponding bit of B to give a result according to the following table:

 A B  A XOR B
 0 0     0
 0 1     1
 1 0     1
 1 1     0

Many languages have bitwise exclusive OR operations. In JavaScript, C  and C# it is written A^B.

The interesting thing about A XOR B is that

(A XOR B) XOR A

is B and

(A XOR B) XOR B

is A - which should be compared to A+B-A and A+B-B.

A simpler way of saying this is that 

A XOR (A XOR B)=B

and XOR is its own inverse. XOR a value with something and you get a new value perform the same XOR again and you get back the value you started with.

This all means that XOR behaves just like addition, and like subtraction as well, you should be able to see how it can be used in the same three-stage swap routine given earlier. That is,

Instruction  Value in A  Value in B
                 A           B
A=A XOR B     A XOR B        B
B=A XOR B     A XOR B        A
A=A XOR B        B           A

and as you can't get an overflow from XORing two values together the method is foolproof and somehow seems to suggest that you can get a quart into a pint pot by storing two values in a single variable at the same time!

Of course the trick is that you are never storing two values in a single variable you are storing two values in two variables at all times. It is just that for some of the times the values are stored in a mixed up coding. 

I am certainly not suggesting that the triple XOR method is the one to use every time you want to swap two variables but it has its own fascination. In the dark old days of punched cards and flashing lights every assembly language programmer, i.e. every programmer, knew the trick because it saved having to use another memory location. Today many compilers perform the XOR swap as an optimization when they detect a variable swap using a temporary variable. The overall result is that even though the technique is still in use - programmers don't get to see it. 

Shame to let a nice idea like that die out.



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.