Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 67 ยท Digital Logic

Building an ALU

Design an arithmetic logic unit step by step: operations, control signals, the Z N C V flags, carry-lookahead logic, and a working 8-bit ALU model in Python.

The arithmetic logic unit (ALU) is the part of the CPU that actually computes. It takes two input words, a few control bits that say which operation to perform, and produces a result plus a handful of status bits called flags. Every add, sub, and, comparison and address calculation your program makes passes through an ALU.

You already have the ingredients: gates from Logic Gates and Boolean Algebra, the full adder and ripple-carry adder from Combinational Circuits, and two's complement from Signed Integers and Two's Complement. This lesson wires them together into one unit, explains the flags, and shows how hardware makes addition fast.

What an ALU looks like from outside

flowchart LR
  A["A (n bits)"] --> ALU["ALU"]
  B["B (n bits)"] --> ALU
  C["Control (op select)"] --> ALU
  ALU --> R["Result (n bits)"]
  ALU --> F["Flags: Z N C V"]

Two operands and a control code go in; a result and flags come out.

An ALU is purely combinational. It has no memory of its own: registers hold the operands before it and the result after it, clocked as described in Latches, Flip-Flops and Registers. A typical teaching ALU supports:

Operation Result
ADD A + B
SUB A - B
AND, OR, XOR bitwise logic
SLT 1 if A < B (signed), else 0
shifts A moved left or right by B places

Real ALUs have more, but this set already runs most programs.

One adder, many operations

Instead of building a separate circuit for each operation, designers share hardware. The key observation is that, in two's complement, subtraction is addition in disguise:

A - B = A + (NOT B) + 1

So the ALU needs just an adder and a row of XOR gates in front of input B. Each XOR gate takes one bit of B and a control signal invert B. When the signal is 0 the bit passes through unchanged; when it is 1 the bit is flipped. Feeding the same signal into the adder's carry-in supplies the "+ 1". Subtraction becomes a matter of setting two wires.

The control unit sets a small bundle of signals for each operation:

Operation Invert B Carry-in Result comes from
ADD 0 0 adder
SUB 1 1 adder
AND 0 0 AND gates
OR 0 0 OR gates
XOR 0 0 XOR gates
SLT 1 1 sign of the subtraction

All the candidate results (adder, AND, OR, XOR, and so on) are computed at the same time. A multiplexer at the end, driven by the control bits, selects which one leaves the ALU. Computing everything and choosing is wasteful in energy but simple and fast, a trade-off hardware makes constantly.

The four flags

Besides the result, the ALU reports four one-bit facts. They are stored in a status register (or flags register) so that later instructions, such as conditional branches, can test them.

  • Z (zero): the result is all zeros. After SUB, Z = 1 means the operands were equal.
  • N (negative): the top bit of the result is 1, which means negative if you read the word as signed.
  • C (carry): the adder produced a carry out of the top bit. For addition this signals an unsigned overflow. For subtraction done as A + NOT B + 1, C = 1 means no borrow occurred (A >= B unsigned), which surprises many people. Some architectures invert it, so check each manual.
  • V (overflow): the signed result does not fit. It happens when two operands of the same sign give a result of the opposite sign, for example 127 + 1 in 8 bits. Hardware computes it by comparing the carry into the sign bit with the carry out of it.

Notice that C and V answer different questions about the same bits. The ALU does not know whether you consider the numbers signed or unsigned; it reports both, and the program (or compiler) picks the flag that matches its type. For more on this duality see Binary Arithmetic and Overflow.

A comparison like if (a < b) is usually just a SUB whose result is thrown away, followed by a branch on the flags. For signed numbers, A < B exactly when N and V differ. That is why the SLT operation above can compute its answer as N xor V of the subtraction.

An 8-bit ALU in Python

The model below follows the hardware design directly: control signals pick the inverted B and the carry-in, one addition is performed, and a final selection chooses the result. Flags come from the adder's output.

Python An 8-bit ALU with control signals and flags

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.

Read a few rows against the rules:

  • ADD 127 1 gives 128, which is 10000000. As unsigned that is fine (C = 0), but as signed it is -128, so N = 1 and V = 1: signed overflow.
  • ADD 200 100 wraps to 44 with C = 1: the unsigned sum does not fit, but V = 0 because, read as signed, 200 is -56 and -56 + 100 = 44 is perfectly valid.
  • SUB 5 5 gives zero with Z = 1 and C = 1 (no borrow).
  • SUB 3 5 gives 254 (that is -2 in two's complement), N = 1, and C = 0 because a borrow was needed.
  • SUB 128 1 is -128 - 1 in signed terms, which does not fit: V = 1.
  • SLT 255 1 asks whether -1 < 1 (signed) and answers 1, even though 255 is larger than 1 unsigned.

A real ALU is generic over the data width, so feeding it a different WIDTH (try 4 or 16) is a good experiment.

When you debug an arithmetic bug, check which flag your code actually depends on. Using C where you meant V (or the reverse) is the classic way to get correct results for small numbers and wrong results near the limits.

Why ripple-carry is slow

The adder in this ALU is the slowest part. A ripple-carry adder passes the carry from bit to bit, and bit 31 cannot know its carry-in until bits 0 to 30 have finished. If each full adder adds about two gate delays, a 64-bit ripple adder takes on the order of 128 gate delays, while the clock period of a fast CPU may allow only a few dozen. The adder would limit the entire processor.

Carry-lookahead

The cure is to compute all the carries at once from the inputs, without waiting. For each bit position define two signals:

  • Generate g = a AND b: this bit creates a carry by itself.
  • Propagate p = a XOR b: this bit passes along a carry that arrives.

A carry out of bit i then exists when bit i generates one, or when it propagates one that came in:

c(i+1) = g(i) OR (p(i) AND c(i))

Substitute the formula for c(i) into itself and you get carries that depend only on g, p and the first carry-in c0:

  • c1 = g0 OR (p0 AND c0)
  • c2 = g1 OR (p1 AND g0) OR (p1 AND p0 AND c0)
  • c3 = g2 OR (p2 AND g1) OR (p2 AND p1 AND g0) OR (p2 AND p1 AND p0 AND c0)

Each is a flat two-level AND-OR expression, so all carries appear after the same short delay. The price is more gates, and the formulas get wider for longer words. Real adders therefore use groups: a 4-bit lookahead block produces group generate and group propagate signals, and a second lookahead level combines blocks. The delay grows roughly with the logarithm of the word width instead of linearly. Other fast designs (carry-select, carry-skip, prefix adders such as Kogge-Stone) trade area and wiring for speed in different ways.

The next TryIt implements the lookahead formula for any width and proves, over every possible pair of 4-bit inputs and both carry-ins, that it matches rippling.

Python Carry-lookahead versus ripple carry

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.

The example adds 0111 and 0001 (7 + 1). Lists are written least-significant bit first, so bit 0 generates a carry (both bits are 1) and bits 1 and 2 merely propagate it (their inputs differ). The carries c1, c2 and c3 are therefore all 1, and bit 3 produces no new carry, so c4 is 0. The Python loops here only simulate the formulas one after another; in hardware the AND-OR terms are separate gates working in parallel, which is the whole point.

Putting the ALU to work

In a full CPU the ALU sits in the middle of the datapath: two register-file outputs feed inputs A and B (or B comes from an immediate field in the instruction), the control unit drives the operation code, and the result is written back to a register or used as a memory address. The flags go to the status register. You will see this assembled in The CPU Datapath, and the instruction fields that select an operation are the subject of Instruction Formats and Encoding.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How does an ALU subtract B from A using its adder?

    A - B equals A + NOT B + 1 in two's complement. XOR gates invert B and the carry-in supplies the +1.
  2. 2. 8-bit ALU, unsigned operands: 200 + 100 produces 44. Which flag shows that the unsigned result did not fit?

    The sum is 300, which needs a ninth bit, so the carry out is 1. V stays 0 because as signed numbers -56 + 100 = 44 is valid.
  3. 3. Which condition sets the overflow flag V for a signed addition?

    Adding two positives and getting a negative (or two negatives and getting a positive) means the true result needed more bits.
  4. 4. What do generate and propagate signals let a carry-lookahead adder do?

    Expanding c(i+1) = g(i) OR (p(i) AND c(i)) gives flat expressions in g, p and c0, so the carries appear after a similar short delay.
  5. 5. After SUB A, B with the result discarded, which test says A < B for signed numbers?

    If there was no overflow, a negative result means A < B. If overflow occurred, the sign bit is wrong, so the real answer is the opposite of N. Together that is N xor V.

Summary

  • An ALU is a combinational circuit: two operands and control bits in, a result and flags out.
  • Sharing one adder works because A - B = A + NOT B + 1: an invert-B control and the carry-in do the job.
  • Several results are computed in parallel and a multiplexer chooses one.
  • Z, N, C and V report zero, negative, unsigned carry and signed overflow. C and V describe the same bits for unsigned and signed interpretations.
  • Signed comparison is a subtraction followed by testing N xor V.
  • Ripple-carry delay grows linearly with width; carry-lookahead uses generate and propagate signals to produce carries in parallel, usually in grouped form.

Continue with Instruction Set Architecture.