Unit 5: Adding

Adding one bit to one bit

There are only four sums to worry about:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 — that is two, so write 0 and carry 1.

So the answer needs two wires out: the digit you write (sum) and the one you carry (carry).

That is the whole chip

An Xor and an And, side by side. That is a half adder — half, because it can add two bits but has nowhere to put a carry *coming in* from the column before.

HDL

CHIP HalfAdder {
    IN a, b;
    OUT sum, carry;
    PARTS:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

TABLE HalfAdder;

It prints

a b | sum carry
0 0 | 0   0
0 1 | 1   0
1 0 | 1   0
1 1 | 0   1

Three bits at a time

In every column except the first, you have three things to add: the two digits, plus whatever was carried in.

So do it in two goes. Add a and b with a half adder. Then add the carry-in to that result with another half adder. If either step carried, the column carries — so Or the two carries together.

HDL

CHIP FullAdder {
    IN a, b, c;
    OUT sum, carry;
    PARTS:
    HalfAdder(a=a, b=b, sum=s1, carry=c1);
    HalfAdder(a=s1, b=c, sum=sum, carry=c2);
    Or(a=c1, b=c2, out=carry);
}

TABLE FullAdder;

It prints

a b c | sum carry
0 0 0 | 0   0
0 0 1 | 1   0
0 1 0 | 1   0
0 1 1 | 0   1
1 0 0 | 1   0
1 0 1 | 0   1
1 1 0 | 0   1
1 1 1 | 1   1

A row of adders, holding hands

To add two four-bit numbers, do what you do on paper: start at the ones column and let each carry fall into the next column along.

The ones column has no carry coming in, so it gets a half adder. The other three get full adders, each one taking the carry from its neighbour.

HDL

CHIP Adder {
    IN a3, a2, a1, a0, b3, b2, b1, b0;
    OUT s3, s2, s1, s0, carry;
    PARTS:
    HalfAdder(a=a0, b=b0, sum=s0, carry=k0);
    FullAdder(a=a1, b=b1, c=k0, sum=s1, carry=k1);
    FullAdder(a=a2, b=b2, c=k1, sum=s2, carry=k2);
    FullAdder(a=a3, b=b3, c=k2, sum=s3, carry=carry);
}

USE Adder;
SET a3=0, a2=1, a1=0, a0=1, b3=0, b2=0, b1=1, b0=1;
SHOW;

It prints

s3=1 s2=0 s1=0 s0=0 carry=0

The most useful sum of all

Adding 1 is what a computer does more than anything else — every loop, every step through a program.

There is no special chip for it. You already have an adder: just wire the number 0001 into its other side. A constant is written straight into the wiring as 0 or 1.

HDL

CHIP Inc {
    IN i3, i2, i1, i0;
    OUT o3, o2, o1, o0;
    PARTS:
    Add4(a3=i3, a2=i2, a1=i1, a0=i0, b3=0, b2=0, b1=0, b0=1,
         s3=o3, s2=o2, s1=o1, s0=o0);
}

USE Inc;
SET i3=0, i2=1, i1=1, i0=1;
SHOW;
SET i3=1, i2=1, i1=1, i0=1;
SHOW;

It prints

o3=1 o2=0 o1=0 o0=0
o3=0 o2=0 o1=0 o0=0

Look what you have

Every gate in that adder came from a Nand. Nothing was added from outside — no arithmetic was ever built in.

You started with one gate that says "not both", and out the other end came addition. Next you will make one chip do several jobs at once, and that is a CPU’s calculator.