- XOR swap algorithm
In
computer programming , the XOR swap is analgorithm that uses the XORbitwise operation to swap distinct values ofvariable s having the samedata type without using a temporary variable.The algorithm
Standard swapping algorithms require 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. For example, in IBMSystem/370 assembly code: XR R1,R2 XR R2,R1 XR R1,R2where R1 and R2 are registers and each XR operation leaves its result in the register named in the first argument.However, the problem still remains that if "x" and "y" use the same storage location, 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.)
Proof that the XOR swap works
The
binary operation XOR over bit strings of length exhibits the following properties (where denotes XOR): [The first three properties, along with the existence of an inverse for each element, are the definition of anAbelian group . The last property is a structural feature of XOR not necessarily shared by other Abelian groups, nor groups in general.]
* L1. Commutativity:
* L2.Associativity :
* L3. Identity exists: there is a bit string, 0, (of length "N") such that for any
* L4. Each element is its own inverse: for each , .Suppose that we have two registers
R1
andR2
, 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.Code example
A C function that implements the XOR swap algorithm: Note that the code does not swap the integers passed immediately, but first checks if their memory locations are distinct. This will remove problems caused by possible aliasing.
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 thelvalue *x
twice without an interveningsequence point .Reasons for use in practice
The algorithm is not uncommon in embedded assembly code,Fact|date=July 2007 where there is often very limited space available for a temporary swap variable, and this form of swap can also avoid a load/store which can be much faster than the equivalent operation using a temporary variable. 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 XOR swap in these situations.Fact|date=April 2007
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. [http://big-bad-al.livejournal.com/98093.html] As a general rule, you should never use the XOR swap unless you know for a fact that the naive swap will not suit your application (which is very rare in this day and age). The XOR swap is also much less readable, and can be completely opaque to anyone who isn't already familiar with the technique.
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.The XCHG instruction
Modern
optimizing compiler s 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 theDatacraft 6024 series (where it was called XCHG). TheIntel 8086 , released in 1978, 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. TheMotorola 68000 's EXG operation can only swap registers with registers. ThePDP-10 inherited the PDP-6's EXCH instruction, but thePDP-11 (the machine on which the C programming language was developed) did not.However, the XCHG instruction in modern processors (e.g. x86) should only be used to swap registers and not memory, as an implicit "LOCK" instruction may be imposed by the processor on the memory location(s) involved so that the operation is atomic.
Aliasing
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.
Variations
The underlying principle of the XOR swap algorithm can be applied to any reversible binary operation. Replacing XOR by addition and subtraction gives a slightly different, but largely equivalent, formulation:
Unlike the XOR swap, this variation requires that the underlying processor or programming language uses a method such as
modular arithmetic orbignum s to guarantee that the computation ofX + Y
cannot cause an error due tointeger overflow . Therefore, it is seen even more rarely in practice than the XOR swap.Notes
ee also
*
Symmetric difference
*XOR linked list
Wikimedia Foundation. 2010.