Monday, October 24, 2011

XOR trivialities

XOR trivialities

Shortcuts for XOR and XNOR

The classical formula for XOR on two variables remains

result = a.b' + b.a'

(where . means logical AND and + means logical OR and ' means logical NOT).

On the possible set of values, the table becomes something like :

a b result
0 0 0
0 1 1
1 0 1
1 1 0

which boils down to the interpretation of ANY BUT NOT ALL. This holds true for any no of variables in question, i.e.,
a ^ b ^ c ^ d ^ e ^ ....... x ^ y ^ z = 0
(iff all a, b, c ... z == 0|1 together. And ^ denotes XOR operation.)

So when it comes to applying an XOR formula to 2 variables, say a & b and storing their result in a variable, say x.

The starting point would be
x = (a AND !b) OR (b AND !a).

While this is correct, problems may arise when a & b are themselves functions which return true/false. In this case, the functions a & b would be executed twice just to compute the value of x. In cases where this may not be desired, we could stick to the short hand equivalent for XOR.

x = (a != b)

Which says that the result will be 1(true) only when both the variables are not the same, as can be inferred from the truth table above.

It solves many problems:
  • Reduces typing effort
  • Doesn't evaluate functions twice
  • Reduces complexity when a & b themselves become large expressions.
  • Makes code easy to read and understand and maintain
Similar interpretation could be extended to the function XNOR, which in its formula looks like:

result = (a XOR b)', where ' means logical complement.

  result = (a.b' + b.a')'
         = (a'+b) . (b'+a)
         = a'b' + b.b' + b.a + a'.a
         = a.b + a'.b'

In plain words, we could simply derive that
  a XNOR b  = !(a XOR b)
            = !(a != b)
a XNOR b = (a == b)

But for the curious reader, the truth table should be enough proof:

Taking the derived formula
result = a.b + a'.b'

a b result
0 0 1
0 1 0
1 0 0
1 1 1

Readers to this point can observe that the result is 1(true) only when (a == b).

No comments:

Post a Comment