## 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:
else:
return t

A=111 B=101
t=010
u=1010
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:
t=1000
u=0100
then since u is still not 0 add is called again:
t = 1100
u=0000
now u is 0 so the program is done and returns t which is 1100. Note that 111+101 = 1100 is 7+5=12.