Wednesday, December 28, 2011

From boolean algebra to regular algebra

Consider the following two tables, the first shows the bitwise XOR function for the first few binary numbers and the second shows the same table converted to decimal:
Bitwise Xor is defined as you look at the two numbers say (0010 and 1011) and a new number is formed that has a 1 in position i if the ith digit of either of the two starting numbers is 1 but not both. So for 0010 and 1011 XOR would give 1001.
There are 16 of these basic bitwise logical functions, another one is AND which gives a 1 in each position if both of the starting numbers have a 1 in that position. 
I'll also define one more the bitshift which takes say L(111) and produces 1110 which is just the original number with a 0 added onto the end. 
From these 3 basic operations we can define addition as the program:
  t = XOR(A,B)
  u = L(AND(A,B))
  if u not equal to 0:
    add(t, u)
    return t

For example adding these:
A=111 B=101 
where t is XOR(A,B) and u is AND(A,B) but shifted 1 position to the left. Then add is called on this t and u, to get:
then since u is still not 0 add is called again:
t = 1100 
now u is 0 so the program is done and returns t which is 1100. Note that 111+101 = 1100 is 7+5=12.

No comments:

Post a Comment