The exclusive or (xor) operator can be used to swap values from one register to another, without the need of a third register for temporary storage. Here's how in 3 steps:
R1|R2, result to R2
R1|R2, result to R1
R1|R2, result to R2
Suppose for example that R1 contains a 0 in the ith place and that R2 contains a 1 in the same place. Then after the first xor, R2 is loaded with a 1. So R1 = 0 and R2 = 1, as before. After the second xor, R1 is loaded with a 1. So R1 = 1 and R2 = 1. After the third, R2 is loaded with a 0. So R1 = 1 and R2 = 0, and we have successfully swapped the values. It turns out that this works for all possible initial values of R1 and R2.
Here's the logic in the general case: Let A be an arbitrary bit in the first register, and B be the corresponding arbitrary bit in the second register.
We assert that A ⇔ B | (A | B) and that B ⇔ A | (B | (A | B)).
To Prove: B | (A | B) ⇔ A
The proof is a bit of a bear, but it's also a good review of elementary logic.
expand xor
B | (A | B) ⇔ B | ((A ∧ ¬B) ∨ (¬A ∧ B))
⇔ (B ∧ ¬((A ∧ ¬B) ∨ (¬A ∧ B))) ∨ (¬B ∧ ((A ∧ ¬B) ∨ (¬A ∧ B)))
de Morgan's
⇔ (B ∧ (¬(A ∧ ¬B) ∧ ¬(¬A ∧ B))) ∨ (¬B ∧ ((A ∧ ¬B) ∨ (¬A ∧ B)))
⇔ (B ∧ ((¬A ∨ B) ∧ (A ∨ ¬B))) ∨ (¬B ∧ ((A ∧ ¬B) ∨ (¬A ∧ B)))
associativity
⇔ ((B ∧ (¬A ∨ B)) ∧ (A ∨ ¬B)) ∨ (¬B ∧ ((A ∧ ¬B) ∨ (¬A ∧ B)))
identities
⇔ (B ∧ A) ∨ (¬B ∧ ((A ∧ ¬B) ∨ (¬A ∧ B)))
distribution
⇔ (B ∧ A) ∨ ((¬B ∧ (A ∧ ¬B)) ∨ (¬B ∧ (¬A ∧ B)))
associativity and commutativity
⇔ (B ∧ A) ∨ (((¬B ∧ ¬B) ∧ A) ∨ ((¬B ∧ B) ∧ ¬A))
identities
⇔ (B ∧ A) ∨ (¬B ∧ A)
distribution
⇔ (B ∨ ¬B) ∧ A
identity
⇔ A
QED
To Prove: (A | B) | (B | (A | B)) ⇔ B
Using the above result twice, we have
(A | B) | (B | (A | B)) ⇔ (A | B) | A ⇔ A | (A | B) ⇔ B
QED
Note that we have used the following relations:
de morgan's laws | tautologies | |
¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y |
X ∨ (X ∧ Y) ⇔ X ⇔ X ∧ (X ∨ Y)
X ∨ (¬X ∧ Y) ⇔ X ∨ Y X ∧ (¬X ∨ Y) ⇔ X ∧ Y |
|
identities | distributive and associative laws | |
X ∧ X ⇔ X
X ∨ X ⇔ X X ∧ ¬X ⇔ false X ∨ ¬X ⇔ true |
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z) X ∨ (Y ∨ Z) ⇔ (X ∨ Y) ∨ Z X ∧ (Y ∧ Z) ⇔ (X ∧ Y) ∧ Z |
Source: Any text on elementary symbolic logic