Added to Favorites

Related Searches

Definitions

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.
## 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:
## Proof that the XOR swap works

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

## Code example

A C function that implements the XOR swap algorithm:

X := X XOR Y

Y := X XOR Y

X := X XOR YThe algorithm typically corresponds to three machine code instructions. For example, in IBM System/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.)

- L1. Commutativity: $A\; oplus\; B\; =\; B\; oplus\; A$
- L2. Associativity: $(A\; oplus\; B)\; oplus\; C\; =\; A\; oplus\; (B\; oplus\; C)$
- L3. Identity exists: there is a bit string, 0, (of length N) such that $A\; oplus\; 0\; =\; A$ for any $A$
- L4. Each element is its own inverse: for each $A$, $A\; oplus\; A\; =\; 0$.

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 06, 2008 at 22:10:02 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 06, 2008 at 22:10:02 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.