Binary Addition

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:

X	Y		Z0
0	0		0
0	1		1
1	0		1
1	1		0

What Boolean operation does that look like? XOR.

The function for the next digit will have to satisfy this truth table:

X	Y		Z1
0	0		0
0	1		0
1	0		0
1	1		1

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 Z₁Z₀, where Z₁ = X AND Y, and Z₀ = 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:

X1	Y1	C		Z1
0	0	0		0
0	1	0		1
1	0	0		1
1	1	0		0
0	0	1		1
0	1	1		0
1	0	1		0
1	1	1		1

X1	Y1	C		Z2
0	0	0		0
0	1	0		0
1	0	0		0
1	1	0		1
0	0	1		0
0	1	1		1
1	0	1		1
1	1	1		1

So, Z₁ = X₁ XOR Y₁ XOR C and Z₂ = (X₁ AND Y₁) OR (X₁ AND C) OR (Y₁ 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 = X₀ AND Y₀.

Each subsequent bit works just like the second, with the second bit of the previous result being carried over. Generally, and Z_n = (X_n AND Y_n) OR (X_n AND C_n-1) OR (Y_n AND C_n-1), and C_n = X_n XOR Y_n XOR C_n-1.

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