Xor swap algorithm

Encyclopedia : X : XO : XOR : 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 B) XOR B = A, for every pair (A, B). The XOR swap has few advantages on modern computers—in fact, it may even be slower than performing the swap using a temporary variable.

Contents

1 The algorithm
2 Explanation
3 Code examples

3.1 Pascal
3.2 C

4 Reasons for use in practice
5 Reasons for avoidance in practice
6 See also

The algorithm

Standard swapping algorithms require the use of temporary storage. Here is one such algorithm to swap x and y:

Copy the value of y to temporary storage: temp ← y
Assign y to get the value of x: y ← x
Assign x to get the temporary storage value: x ← temp

Or, if given two variables x and y of type integer, an arithmetic algorithm to swap them without using any temporary storage goes as follows:

x := x + y
y := x - y
x := x - y

The above algorithm breaks down on systems that trap integer overflow. Also, when x and y are aliased to the same storage location the result is to zero out that location. Using the XOR swap algorithm, however, neither temporary storage nor the absence of overflow detection are needed. The algorithm is as follows:

x := x XOR y
y := x XOR y
x := x XOR y

(However, the problem still remains that if x and y use the same storage location, the values will be zeroed out.) The algorithm typically corresponds to three machine code instructions. For example, in IBM System/370 assembly 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.

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

Pascal

A Pascal procedure to swap two integers using the xor swap algorithm:

procedure XorSwap(var X, Y: Integer);
begin
if X <> Y then begin
X := X xor Y;
Y := X xor Y;
X := X xor Y;
end;
end;

C

A C function that implements the xor swap algorithm:

void xorSwap (int *x, int *y)

}

The body of this function is often seen reduced to "if (x != y) *x^=*y^=*x^=*y;". This is however not valid C, because of a lack of sequence points.

Reasons for use in practice

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. On some architectures, certain operations require their operands to be in particular registers, requiring a swap; and all available "temporary" registers may be in use storing other data. Some optimizing compilers can generate code using the xor swap algorithm in these situations.

This trick could also be used by someone trying to win the International Obfuscated C Code Contest, since it is somewhat obscure.

Reasons for avoidance in practice

On modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute commands in parallel; see Instruction pipeline. In the XOR technique, the inputs to each operation depend on the results of the previous operation, 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.

Modern optimizing compilers work by translating the code they are given into an internal flow-based representation which they transform in many ways before producing their machine-code output. These compilers are more likely to recognize and optimize a conventional (temporary-based) swap than to recognize the high-level language statements that correspond to an xor swap. Many times, what is written as a swap in high-level code is translated by the compiler into a simple internal note that two variables have swapped memory addresses, rather than any amount of machine code. Other times, when the target architecture supports it, the compiler can use a single XCHG (exchange) instruction which performs the swap in a single operation.

An XCHG operation was available as long ago as 1964, on the PDP-6 (where it was called EXCH) and in 1970 on the Datacraft 6024 series (where it was called XCHG). The Intel 8086, released in 1986, also included an instruction named XCHG. All three of these instructions swapped registers with registers, or registers with memory, but were unable to swap the contents of two memory locations. The Motorola 68000's EXG operation can only swap registers with registers. The PDP-10 inherited the PDP-6's EXCH instruction, but the PDP-11 (the machine on which the C programming language was developed) did not.

The xor swap is also complicated in practice by aliasing. As noted above, if an attempt is made to xor-swap the contents of some location with itself, the result is that the location is zeroed out and its value lost. Therefore, xor swapping must not be used blindly, in a high-level language, if aliasing is possible.

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.