Combinational Circuits - Building an ALU from Logic Gates
Helpful context:
- Logic Gates - The Basic Building Blocks of All Computation
- Negative Numbers in Binary - Two’s Complement and Why It’s Clever
Individual logic gates compute one bit at a time. Connecting them into circuits lets you compute on multi-bit numbers - adding 8-bit integers, selecting between two values, comparing two numbers. The arithmetic logic unit (ALU) at the heart of every CPU is exactly this: a carefully arranged collection of gates that implements addition, subtraction, and logical operations on whatever word size the processor supports.
This post builds the ALU from first principles, starting from a single-bit adder.
The Multiplexer: Selecting Between Inputs
Before arithmetic, there is routing. A multiplexer (MUX) takes two data inputs $A$ and $B$ and a selector $S$, and outputs whichever input the selector designates.
| $S$ | Output |
|---|---|
| 0 | $A$ |
| 1 | $B$ |
The implementation: $\text{Out} = (\overline{S} \cdot A) + (S \cdot B)$. When $S = 0$, the first term passes $A$ through and the second term zeros; when $S = 1$, vice versa.
Multiplexers appear everywhere in CPU design: selecting which operand goes to the ALU, choosing between a computed result and a forwarded value, routing data across the bus. They are the traffic cops of digital logic.
The Half Adder
To add two single bits $A$ and $B$, you need two output bits: the sum and the carry (which propagates to the next position, just like carrying a digit in decimal addition).
| $A$ | $B$ | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Look at the sum column: it is the XOR of the inputs. The carry column is the AND of the inputs.
$$\text{Sum} = A \oplus B \qquad \text{Carry} = A \cdot B$$
Two gates, two outputs. This is called a half adder - “half” because it cannot handle a carry coming in from a previous position.
The Full Adder
Real multi-bit addition requires handling three inputs: $A$, $B$, and $C_{in}$ (the carry arriving from the less significant bit). This is a full adder.
| $A$ | $B$ | $C_{in}$ | Sum | $C_{out}$ |
|---|---|---|---|---|
| 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 full adder is built from two half adders. First half adder adds $A$ and $B$, producing an intermediate sum and carry. Second half adder adds that sum with $C_{in}$, producing the final sum and another carry. The final carry-out is the OR of the two intermediate carries.
$$\text{Sum} = A \oplus B \oplus C_{in}$$ $$C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))$$
Chaining Full Adders: The Ripple Carry Adder
To add two $n$-bit numbers, chain $n$ full adders. The carry-out of each stage feeds the carry-in of the next. The first stage has $C_{in} = 0$.
This is called a ripple carry adder: the carry ripples from the least significant bit to the most significant bit. Eight full adders give you an 8-bit adder; sixteen give you 16-bit; and so on.
Discomfort check. Why is it called “ripple carry” - is it slow? Yes. The carry must propagate through every stage in sequence; the final sum bit cannot be computed until the carry from the previous stage arrives. For an $n$-bit adder the delay is proportional to $n$. In practice, CPUs use carry look-ahead adders that compute all carries in parallel, reducing the delay to $O(\log n)$. The ripple carry adder is the clearest conceptually but not the fastest.
Building the ALU
A CPU’s arithmetic logic unit needs more than addition - it also needs subtraction, bitwise AND, OR, XOR, and comparison. These are selected by operation control bits that route signals through multiplexers.
Subtraction from addition. Thanks to two’s complement, $A - B = A + (-B) = A + (\overline{B} + 1)$. Set all B inputs through NOT gates (flip all bits) and set the first carry-in to 1 (adding 1 completes the two’s complement). No separate subtraction circuit is needed - one extra NOT per bit and a carry-in control line.
Logic operations. AND, OR, XOR operate bitwise: each bit pair independently. These are just $n$ copies of the corresponding gate in parallel.
Operation selection. A multiplexer at the output selects which result (addition, AND, OR, XOR) to pass through, controlled by 2-3 bits from the instruction decoder.
For an 8-bit ALU, each component (adder, AND, OR, XOR) operates on 8 bits in parallel, and the multiplexer selects among 8-bit results. The carry chain from the adder spans all 8 bits.
Flags
The ALU also produces flag bits that report properties of the result:
- Zero flag (Z): result is all zeros
- Carry flag (C): carry out of the MSB (unsigned overflow)
- Overflow flag (V): signed overflow (carry into MSB differs from carry out)
- Negative flag (N): MSB of result is 1
These flags are stored in a status register and used by branch instructions: “jump if zero,” “jump if carry,” and so on. They are how the CPU makes decisions.
Summary
| Component | Gates used | Function |
|---|---|---|
| Half adder | XOR, AND | Add 2 single bits |
| Full adder | 2 half adders + OR | Add 2 bits + carry-in |
| Ripple carry adder | $n$ full adders chained | Add two $n$-bit numbers |
| ALU | Adder + logic units + MUX | Add, subtract, AND, OR, XOR |
The ALU is entirely combinational: given inputs, it immediately produces outputs with no memory of past states. Adding memory is the next step.
Read next: