CACTUSPEAR.ORG PRESENTS

xor

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 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

Proof: 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

Proof: 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


cactuspear home
comments to comments at cactuspear dot org