In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap distinct values of variables having the same data type without using a temporary variable. Programming redirects here. ... Flowcharts are often used to graphically represent algorithms. ... Exclusive disjunction, also known as exclusive or and symbolized by XOR or EOR, is a logical operation on two operands that results in a logical value of true if and only if one of the operands, but not both, has a value of true. ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ... It has been suggested that this article or section be merged with XOR swap algorithm. ... In computer science and mathematics, a variable (pronounced ) (sometimes called an object or identifier in computer science) is a symbolic representation used to denote a quantity or expression. ... In programming languages a data type defines a set of values and the allowable operations on those values[1]. For example, in the Java programming language, the int type represents the set of 32-bit integers ranging in value from -2,147,483,648 to 2,147,483,647, and...

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 Y 

The algorithm typically corresponds to three machine code instructions. For example, in IBM System/370 assembly code: Machine code or machine language is a system of instructions and data directly executed by a computers central processing unit. ... IBM logo The IBM System/370 (often: S/370) was a model range of IBM mainframes announced on June 30, 1970 as the successors to the System/360 family. ...

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

where R1 and R2 are registers and each XR operation leaves its result in the register named in the first argument. In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to frequently used values—typically, these values are involved in multiple expression evaluations occurring within a small region on the program. ...

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 XOR swap works

The binary operation XOR over bit strings has the following properties (where denotes XOR): In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ...

• L1. Commutativity:
• L2. Associativity:
• L3. Identity exists: there is a value 0 such that for any A
• L4. Each element has an inverse: for each A, there is a value such that
  • L4a. In fact, each element is its own inverse: .

The first four properties are the definition of an Abelian group. The last is a structural feature of XOR not necessarily shared by other Abelian groups or groups in general. Due to this last property, one can derive the following division theorem of XOR: Mathematical meaning A map or binary operation is said to be commutative when, for any x in A and any y in B . ... In mathematics, associativity is a property that a binary operation can have. ... For other uses, see identity (disambiguation). ... In mathematics, the inverse of an element x, with respect to an operation *, is an element x such that their compose gives a neutral element. ... In mathematics, an abelian group, also called a commutative group, is a group (G, * ) with the additional property that * commutes: for all a and b in G, a * b = b * a. ... This picture illustrates how the hours on a clock form a group under modular addition. ... This picture illustrates how the hours on a clock form a group under modular addition. ...

Given two bit strings A and B of equal length, there exists the unique XOR-product Y of A and B, written as

Because each string of bits is its own inverse under XOR, we can derive the following in the spirit of division: In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ...

(XOR-product definition)

(self-inverse; L4a)

(left-apply A)

(inverse; L4)

(identity; L1 & L3)

Therefore B is the XOR-quotient of A and Y.

This argument applies just the same if B is substituted for A and vice versa.

Suppose that we have two 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 property list above.

Step	Operation	Register 1	Register 2	Reduction
1	Initial value			—
2	R1 := R1 XOR R2			—
3	R2 := R1 XOR R2			L2 L4a L3
4	R1 := R1 XOR R2			L1 L2 L4a L3

Code example

A C function that implements the XOR swap algorithm: C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

 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 locations are distinct. This will remove problems caused by possible aliasing. In computing, aliasing is a term that generally means that one variable or some reference, when changed, has an indirect (usually unexpected) effect on some other data. ...

The body of this function is sometimes seen incorrectly shortened to if (x != y) *x^=*y^=*x^=*y;. This may not obtain desired result because of a lack of sequence points; No evaluation order was given for the assignments. A sequence point in a programming language defines any point in a computer programs execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed. ...

Reasons for use in practice

The algorithm is not uncommon in embedded assembly code, 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.^{[citation needed]} Compiler optimization is the process of tuning the output of a compiler to minimize some attribute (or maximize the efficiency) of an executable program. ...

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. Basic five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back) An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput (the number of instructions that...

The XCHG instruction

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. Compiler optimization techniques are optimization techniques that have been programmed into a compiler. ... In computing, an intermediate representation is a data structure that is constructed from input data to a program, and from which part or all of the output data of the program is constructed in turn. ...

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 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. 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 PDP-6 (Programmed Data Processor-6) was a computer model developed by Digital Equipment Corporation (DEC) in 1963. ... The 8086[1] is a 16-bit microprocessor chip designed by Intel in 1978, which gave rise to the x86 architecture. ... The Motorola 68000 is a 16/32-Bit [1] CISC microprocessor core designed and marketed by Freescale Semiconductor (formerly Motorola Semiconductor Products Sector). ... The PDP-10 was a computer manufactured by Digital Equipment Corporation (DEC) from the late 1960s on; the name stands for Programmed Data Processor model 10. It was the machine that made time-sharing common; it looms large in hacker folklore because of its adoption in the 1970s by many... The PDP-11 was a 16-bit minicomputer sold by Digital Equipment Corp. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

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. Intel Pentium 4 (Northwood version), one example out of a huge number of x86 implementations from Intel, AMD, and others. ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to frequently used values—typically, these values are involved in multiple expression evaluations occurring within a small region on the program. ... RAM redirects here. ... In computer science, an atomic operation is an operation during which a processor can simultaneously read a location and write it in the same bus operation. ...

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. In computing, aliasing is a term that generally means that one variable or some reference, when changed, has an indirect (usually unexpected) effect on some other data. ...

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:

 procedure AddSwap (var X, Y: integer); begin if X <> Y then begin X := X + Y; Y := X - Y; X := X - Y end end 

Unlike the XOR swap, this variation requires that the underlying processor or programming language uses a method such as modular arithmetic or bignums to guarantee that the computation of X + Y cannot cause an error due to integer overflow. Therefore, it is seen even more rarely in practice than the XOR swap. Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... A bignum package in a computer or program allows internal representation of very large integers, rational numbers, decimal numbers, or floating-point numbers (limitted only by available memory), and provides a set of arithmetic operations on such numbers. ... In computer programming, an integer overflow is an anomalous condition which may cause a buffer overflow, resulting in a computer security risk where adjacent, valid program control data may be overwritten, permitting the execution of arbitrary, and potentially harmful code. ...

See also

• Symmetric difference
• XOR linked list