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 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)
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (1817–1862)
“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)