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:
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)
“The surest guide to the correctness of the path that women take is joy in the struggle. Revolution is the festival of the oppressed.”
—Germaine Greer (b. 1939)