We all know that if you want to swap the contents of two variables you need a third temporary variable to do the job. It's like swapping the contents of two mugs using a third to hold the contents of the first while you pour the second into it. Using a third temporary mug seems inevitable, but you can swap the contents of two variables without a third with the magic XOR swap.

What Programmers Know

Contents

1. The Computer - What's The Big Idea?*
2. The Memory Principle - Computer Memory and Pigeonholes*
3. Principles of Execution - The CPU
4. Assemblers and assembly language*
5. The Essence Of Programming
6. Variables - Scope, Lifetime And More*
7. Binary Arithmetic
8. Hexadecimal*
9. Binary - Negative Numbers*
10. Floating Point Numbers*
11. Inside the Computer - Addressing
12. The Mod Function
13. Recursion
14. The Lost Art Of The Storage Mapping Function *
15. Hashing - The Greatest Idea In Programming
16. Advanced Hashing
17. XOR - The Magic Swap*
18. Programmer's Introduction to XML
19. From Data To Objects*
20. What Exactly Is A First Class Function - And Why You Should Care*
21. Stacks And Trees*
22. The LIFO Stack - A Gentle Guide*
23. Data Structures - Trees
24. Inside Random Numbers
25. The Monte Carlo Method
26. Cache Memory And The Caching Principle
27. Data Compression The Dictionary Way
28. Dates Are Difficult*
29. Sequential Storage*
30. Magic of Merging*
31. Power of Operators
32. The Heart Of A Compiler*
33. The Fundamentals of Pointers
34. Functional And Dysfunctional Programming*

* Recently revised

I guess it must be a bit like pouring the contents of the two mugs into each other at the same time - not something easy to imagine!

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 a 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, or whatever the most difficult language you can think of is, 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. Python for example performs the swap as a simple:

A,B=B,A


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!

<ASIN:1871962439> 

<ASIN:1871962722> 

<ASIN:1871962714>

<ASIN:1871962420>