Monday, November 24, 2014

Before, I talked about how to use binary to represent a number using only two values. But what if you want to actually do something with those numbers? How do you add numbers using Boolean operations?

Well, let's start with a simple case: adding two one-bit numbers. We'll call them X and Y, and since they each only have one binary digit they can only have the values 0 or 1. So here are the cases we need to account for: 0+0=0, 0+1=1, 1+0=1, 1+1=10.

Notice the answer for that final case has two digits. A Boolean function can only return one value, so how can get that? By having two functions, one for each digit.

So, the function for the rightmost digit has to satisfy this truth table:
XYZ0
000
011
101
110
What Boolean operation does that look like? XOR.

The function for the next digit will have to satisfy this truth table:
XYZ1
000
010
100
111
That's the same as the AND operation.

I'm using the subscripts here to indicate which digit in the overall number. So our two bit answer Z has the individual bits Z1Z0, where Z1 = X AND Y, and Z0 = X XOR Y;

So, that's how you can add two one-bit numbers. But what if you want to add bigger numbers? Well, the way you add the second bits together is pretty much the same as the first bits, with one major difference: You need to account for the bit that got carried from the sum of the first bits. If that carry bit was 0, then the result of the next bit will be same as the first. But if it's one, then the result is increased by one. So, 0+0+1=1, 0+1+1=10, 1+0+1=10, 1+1+1=11.
So, now we have these two truth tables:
X1Y1CZ1
0000
0101
1001
1100
0011
0110
1010
1111
X1Y1CZ2
0000
0100
1000
1101
0010
0111
1011
1111
So, Z1 = X1 XOR Y1 XOR C and Z2 = (X1 AND Y1) OR (X1 AND C) OR (Y1 AND C). C, the carry bit, comes from the second bit of the result of the sum of the first two bits, that is C = X0 AND Y0.

Each subsequent bit works just like the second, with the second bit of the previous result being carried over. Generally, and Zn = (Xn AND Yn) OR (Xn AND Cn-1) OR (Yn AND Cn-1), and Cn = Xn XOR Yn XOR Cn-1.

Here's another challenge for you: How do you do subtraction in a similar manner?