XOR Swap Algorithm - Proof of Correctness

Proof of Correctness

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

  • 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 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
1 R1 := R1 XOR R2
2 R2 := R1 XOR R2 L2
L4
L3
3 R1 := R1 XOR R2 L1
L2
L4
L3

Read more about this topic:  XOR Swap Algorithm

Famous quotes containing the words proof of, proof and/or correctness:

    The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.
    Charles Baudelaire (1821–1867)

    The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!
    Lenny Bruce (1925–1966)

    With impressive proof on all sides of magnificent progress, no one can rightly deny the fundamental correctness of our economic system.
    Herbert Hoover (1874–1964)