Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 57 ยท Toward a Processor

Designing an ALU

Design an arithmetic logic unit step by step. Combine an adder, logic gates and a multiplexer, add Z, C, N and V flags, and model an n-bit ALU in Python.

Every processor has a part that does the actual arithmetic: the arithmetic logic unit, or ALU. It takes two binary numbers and a code that says which operation to perform, and it produces a result plus a few status bits called flags. Everything you have built so far, adders, gates and multiplexers, comes together here.

An ALU is not one clever circuit. It is a small collection of ordinary circuits that all work at once, plus a multiplexer that selects which answer to keep. This lesson builds that structure, explains the four common flags (zero, carry, negative and overflow), and models an n-bit ALU in Python. You will also see how the flags let a CPU compare numbers without a dedicated comparison circuit.

Details such as the exact meaning of the carry flag after a subtraction differ between processors. This lesson uses the convention found on ARM-style CPUs (carry means "no borrow"), and says so where it matters.

The big idea: compute everything, then select

Imagine a box with inputs A and B (both n bits wide) and a select input op. Inside the box, an adder, an AND unit, an OR unit and an XOR unit all receive A and B and compute their results at the same time. A multiplexer, steered by op, passes exactly one of those results to the output.

Inside an ALU

Arithmetic unit An adder, reused for subtract.
Logic unit AND, OR, XOR, NOT per bit.
Shifter Moves bits left or right.
Output mux The op code picks one result.

All units run in parallel. The mux only chooses.

1 / 2

This "compute everything, select one" design is simple and fast. The unused units waste a little power, but there is no waiting for a decision before the work starts, and that is what makes it quick.

Subtraction with the same adder

You do not need a separate subtractor. From Signed Numbers and Two's Complement you know that A - B equals A + (~B) + 1. So the adder needs only two extra pieces:

  1. An XOR gate on each bit of B, controlled by a sub signal. XOR with 0 passes the bit unchanged, XOR with 1 inverts it.
  2. The sub signal also goes into the adder's carry-in, supplying the "+ 1".

When sub is 0 the circuit adds, and when sub is 1 it subtracts. The program below builds an n-bit ripple adder this way from the full-adder equations and compares it with ordinary integer arithmetic.

Python One adder that adds and subtracts

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.

Look at 3 - 5. The 4-bit answer is 14, which is 1110, the two's complement pattern for -2. The carry-out is 0. In a subtraction, a carry-out of 1 means "no borrow was needed" (A was at least B) and 0 means "a borrow happened" (A was smaller). That inverted meaning is the ARM convention. Some older CPUs invert the carry after subtraction so that it means "borrow" instead.

The four flags

After every operation, the ALU computes four single-bit flags from the result and the operands. Together they form a small status register.

  • Z (zero): 1 when every bit of the result is 0. It is a wide NOR of the result bits.
  • N (negative): a copy of the result's top bit. For signed numbers in two's complement, that bit is the sign.
  • C (carry): the carry-out of the top bit position of the adder. For unsigned numbers it means the result did not fit. For shifts, it holds the bit that fell off the end.
  • V (overflow): 1 when a signed result does not fit in n bits.

Overflow deserves care, because carry and overflow are different things. Think about the signs of the operands:

  • Adding two numbers with the same sign can overflow if the result has the opposite sign. For example 0111 + 0001 is 7 + 1, and the 4-bit result 1000 reads as -8.
  • Adding numbers with different signs can never overflow, because the result lies between the two operands.

The hardware test is: V = 1 if the sign of A equals the sign of the (possibly inverted) B, and the sign of the result differs. In code, ((a ^ r) & (b ^ r) & SIGN) checks "result differs from both inputs in the top bit". For subtraction, the roles change: overflow happens when A and B have different signs and the result sign differs from A.

A complete n-bit ALU

Now put it together. The ALU below has eight operations picked by a 3-bit select, and returns the result with all four flags. The width is a constant, so you can change WIDTH to model an 8-bit or 16-bit ALU.

Python An eight-operation ALU with 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 the output with the flags in mind:

  • 5 + 3 = 1000: the result is 8, which is fine as an unsigned number, but as a signed 4-bit number 1000 is -8. The flags show N and V: a signed overflow.
  • 9 + 9 = 0010: unsigned, the true answer 18 does not fit in four bits, so C is set. As signed numbers, 9 is -7, and -7 + -7 = -14 also does not fit, so V is set too.
  • 4 - 4 = 0000: Z is set, and C is set because no borrow was needed.
  • The shift rows put the bit that fell off the end into C.

Notice that the logic operations leave C and V at 0. Real processors differ on whether logic operations clear or preserve those flags, which is why a programmer should not rely on them.

How the select code reaches the mux

In hardware, the select code op drives an 8:1 multiplexer for each result bit, and also sets the sub line of the adder. A small piece of control logic turns the op code into the exact signals each unit needs. For example, sub = 1 for the subtract code. Designers often choose op codes so that this decoding is as small as possible, for instance making one op-code bit equal to sub.

Comparing numbers with flags

A CPU has no dedicated "less than" circuit. It subtracts and then reads the flags. The subtraction is done only for its flags, and the result is thrown away. That is what a CMP instruction does.

  • Unsigned A < B is true when subtraction needs a borrow, that is when C = 0.
  • Signed A < B is true when N โ‰  V. If there is no overflow, a negative result means A is smaller. If there is an overflow, the sign bit is wrong and the meaning flips.
  • A = B is simply Z = 1.

The program below proves both rules by trying all 256 pairs of 4-bit values against Python's own comparison.

Python Comparison from flags, checked exhaustively

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 sample rows show why two versions exist. For a=7, b=8, the unsigned answer is "less" (7 < 8) but the signed answer is "not less", because 8 is the pattern for -8. The same bits, subtracted once, give both answers through different flag combinations. A conditional branch instruction simply picks which combination to test.

Design choices you will meet

  • Width. Real ALUs are 8, 32 or 64 bits wide. The bit-slice idea is the same: one slice per bit, plus carry between slices. A ripple chain gets slow at 64 bits, so real ALUs use the carry-lookahead techniques you saw earlier.
  • Shifters. A one-bit shift is easy. Shifting by any amount in one step uses a barrel shifter, a stack of 2:1 multiplexers where each layer shifts by 1, 2, 4, 8 and so on.
  • Multiplication. It is usually a separate unit, or several cycles of adding and shifting, not part of the basic ALU.
  • Pass-through operations. Many ALUs include "pass B" and "pass A", so moving a value through the datapath reuses the same hardware.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How does a typical ALU produce a result for the selected operation?

    The adder, logic and shift units all receive the inputs at once. The op code only steers the output multiplexer, which keeps the chosen result.
  2. 2. How can one adder also subtract?

    A - B = A + (~B) + 1. XOR gates invert B when sub is 1, and the same sub signal supplies the extra +1 through the carry-in.
  3. 3. In 4 bits, 0111 + 0001 gives 1000. Which flags are set?

    The result 1000 has its top bit set (N). Adding two positive numbers produced a negative one, so the signed result overflowed (V). No bit left the top position, so C stays 0.
  4. 4. After SUB, which flag test means signed A < B?

    If there was no overflow, a negative result (N=1) means A < B. If overflow occurred, the sign bit is wrong, so the meaning flips. Together this is N XOR V.
  5. 5. What does C = 0 mean after an ARM-style unsigned subtraction A - B?

    With the ARM convention, carry means no borrow. C = 0 therefore means A was smaller than B in unsigned terms.

Summary

  • An ALU contains an adder, a logic unit and a shifter that all work in parallel, and an output multiplexer chooses the result.
  • XOR gates on B plus carry-in = 1 turn an adder into a subtractor using two's complement.
  • Flags describe the result: Z (all zeros), N (top bit), C (carry out or no-borrow) and V (signed overflow).
  • Carry is about unsigned overflow, overflow is about signed overflow, and they are independent.
  • A comparison is a subtraction whose result is discarded: unsigned less-than is C = 0, signed less-than is N != V, and equality is Z = 1.
  • Wider ALUs need faster carry logic, and barrel shifters make multi-bit shifts a single step.

Next: From Gates to a Tiny CPU.