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 source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“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)
“Rather would I have the love songs of romantic ages, rather Don Juan and Madame Venus, rather an elopement by ladder and rope on a moonlight night, followed by the father’s curse, mother’s moans, and the moral comments of neighbors, than correctness and propriety measured by yardsticks.”
—Emma Goldman (1869–1940)