Visualizing XOR swap
Introduction
In programming, we often need to swap (exchange) the contents of two
variables, say x and y. This is normally achieved using a
temporary variable, say t, as follows:
t := x
x := y
y := t
The XOR swap technique achieves the above for binary values without using a third variable, here \(\oplus\) is the XOR operation:
- (1) \(x := x \oplus y\)
- (2) \(y := x \oplus y\)
- (3) \(x := x \oplus y\)
I first came across the algorithm (technique) in the mid 80s, and set about convincing myself how and why it works. My first attempt was to use a truth table, shown below. The second was to use simple algebra, which is described in the Wikipedia article, so I won’t cover it here. Many years later I discovered that the technique can be explained graphically using a triangle.
The Wikipedia page for XOR swap is very extensive and covers a lot of ground. Here, I will cover a couple of additional explanations that are not included on the Wikipedia page.
Using a truth table
Interestingly, the Wikipedia page, while extensive, does not include an explanation using a truth table, so here’s my version:
| \(x\) | \(y\) | (1) \(x\) | (2) \(y\) | (3) \(x\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 |
In the above, the columns \(x\) and \(y\) represent the initial values of the two variables, and columns (1), (2) and (3) represent the values of the left hand sides of the three assignments after each of the respective operations. So, column (2) shows the final value of \(y\), which matches the original column for \(x\), and, column (3) shows the final value of \(x\), which matches the original column for \(y\).
The truth table above applies to single bit values, however, since the application of the XOR operation to larger integers is performed bit-wise, the XOR-swap is valid for integers of any size. Basically, the same truth table applies to each pair of bits independently.
The triangle
The XOR operation can be visualized as a triangle with the two operands at two of the vertices and their exclusive-or at the third. That is, if \(A\) and \(B\) are two arbitrary binary values at two of the vertices, then \((A \oplus B)\) will be at the third vertex.
The most interesting, and useful, property of XOR is that from the values at any two vertices we can derive the third by applying the XOR operation to the two values at those vertices. So,
\(A = B \oplus (A \oplus B)\), and
\(B = A \oplus (A \oplus B)\).
Now, let’s say \(x\) and \(y\) have the values \(A\) and \(B\), respectively, then the three assignments will move the two variables around the triangle one vertex at a time, which will result in \(x\) and \(y\) containing the new values \(B\) and \(A\), respectively.
