Many people have heard of how to swap two values without using temporary storage, using XORs. This is often summarised as:

a ^= b ^= a ^= b;

There are other operators that can be used to do the swap, but in the degenerate case, this essentially becomes the XOR trick again.

Firstly, I ought to address the fact that the above statement isn’t strictly valid C. Multiple side effects within a single expression leads to undefined results. Most compilers will get the ‘right’ answer, but why take the risk for the sake of a few extra characters? It is easy to rewrite correctly (I’ll also remove the combined xor-assignment operator, for clarity later):

a = a ^ b;
b = a ^ b;
a = a ^ b;


If you haven’t seen this trick before, it is probably worth working through an example or two on paper. There are quite a few explanations on the net, if you get stuck.

The reason this works is that xor is a reversible operation. It is further simplified by the fact that xor is its own inverse – that is to say:

(a ^ b) ^ b = a

You can use other operations instead of xor, such as addition and subtraction. Subtraction is the inverse of addition, so you can write the swap as:

The 2nd and 3rd columns show how the values change during execution, and that the end result is that the values in a and b are swapped. It isn’t quite as neat as xor since you need to use two different operators (+ and -) rather than just one, but it is easier to grasp since most of us are more familiar with + and – than with xor. The similarities in structure to the xor version above should be clear.

One thing to note in the above is that I have completely ignored the issues associated with finite register width. What happens when the intermediate values generate a carry? I’ll work through an example, assuming a 4-bit register width. We should use large numbers, since we are interested in seeing what happens when we overflow a 4-bit number. Lets try to swap 15 and 14. In this example, the numbers in brackets indicate what the full-precision result is, before truncating to a 4-bit unsigned representation.

So, both a and b end up with the right (swapped) values. This means that instead of using xor, we can swap values using addition and subtraction and ignoring any carry. By truncating all the numbers in these examples to 4 bits, we are simply doing modulo 16 arithmetic.

We can go further than this, by shrinking the register width. Instead of 4 bits, lets think about 1-bit registers (which will be modulo 2 arithmetic). Rather than work through some examples, we can look at the truth tables for 1-bit addition and subtraction. We can compare them to xor too.

Once you move down to single-bit operations, and ignore the carry, an odd thing happens. Addition and subtraction become the same operation, and both are the same as an xor. This modulo 2 equivalence of operators should start to suggest another way of looking at the original xor formulation. We could say that it is equivalent to performing multiple 1-bit additions/subtractions, in parallel. In other words, it is simply the vector processing version of the addition/subtraction approach with each bit being calculated with modulo 2 operations!