Xor swap algorithm

In computer programming, the xor swap is an algorithm which uses the exclusive disjunction (XOR) operation to swap the values of two variables without a temporary variable. This algorithm works using the symmetric difference property of XOR, that

A xor A = 0 for every A

Explanation

Standard swapping algorithms require the use of a temporary storage area - standard intuitive algorithms to swap x and y involve:

• copying y aside to a temporary storage area
• setting y to be x
• copying the temporary storage value back to x.

However, the XOR swap algorithm does not -- this algorithm follows (where X and Y are the names of two variables, rather than two values):

1. XOR X and Y and store in X
2. XOR X and Y and store in Y
3. 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 assember 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.

To see how this works, call the initial value of X = x0 and the initial value of Y = y0. Then:

1. X = x0 XOR y0, Y = y0
2. X = x0 XOR y0, Y = x0 XOR y0 XOR y0 = x0
3. X = x0 XOR y0 XOR x0 = y0, Y = x0

(remember that a XOR a=0, b XOR 0=b).

Usage in practice

Some experienced programmers advise that this technique should not be used in programming, as its effect is not clear unless you already know the trick. However, others remark that its use is acceptable providing that the trick is wrapped in an appropriately named macro such as SWAP or XOR-SWAP, or appropriate commenting of the code is done.

The use of the algorithm is not uncommon in embedded assembly code where often there is 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 generates code using this algorithm.

This trick could also be used by someone trying to win an Obfuscated C Code Contest.

See also: Xor,Symmetric difference,Xor linked list