Switches that cannot count
A shop's till adds a 6 pound sandwich to a 3 pound drink in a few billionths of a second. Yet nothing inside the processor can count.
Each tiny part only answers a yes or no question about two bits. This lesson builds addition out of those questions.
By the end of this lesson
Note
I can build an adder from logic gates.
Key words
| Word | What it means |
|---|---|
| Logic gate | a circuit that turns one or two input bits into one output bit |
| Truth table | a list of every input and the output it gives |
| Carry | the bit passed to the next place when a sum is too big |
| Half adder | two gates that add two bits |
| Full adder | gates that add two bits and a carry |
| Overflow | an answer too big for the bits kept |
The cells students fill in are left blank in this preview.
Four gates answer questions about bits
A logic gate takes bits in and gives one bit out. AND gives 1 only when both inputs are 1. OR gives 1 when either input is 1, or both. XOR, exclusive or, gives 1 when the inputs differ. NOT has one input and flips it.
A truth table lists every input with its output. Two inputs have only four cases, so the table is short.
Truth table: three gates
| A | B | A AND B | A OR B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
The cells students fill in are left blank in this preview.
Go to the architecture folder
cd ~/archShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Apply the gates to 6 and 3
python3 -c "print(6 & 3, 6 | 3, 6 ^ 3)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: the gates, bit by bit
| Bits | Number | |
|---|---|---|
| A | 0110 | 6 |
| B | 0011 | 3 |
| A AND B | 0010 | 2 |
| A OR B | 0111 | 7 |
| A XOR B | 0101 | 5 |
The cells students fill in are left blank in this preview.
Two gates add two bits
Adding two bits has four cases. 0 + 0 is 0, and 0 + 1 and 1 + 0 are 1. But 1 + 1 is 2, written 10 in binary.
The right-hand bit of the answer is A XOR B. The left-hand bit, the carry, is A AND B. So one XOR gate and one AND gate make a half adder.
Truth table: a half adder
| A | B | Sum (XOR) | Carry (AND) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
The cells students fill in are left blank in this preview.
XOR is the sum without the carries
python3 -c "print(6 + 3, 6 ^ 3, (6 & 3) << 1)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A full adder takes the carry in
Every place except the first must also add the carry from the place to its right. So it adds three bits.
A full adder does that with two half adders and an OR gate. Chain four of them and you can add 4-bit numbers. The carry ripples from right to left, one full adder to the next, so this design is called a ripple-carry adder.
Worked example: 0110 + 0011, right to left
| Place | A | B | Carry in | Sum | Carry out |
|---|---|---|---|---|---|
| 1s | 0 | 1 | 0 | 1 | 0 |
| 2s | 1 | 1 | 0 | 0 | 1 |
| 4s | 1 | 0 | 1 | 0 | 1 |
| 8s | 0 | 0 | 1 | 1 | 0 |
The cells students fill in are left blank in this preview.
When the answer does not fit
An adder keeps a fixed number of bits. For unsigned numbers, a carry out of the top place is lost, and the answer wraps round.
For signed numbers the test is different. 0110 + 0011 is 9, but in 4-bit two's complement 1001 reads as -7. Two positive numbers gave a negative answer. That is overflow too, although nothing carried out of the top.
Write a program that adds 200 and 100
printf '.globl _start\n_start:\n li a0, 200\n li a1, 100\n add a0, a0, a1\n li a7, 93\n ecall\n' > big.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Assemble it
riscv64-linux-gnu-as big.s -o big.oShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Link it
riscv64-linux-gnu-ld big.o -o bigShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Run it on the emulator
qemu-riscv64 ./bigShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read the exit status
echo $?Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think overflow always means a carry came out of the top. That is true only for unsigned numbers. In two's complement, 1111 + 0001 carries out, yet -1 + 1 = 0 is right. Signed overflow happens when both inputs have the same sign and the answer has the other sign.
Going further: subtracting with an adder
A processor has no separate circuit for subtraction. It works out a - b as a + (NOT b) + 1, because NOT b + 1 is -b in two's complement.
Write subtract(a, b) with your add: flip every bit of b, add it to a, then add 0001. Try 0101 - 0011 and 0011 - 0101. Then say how hardware could save the second addition.