Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 57 Β· Combinational Building Blocks

Half Adders and Full Adders

Build binary adders from logic gates: half adder, full adder and ripple-carry adder, with sum and carry equations, an overflow flag and a runnable Python model.

Everything a processor computes, subtraction, multiplication, address calculation, comparing numbers, comes down to adding binary digits. The adder is the first real combinational building block in this course: a circuit whose outputs depend only on its current inputs, built from the gates you already know. If you can design an adder, you have seen the whole method for building bigger circuits out of small ones.

In this lesson you will derive the half adder and the full adder from their truth tables, chain full adders into a multi-bit ripple-carry adder, and learn how hardware detects overflow. Every circuit is modeled in Python so you can run it.

Adding two bits: the half adder

Add two single bits A and B the way you would on paper. The possibilities are 0+0=0, 0+1=1, 1+0=1 and 1+1=10 (binary for two). The answer needs two output bits: a sum S (the low digit) and a carry C (the high digit).

A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Read the columns. The sum is 1 when exactly one input is 1: that is XOR. The carry is 1 only when both inputs are 1: that is AND. So

S = A βŠ• B and C = A Β· B

A half adder is therefore one XOR gate and one AND gate. It is called "half" because it has no input for a carry coming from a lower bit, so it can only start an addition, not continue one.

Adding three bits: the full adder

In a multi-digit addition, every column except the first has to add three bits: the two operand bits and the carry from the column to its right. A full adder has inputs A, B and Cin, and outputs S and Cout. The largest possible total is 1+1+1 = 3 = 11 in binary, which still fits in two output bits.

The sum is 1 when an odd number of inputs are 1, which is the three-input XOR. The carry out is 1 when at least two inputs are 1, the majority function. Written as equations:

S = A βŠ• B βŠ• Cin

Cout = AΒ·B + CinΒ·(A βŠ• B)

The second form reuses A βŠ• B, which the sum already needs. Two half adders and one OR gate do the whole job: the first half adder adds A and B, the second adds that partial sum to Cin, and the OR gate combines the two possible carries (they can never both be 1 at the same time).

Half adder versus full adder

Half adder Two inputs. One XOR and one AND.
Full adder Three inputs, with a carry in.
Parts list Two half adders plus one OR gate.

The carry in is what lets adders be chained.

1 / 2

The program below builds both circuits from tiny gate functions and prints their truth tables. The last column checks the circuit against ordinary arithmetic: 2 * carry + sum must equal a + b + cin on every row.

Python Half adder and full adder truth tables

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the decimal column always agrees with 2c + s. That equality is the whole specification of an adder: the pair (Cout, S) is simply the two-bit binary number A + B + Cin.

Chaining adders: the ripple-carry adder

To add two n-bit numbers, line up n full adders. Adder 0 handles the least significant bits, and its Cout is wired into the Cin of adder 1, and so on up the chain. The first Cin is usually 0 (you will see why it is useful as an input in subtractors). The carry ripples from the low end to the high end, which gives this design its name.

flowchart LR
    C0["Cin = 0"] --> FA0["FA bit 0"]
    FA0 -- "c1" --> FA1["FA bit 1"]
    FA1 -- "c2" --> FA2["FA bit 2"]
    FA2 -- "c3" --> FA3["FA bit 3"]
    FA3 --> C4["Cout"]

A 4-bit ripple-carry adder: each full adder passes its carry to the next one.

The Python model keeps bit lists with the least significant bit first, loops over the full adders, and records every carry. The function returns the sum, the final carry out, and an overflow flag, which the next section explains. Run it to watch 5 + 3 ripple through the chain.

Python A 4-bit ripple-carry adder

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the trace, the carry starts at bit 0 (1+1) and travels through bits 1 and 2 before bit 3 finally receives it. Bit 3 cannot finish until the carry has arrived, which matters for speed: each stage adds a delay, so a 64-bit ripple adder is slow. Carry-lookahead fixes that.

Carry and overflow are different things

The same adder handles unsigned and two's complement numbers, because the bit patterns add identically. What changes is how you interpret the flags.

  • Carry out (Cout of the top stage) signals unsigned overflow: the true answer does not fit in n bits. 15 + 1 in 4 bits gives 0000 with carry 1.
  • Signed overflow happens when two numbers of the same sign give a result of the opposite sign. In 4 bits the signed range is -8 to 7, so 5 + 3 = 8 does not fit and the result 1000 reads as -8.

Hardware detects signed overflow with one XOR gate: overflow = (carry into the top bit) βŠ• (carry out of the top bit). In the trace above the carry into bit 3 is 1 and the carry out is 0, so overflow is 1. An addition like 15 + 1 has carry out 1 but carry into the top bit also 1, so the signed overflow flag is 0: as signed numbers it is just -1 + 1 = 0.

Never judge overflow by the carry flag alone for signed numbers. Both 7 + 1 (signed overflow, no carry out) and -1 + 1 (carry out, no signed overflow) show that the two flags are independent. A processor keeps both so software can pick the right one.

Cost of an adder

A full adder built as above needs two XOR, two AND and one OR gate, five gates for each bit. An n-bit ripple-carry adder needs n full adders, so its size grows linearly with n, which is cheap. Its delay also grows linearly with n, which is the price. Designing adders is the classic trade between area and speed, and you will explore the fast side next.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which gate pair makes a half adder?

    The sum is 1 when exactly one input is 1 (XOR), and the carry is 1 only when both inputs are 1 (AND).
  2. 2. What are the outputs of a full adder for A=1, B=1, Cin=1?

    1 + 1 + 1 = 3, which is 11 in binary, so both the sum bit and the carry out bit are 1.
  3. 3. Why is a ripple-carry adder slow for wide numbers?

    The carry has to travel through every full adder in turn, so the delay grows in proportion to the number of bits.
  4. 4. A 4-bit adder computes 0111 + 0001 = 1000. What do the flags say for signed numbers?

    7 + 1 = 8 does not fit in the signed range -8 to 7, so the pattern 1000 reads as -8. The carry into the top bit is 1 and the carry out is 0, so the overflow XOR is 1.

Summary

  • A half adder adds two bits: S = A βŠ• B, C = AΒ·B. It has no carry input.
  • A full adder adds three bits: S = A βŠ• B βŠ• Cin, Cout = AΒ·B + CinΒ·(A βŠ• B). It is two half adders plus an OR gate.
  • Chaining full adders, with each carry out feeding the next carry in, gives an n-bit ripple-carry adder.
  • Carry out flags unsigned overflow; signed overflow is the carry into the top bit XOR the carry out of it.
  • Ripple-carry adders are small but slow, because the carry travels through every stage.

Next: Carry-Lookahead and Faster Adders.