Xor swap algorithm
|
|
In computer programming, the xor swap is an algorithm which uses the exclusive disjunction (XOR) operation to swap distinct values of variables having the same data type without using a temporary variable. This algorithm works using the symmetric difference property of XOR: A XOR A = 0 for every A
| Contents |
The algorithm
Standard swapping algorithms require the use of temporary storage. The intuitive algorithm to swap x and y involves:
- Copying y aside to temporary storage (
temp ← y) - Setting y to be x (
y ← x) - Copying the temporary storage value back to x. (
x ← temp)
Or, if given two variables x and y of type integer, the algorithm to swap them is as follows:
- x = x + y
- y = x - y
- x = x - y
Using the XOR swap algorithm, however, neither temporary storage nor arithmetic operations are needed. The algorithm is as follows (where X and Y are the names of two variables, rather than two values):
- XOR X and Y and store in X
- XOR X and Y and store in Y
- XOR X and Y and store in X
The algorithm looks much simpler when it is written in pseudocode.
- X := X XOR Y
- Y := X XOR Y
- X := X XOR Y
This typically corresponds to three machine code instructions. For example, in IBM 370 Assembler code:
- XOR R1, R2
- XOR R2, R1
- XOR R1, R2
where R1 and R2 are registers and the operation XOR leaves the result in the first argument. This algorithm is particularly attractive to assembler programmers due to its performance and efficiency. It eliminates the usage of the intermediate register which is a limited resource in machine language programming. It also eliminates two memory access cycles which would be expensive compared to a register operation.
Explanation
For example, let's say we have two values X = 12 and Y = 10. In binary, we have
- X = 1 1 0 0
- Y = 1 0 1 0
Now, we XOR X and Y to get 0 1 1 0 and store in X. We now have
- X = 0 1 1 0
- Y = 1 0 1 0
XOR X and Y again to get 1 1 0 0 - store in Y, and we now have
- X = 0 1 1 0
- Y = 1 1 0 0
XOR X and Y again to get 1 0 1 0 - store in X, and we have
- X = 1 0 1 0
- Y = 1 1 0 0
The values are swapped, and the algorithm has indeed worked in this instance.
In general, however, if we call the initial value of X = x and the initial value of Y = y, then performing the above steps, using ⊕ for XOR for clarity, and remembering that a ⊕ a = 0 and b ⊕ 0 = b, yields:
- X = x ⊕ y, Y = y
- X = x ⊕ y, Y = x ⊕ y ⊕ y = x
- X = x ⊕ y ⊕ x = y, Y = x
Code examples
x86 assembly language
The following code in x86 assembly language uses the xor swap algorithm to swap the value in the AX register with the value in the BX register without using a temporary buffer.
XOR AX, BX
XOR BX, AX
XOR AX, BX
However, all x86 microprocessors have an XCHG instruction which does the same work on its operands more efficiently than the above sequence of XORs.
Visual Basic
The following Visual Basic subroutine swaps the values of its parameters using the xor operator.
Sub Swap (Var1, Var2) Var1 = Var1 Xor Var2 Var2 = Var2 Xor Var1 Var1 = Var1 Xor Var2 End Sub
C
C programming language code to implement XOR swap of x and y:
x ^= y; y ^= x; x ^= y;
The set-up as a compiler macro is common for extensive use.
#define xorSwap(x,y) { (x) = (x) ^ (y); (y) = (x) ^ (y); (x) = (x) ^ (y); }
As a function:
void xorSwap(int *x, int *y)
{
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
It should be noted that this function will not work if you try to swap something with itself (i.e. xorSwap(&var, &var) will fail — it will assign the value zero to var).
Usage in practice
The use of the algorithm is not uncommon in embedded assembly code where there is often very limited space available for temporary swap space, and this form of swap can also avoid a load/store which can make things much faster. Some optimizing compilers can generate code using this algorithm.
However on modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. This is because modern CPUs strive to execute commands in parallel. In the XOR technique, the operands of all commands depend on the results of the previous command so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture.
If the language permits, the ugly details of swapping should be hidden inside a macro or an inline function. Not only will it make the code clearer, but it will also be possible to switch to a different swapping routine if it is faster.
This trick could also be used by someone trying to win an Obfuscated C Code Contest.
This can have dangerous side-effects, especially when used in macros, as a XOR a will incorrectly yield 0.
Machines with hardware swap capability
In actual code, the need to exchange the contents of two variables occurs frequently. At least one machine available as early as 1970, the Datacraft (later Harris) 6024 series did provide such a capability, obviating the need for temporary storage, XOR swapping, or any other trickery. Instructions permitted the contents of any register to be exchanged with a core memory location in a single read-write cycle. Another machine, the PDP-6, had such a capability as early as 1964; its EXCH instruction could exchange the contents of any accumulator with the contents of any memory location or any other accumulator. And as noted above x86 microprocessors feature an XCHG instruction.
Had the PDP-11 included such an instruction, it is possible that the C language might have included variable exchange as a fundamental binary operator.