XOR swap algorithm

related topics
{math, number, function}
{system, computer, user}

In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap values of distinct variables having the same data type without using a temporary variable. "Distinct" means that the variables are stored at different memory addresses; the actual values of the variables do not have to be different.

Contents

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 Y

The 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. For example, in IBM System/370 assembly code:

XR    R1,R2
XR    R2,R1
XR    R1,R2

where R1 and R2 are distinct registers and each XR operation leaves its result in the register named in the first argument.

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.)

[edit] Proof that the XOR swap works

The binary operation XOR over bit strings of length N exhibits the following properties (where \oplus denotes XOR):[1]

Suppose that we have two distinct registers R1 and R2 as in the table below, with initial values A and B respectively. We perform the operations below in sequence, and reduce our results using the properties listed above.

Step Operation Register 1 Register 2 Reduction
0 Initial value \ A \ B
1 R1 := R1 XOR R2 \ A \oplus B \ B
2 R2 := R1 XOR R2 \ A \oplus B \begin{align} (A \oplus B) \oplus B =& A \oplus (B \oplus B) \\=& A \oplus 0 \\=& A \end{align} L2
L4
L3
3 R1 := R1 XOR R2 \begin{align} (A \oplus B) \oplus A =& A \oplus (A \oplus B) \\=& (A \oplus A) \oplus B \\=& 0 \oplus B \\=& B \end{align} \ A L1
L2
L4
L3

[edit] Code example

A C function that implements the XOR swap algorithm:

 void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

Note that the code does not swap the integers passed immediately, but first checks if their memory addresses are distinct. This is because the algorithm works only when x and y refer to distinct locations (otherwise, it will erroneously set *x = *y = 0).

The body of this function is sometimes seen incorrectly shortened to if (x != y) *x^=*y^=*x^=*y;. This code has undefined behavior, since it modifies the lvalue *x twice without an intervening sequence point.

[edit] Reasons for use in practice

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include:

  • On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes;
  • In a region with high register pressure, it may allow the register allocator to avoid spilling a register.
  • In Microcontrollers where available RAM is very limited.

Because these situations are rare, most optimizing compilers do not generate XOR swap code.

[edit] Reasons for avoidance in practice

Most modern compilers can optimize away the temporary variable in the naive swap, in which case the naive swap uses the same amount of memory and the same number of registers as the XOR swap and is at least as fast, and often faster.[2] The XOR swap is also much less readable, and can be completely opaque to anyone who isn't already familiar with the technique.

Full article ▸

related documents
Block cipher
Symmetric-key algorithm
Transfer function
Abstract Syntax Notation One
Object-relational database
Lazy evaluation
Grep
Mathematica
XSL Transformations
SECD machine
B-tree
Queue (data structure)
Spaghetti code
Oracle machine
Unicity distance
Referential transparency (computer science)
Information retrieval
Nial
P-complete
Diffie-Hellman key exchange
Lagrange inversion theorem
Consistency
Quotient group
Statistical independence
Elementary group theory
Legendre symbol
Functional analysis
Tree (graph theory)
Axiom of pairing
Examples of groups