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:

    There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.
    François, Duc De La Rochefoucauld (1613–1680)

    If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.
    Herman Melville (1819–1891)

    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)