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
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.
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 museli say - and ask them to swap the contents. Without an additional empty bowl this usually results in a very messy table as bowl A is emptied on the table to make way for the contents of bowl B.
The correct 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
and this is the basic swap algorithm, so deep in every programmer that they 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 impmenentation.
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!
More seriously the SWAP statement does have a subtle side of its own. Instead of moving data many SWAP statements move labels. If you have a bowl of cornflakes labelled A and a bowl of muesli labelled B then simply swapping the labels on the bowls achieves the much the same effect as swapping the contents of the bowls!
Swapping labels avoids the need for a temporary variable to hold the value in transit in a fairly obvious way once you have seen the idea.
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. Using this fact it isn't difficult to see that you can swap the contents of A and B by a three stage process:
Value in A Value in B
A=A+B A+B B
B=A-B A+B A
A=A-B B A
This 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 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. 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.
As 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,
Value in A Value in 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!
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. Shame to let a nice idea like that die out.