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:
“When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
—Stephanie Martson (20th century)
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“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)