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 proof of a poet is that his country absorbs him as affectionately as he has absorbed it.
    Walt Whitman (1819–1892)

    War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.
    M.F.K. Fisher (1908–1992)

    What will happen once the authentic mass man takes over, we do not know yet, although it may be a fair guess that he will have more in common with the meticulous, calculated correctness of Himmler than with the hysterical fanaticism of Hitler, will more resemble the stubborn dullness of Molotov than the sensual vindictive cruelty of Stalin.
    Hannah Arendt (1906–1975)