The Algorithm
Conventional swapping requires the use of a temporary storage variable. Using the XOR swap algorithm, however, no temporary storage is needed. The algorithm is as follows:
X := X XOR Y Y := X XOR Y X := X XOR YThe algorithm typically corresponds to three machine code instructions. Since XOR is a commutative operation, X XOR Y can be replaced with Y XOR X in any of the lines. When coded in assembly language, this commutativity is often exercised in the second line:
Pseudocode | IBM System/370 assembly | x86 assembly |
---|---|---|
X := X XOR Y |
XR R1,R2 |
xor eax, ebx |
Y := X XOR Y |
XR R2,R1 |
xor ebx, eax |
X := X XOR Y |
XR R1,R2 |
xor eax, ebx |
In the above System/370 assembly code sample, R1 and R2 are distinct registers, and each XR operation leaves its result in the register named in the first argument. Using x86 assembly, values X and Y are in registers eax and ebx (respectively), and xor
places the result of the operation in the first register.
However, the algorithm fails if x and y use the same storage location, since the value stored in that location will be zeroed out by the first XOR instruction, and then remain zero; it will not be "swapped with itself". (Note that this is not the same as if x and y have the same values. The trouble only comes when x and y use the same storage location, in which case their values must already be equal.)
Read more about this topic: XOR Swap Algorithm