Wednesday, June 7, 2017

Swamping two variables without temporary variable

Based on the Boolean Algebra, where XOR operator is commutative and associative:

A = A ⊕ B
B = B ⊕ A = B ⊕ (A ⊕ B) = B ⊕ (B ⊕ A) = (B ⊕ B) ⊕ A
  = 0 ⊕ A = A
A = A ⊕ B = (A ⊕ B) ⊕ A = B ⊕ (A ⊕ A) = B

So the steps are:

A = A^B;
B = B^A;
A = A^B;

Another way is by doing arithmetics:

A = A - B;
B = A + B;
A = B - A;

Or
A = A + B;
B = A - B;

A = A - B;

If we look at carefully, the XOR operator is actually a half-adder operation (with carry bit).

A ⊕ B = A' * B + A * B', where if A=1 the result would be equal to B', else equal to B.

No comments:

Post a Comment