Embercode: AI-powered software engineer course

Why this matters

When a program runs a + b, the arithmetic is done by circuits inside the CPU. The CPU has no separate "maths brain" that works in a different way. It uses the same logic gates from the previous lesson, wired together so the output of one gate feeds the input of the next.

This lesson builds the smallest useful version of that circuit. It adds two numbers of four bits each. Once you see how the carry passes from one column to the next, several common bugs make sense: numbers that wrap around, results that are too small, and a carry that gets lost. The lesson on logic gates covered AND, OR, NOT and XOR. Here you will only combine them.

The idea is the same at any width. A 64-bit adder is a chain of 64 full adders, one per column. The chain is longer, but each column still does the same three-input job.

Adding in binary, one column at a time

You already know the binary rules from the binary lesson: 0 plus 0 is 0, 0 plus 1 is 1, and 1 plus 1 is 10 in binary, which is two. The last case writes a 0 in the current column and carries a 1 to the column on the left.

Here is 5 plus 3 written in binary, one column per bit. The bits are written from the most significant on the left to the least significant on the right.

  0101     5
+ 0011     3
------
  1000     8

Add it from the right, one column at a time.

Rightmost column: 1 plus 1 is 10. Write 0 and carry 1.
Second column: 0 plus 1 plus the carry 1 is 10. Write 0 and carry 1.
Third column: 1 plus 0 plus the carry 1 is 10. Write 0 and carry 1.
Leftmost column: 0 plus 0 plus the carry 1 is 1. Write 1 and carry 0.

The result is 1000, which is 8. Notice that each column has three things to add: a bit from the first number, a bit from the second number, and a carry from the column on the right. A circuit that does one column needs three inputs and two outputs. The outputs are the sum bit for the column and the carry bit for the next column.

The half adder: two bits in

A half adder adds two bits and ignores any carry coming in from the right. It is the simplest part of an adder, and it is the starting point for the full adder.

The half adder has two inputs, a and b, and two outputs, sum and carry. The rules are:

The sum is 1 when exactly one input is 1. That is the XOR rule.
The carry is 1 only when both inputs are 1. That is the AND rule.

In words: a and b go into an XOR gate, and its output is the sum. The same a and b also go into an AND gate, and its output is the carry.

a	b	sum (XOR)	carry (AND)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Worked example. Add 1 and 1 with a half adder. The sum is XOR(1, 1), which is 0. The carry is AND(1, 1), which is 1. Together they read as binary 10, which is 2. The output matches 1 plus 1.

A half adder cannot handle a column that has a carry coming in. For that you need a third input.

The full adder: add the carry from the right

A full adder adds three bits: a, b, and the carry from the column on the right. Its outputs are the sum bit for this column and the carry bit for the column on the left. It is built from two half adders and one OR gate.

The steps are:

The first half adder takes a and b. It gives a partial sum, which I will call s1, and a carry, which I will call c1.
The second half adder takes s1 and the carry in. It gives the final sum bit and a second carry, which I will call c2.
The OR gate takes c1 and c2. Its output is the carry out for this column.

Why is OR enough to combine the two carries? Because c1 and c2 can never both be 1 at the same time. The first carry is 1 only when a and b are both 1. In that case s1 is 0, so the second half adder gets 0 for one of its inputs and its carry is 0. A plain OR is therefore enough, and no extra gate is needed.

Worked example, with three inputs of increasing difficulty. Take a = 1, b = 1, and carry in = 1. The sum of the three bits is 3.

First half adder on 1 and 1: s1 = XOR(1, 1) = 0, c1 = AND(1, 1) = 1.
Second half adder on s1 = 0 and the carry in = 1: sum = XOR(0, 1) = 1, c2 = AND(0, 1) = 0.
Carry out = OR(c1, c2) = OR(1, 0) = 1.

The output is sum 1 and carry out 1. Together they read as binary 11, which is 3. That matches 1 plus 1 plus 1.

The block below defines the gates and the two adders, then prints the full adder's truth table for all eight rows. The table has three inputs, so there are 8 rows.

Python · editable

Output:

a b cin | sum cout
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

Check the row 0 1 1. The sum is 0 and the carry out is 1. That is right, because 0 plus 1 plus 1 is 2, which is binary 10. The sum bit is 0 and the carry is 1.

Chaining full adders into a 4-bit adder

One full adder handles one column. To add two whole numbers, you chain one full adder per column. The carry out of the rightmost column becomes the carry in of the next column to the left, and so on. The carry therefore ripples from right to left through the chain. A circuit built this way is called a ripple-carry adder.

For 4-bit numbers you need four full adders. The rightmost full adder gets a carry in of 0, because there is no column to its right. Each later one gets the carry from the one before it. The last carry out is the fifth bit of the answer. It is 1 only when the sum does not fit in 4 bits.

Each carry has to wait until the carry before it is ready, so a long chain takes longer to settle. Real CPUs therefore pass the carry through faster paths than a plain chain. They still produce the same bits as the chain does, so the chain is the right model for learning how the sum is built.

In the Python code, a number is stored as a list of bits with the least significant bit first. So the list [1, 0, 1, 0] means 1 in the ones column, 0 in the twos column, 1 in the fours column, and 0 in the eights column. That is 5. The helper to_bits makes this list from an ordinary number, and from_bits turns it back. >> moves a number's bits right and << moves them left, so (number >> i) & 1 picks out bit i.

Here is 5 plus 3, traced column by column, with the bits in the order used by the code.

Column 0 (ones): 1 plus 1 with carry in 0. Sum 0, carry out 1.
Column 1 (twos): 0 plus 1 with carry in 1. Sum 0, carry out 1.
Column 2 (fours): 1 plus 0 with carry in 1. Sum 0, carry out 1.
Column 3 (eights): 0 plus 0 with carry in 1. Sum 1, carry out 0.

The sum bits are 0, 0, 0, 1, which is 8. The final carry out is 0, so the answer fits in 4 bits.

Second example, with a carry out. Take 11 plus 6. Eleven is 1011 and six is 0110. In list form the first number is [1, 1, 0, 1] and the second is [0, 1, 1, 0]. Each column below takes one pair of bits and the carry from the column before it.

Column 0 (ones): 1 plus 0 with carry in 0. Sum 1, carry out 0.
Column 1 (twos): 1 plus 1 with carry in 0. Sum 0, carry out 1. This is the half adder table row 1 1.
Column 2 (fours): 0 plus 1 with carry in 1. Sum 0, carry out 1.
Column 3 (eights): 1 plus 0 with carry in 1. Sum 0, carry out 1.

The sum bits are 1, 0, 0, 0, which is 1. The carry out is 1, and it stands for 16, so the full answer is 17. The carry out of column 1 became the carry in of column 2, which is the ripple the name refers to.

The block below builds the 4-bit adder from the gates, runs 5 plus 3, runs 9 plus 9, checks all 256 pairs of 4-bit numbers against Python's +, and then shows four common mistakes. Each mistake is a separate line of output, so you can see what each one produces.

Python · editable

def XOR(a, b):
    return a ^ b

def AND(a, b):
    return a & b

def OR(a, b):
    return a | b

def half_adder(a, b):
    return XOR(a, b), AND(a, b)

def full_adder(a, b, carry_in):
    first_sum, first_carry = half_adder(a, b)
    second_sum, second_carry = half_adder(first_sum, carry_in)
    return second_sum, OR(first_carry, second_carry)

def to_bits(number, width):
    return [(number >> i) & 1 for i in range(width)]

def from_bits(bits):
    value = 0
    for i, bit in enumerate(bits):
        value += bit << i
    return value

def add_bits(a_bits, b_bits):
    if len(a_bits) != len(b_bits):
        raise ValueError(f"lengths differ: {len(a_bits)} and {len(b_bits)}")
    carry = 0
    result = []
    for a, b in zip(a_bits, b_bits):
        total, carry = full_adder(a, b, carry)
        result.append(total)
    return result, carry

print("5 + 3 in 4 bits")
sum_bits, carry = add_bits(to_bits(5, 4), to_bits(3, 4))
print("sum bits (LSB first):", sum_bits)
print("carry out:", carry)
print("sum =", from_bits(sum_bits))
print()

print("9 + 9 in 4 bits")
sum_bits, carry = add_bits(to_bits(9, 4), to_bits(9, 4))
print("sum bits (LSB first):", sum_bits)
print("carry out:", carry)
print("low 4 bits =", from_bits(sum_bits))
print("with the carry =", from_bits(sum_bits) + carry * 16)
print()

print("11 + 6 in 4 bits")
sum_bits, carry = add_bits(to_bits(11, 4), to_bits(6, 4))
print("sum bits (LSB first):", sum_bits)
print("carry out:", carry)
print("with the carry =", from_bits(sum_bits) + carry * 16)
print()

failures = 0
for a in range(16):
    for b in range(16):
        bits, carry = add_bits(to_bits(a, 4), to_bits(b, 4))
        if from_bits(bits) + carry * 16 != a + b:
            failures += 1
print("pairs checked: 256, failures:", failures)
print()

print("Mistake 1: half adders only, no carry in")
bits = [half_adder(a, b)[0] for a, b in zip(to_bits(7, 4), to_bits(1, 4))]
print("7 + 1 gives", from_bits(bits))
print()

print("Mistake 2: sum bits read in the wrong order")
bits, _ = add_bits(to_bits(5, 4), to_bits(3, 4))
print("reading the list as most significant first:", from_bits(bits[::-1]))
print()

print("Mistake 3: lists of different length")
print(list(zip(to_bits(5, 4), to_bits(3, 3))))
try:
    add_bits(to_bits(5, 4), to_bits(3, 3))
except ValueError as error:
    print("ValueError:", error)
print()

print("Mistake 4: dropping the carry out")
print("9 + 9 keeps only 4 bits:", from_bits(add_bits(to_bits(9, 4), to_bits(9, 4))[0]))

Output:

5 + 3 in 4 bits
sum bits (LSB first): [0, 0, 0, 1]
carry out: 0
sum = 8
 
9 + 9 in 4 bits
sum bits (LSB first): [0, 1, 0, 0]
carry out: 1
low 4 bits = 2
with the carry = 18
 
11 + 6 in 4 bits
sum bits (LSB first): [1, 0, 0, 0]
carry out: 1
with the carry = 17
 
pairs checked: 256, failures: 0
 
Mistake 1: half adders only, no carry in
7 + 1 gives 6
 
Mistake 2: sum bits read in the wrong order
reading the list as most significant first: 1
 
Mistake 3: lists of different length
[(1, 1), (0, 1), (1, 0)]
ValueError: lengths differ: 4 and 3
 
Mistake 4: dropping the carry out
9 + 9 keeps only 4 bits: 2

The 9 plus 9 case shows why the carry out matters. The true answer is 18. Four bits can hold only 0 to 15, so the sum wraps to 2 in the low four bits. The carry out is 1, and it stands for the value 16 that the four bits cannot hold. Add 16 back and you get 18.

The exhaustive check covers every pair of 4-bit numbers, which is 16 times 16, or 256 cases. Because the input space is that small, a clean result here is a complete test of the adder, not a sample.

Common mistakes

Leaving out the carry in. Mistake 1 chains only half adders. The output is 6 for 7 plus 1, but the answer is 8. Each column needs the carry from the column on its right, and a half adder cannot take that carry in. This is the bug the full adder exists to fix.

Reading the bits in the wrong order. The code stores the least significant bit first. The sum bits are [0, 0, 0, 1] for 8. Reversed, they read as [1, 0, 0, 0], which is 1. Whenever you convert a list of bits to a number, check which end holds the ones column. Mistake 2 shows the wrong result in the output.

Using lists of different lengths. Python's zip stops at the shorter list without a warning. Mistake 3 shows zip quietly making only three pairs from a four-bit and a three-bit number. The adder code checks the lengths first and raises a ValueError with the two numbers in the message. The error text tells you what to fix: one number has 4 bits and the other has 3.

Ignoring the carry out. Mistake 4 keeps only the sum bits. For 9 plus 9 the output is 2, which is wrong. A fixed-width adder always produces a carry out, and the caller has to decide what to do with it. Real CPUs store it in a flag, and programs check that flag for overflow.

Practice

Exercise 1. Use a half adder with inputs a = 1 and b = 0. What are the sum and the carry?

Show the answer

The sum is 1 and the carry is 0. XOR(1, 0) is 1, and AND(1, 0) is 0. The result is binary 01, which is 1.

Exercise 2. Use a full adder with a = 0, b = 1 and carry in = 1. What are the sum and the carry out?

Show the answer

The sum is 0 and the carry out is 1. The first half adder gives XOR(0, 1) = 1 and AND(0, 1) = 0. The second half adder takes the sum 1 and the carry in 1, giving sum XOR(1, 1) = 0 and carry AND(1, 1) = 1. The carry out is OR(0, 1) = 1. Together that is binary 10, which is 2, matching 0 plus 1 plus 1.

Exercise 3. Using the 4-bit adder, what is 6 plus 7? Give the sum bits and the carry out.

Show the answer

The sum is 13, written as binary 1101, with carry out 0. Six is 0110 and seven is 0111. The sum of the two lists, column by column from the right, is 1101 with no carry out, because 13 fits in four bits.

Exercise 4. Using the 4-bit adder, what is 12 plus 5? Give the low four sum bits, the carry out, and the full value.

Show the answer

The low four bits are 0001, the carry out is 1, and the full value is 17. Twelve is 1100 and five is 0101. Their sum is 10001 in binary, which is 17. Four bits hold only the low part, 0001, and the carry out holds the 16.

Exercise 5. The OR gate in the full adder combines two carries. Explain in your own words why a plain OR is enough and XOR is not needed there.

Show the answer

The two carries can never both be 1 together. The first carry is 1 only when both input bits are 1, and then the partial sum is 0, so the second half adder produces no carry. Since at most one carry is 1, OR gives the right answer. XOR would also give the same result in this case, but OR is the simpler gate and it is the one the standard full adder uses.

Summary

A half adder adds two bits. Its sum is XOR of the inputs and its carry is AND of the inputs.
A full adder adds two bits plus a carry in. It is two half adders and an OR gate.
A ripple-carry adder chains one full adder per column, and each carry out feeds the column on its left.
A 4-bit adder can hold sums from 0 to 15. A sum of 16 or more sets the carry out, and dropping that bit loses the answer.
Check an adder against Python's + on every input pair. For 4-bit numbers that is 256 cases, which is a complete test.

Building a tiny adder

Why this matters

Adding in binary, one column at a time

The half adder: two bits in

The full adder: add the carry from the right

Chaining full adders into a 4-bit adder

Common mistakes

Practice

Summary

Stuck? Ask the tutor