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 insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
—Charles Baudelaire (1821–1867)
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious life’s a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (1647–1680)
“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)