Bit Lab: the ALU and its flags

Prerequisites

You should already be comfortable with:

• Reading a number in binary and hex, and converting between them (e.g. 0b1010 = 0xA = 10).
• The truth tables of NOT, AND, OR and XOR.
• The idea that a CPU register holds a fixed number of bits (here 4 or 8).

This is part 5 of From gates to a compiled if. Three other parts build the pieces this lab uses from those gates, with inputs you can tap: From gates to an ALU (a full adder, then four of them chained), From adding to subtracting (wrap-around, NOT then add 1, and the borrow as a carry) and From gates to a register (a latch, a clock, a 4-bit register). Read them first if you want the ground under your feet; the background below only summarises them.

Notation. Gate equations on this page use the usual Boolean shorthand: A ⊕ B is XOR (1 exactly when the inputs differ), A·B or AB is AND, A + B is OR when it appears inside a gate equation, and ¬A is NOT. So the full adder's carry-out, A·B + cin·(A ⊕ B), reads "A and B, or cin and (A xor B)". Everywhere else on the page, + is ordinary addition.

You do not need to know what an ALU is, what a flag is, what a clock does, or anything about two's complement. The background section introduces all of them.

Learning goals

By the end of this lab you will be able to:

1. Explain why bitwise logic ops need no communication between bit positions (columns), while addition does.
2. Trace a carry rippling through a chain of full adders and predict the result.
3. Show how subtraction and negation are built from addition using invert-and-add-one.
4. State what each of the N, Z, C and V flags means and which gates produce it.
5. Distinguish unsigned overflow (C) from signed overflow (V), and predict both for a given addition.
6. Describe what the three kinds of shift do to the bits and to the carry flag.

Background

What an ALU is. Inside every CPU there is one circuit whose whole job is to take one or two numbers and produce a new number from them: add, subtract, AND, shift and so on. It's called the arithmetic logic unit, or ALU. It has no memory and no clock of its own — it is pure combinational logic, a web of gates, so its output changes the moment its inputs do. Everything else in a CPU is plumbing to get numbers into the ALU and results out of it.

A register is just a row of bits the CPU holds on to — in this lab, A and B are 4 or 8 bits wide. An instruction like add selects which operation the ALU performs, the ALU computes, and the result is written back to a register. Alongside the result the ALU also outputs a few single bits of information about the result: was it zero, was it negative, did it overflow. These are the flags. They are what makes if statements and loops possible: a conditional branch simply tests a flag left by the previous ALU operation.

Where the operation comes from. The instruction is itself a number, fetched from memory into the instruction register. A few of its bits, the opcode, go to the control unit, which decodes them into the wires that tell the ALU what to do and which registers to use. So "add" never reaches the ALU as a word: it arrives as a pattern on the operation lines, and the ALU is wired so that pattern selects the adder. Some example instructions, in a generic assembly notation:

CMP followed by BEQ is how if (a == b) runs: the subtraction leaves Z set exactly when the two values were equal, and the branch reads it. In the lab below there is no control unit; you are it. The operation buttons are its output wires.

The lab below is a miniature ALU: two input registers, the gate network for one operation at a time, a result, and the four flags.

Two readings of the same bits. An 8-bit pattern has no intrinsic sign. Read as unsigned, 0xFF is 255. Read as two's complement signed, the top bit counts as −128, so 0xFF is −1 and the range is −128…127. The hardware adds the same way regardless; the flags let software decide whether the answer is trustworthy under the reading it cares about.

The companion pages, in brief

From gates to an ALU. Bitwise ops use one gate per bit position. Addition uses one full adder per bit position, and a full adder is only five gates: sum = A ⊕ B ⊕ cin and carry-out = A·B + cin·(A ⊕ B). Four of them, each carry-out wired to the next carry-in, add two 4-bit numbers the way you add on paper, and the carry ripples from bit 0 upward. The lab draws each full adder as a box marked FA (short for full adder). To see inside the box, with inputs you can tap and a ripple you can watch, read the companion page From gates to an ALU.

From adding to subtracting. A register with 8 bits holds 256 patterns and wraps round: count down past 0 and you are at 255. So 3 − 5 lands on 254, which is 0xFE, and 0xFE is also the pattern for −2. That is what the lab shows when you pick A − B, and it is not a mistake: the same bits are 254 to one reading and −2 to the other. The adder does it without a subtractor. Inverting every bit of B gives 255 − B, so adding NOT B and then 1 adds 256 − B, which modulo 256 is subtracting B. In the drawing, A − B is the adder with an inverter under every B bit and the first carry-in set to 1. The carry out of the top adder then reports whether a borrow was needed: C = 1 means no borrow. The companion page From adding to subtracting shows this on a 16-position wheel and in bits you can tap.

Shifts. The last three operations move bits sideways and need no gates at all, only wiring: each bit's wire is connected one column over. Shifting left moves every bit up a column, which doubles the number, and the bit that falls off the top lands in C. Shifting right halves the number, but there are two right shifts, because the column that empties at the top has to be filled with something. One fills it with 0, which is right for an unsigned number; its traditional name is the logical shift. The other fills it with a copy of the old top bit, so a negative number stays negative, which is right for a signed one; that is the arithmetic shift. The lab's buttons say what each does rather than its name. This is one of the pairs of instructions that exist only because the same bits have two readings; the two kinds of branch, on the next page, are another. In C, >> on an unsigned variable is the logical shift and on a signed variable is, in practice, the arithmetic one, so again the declaration chooses. Java and JavaScript spell them the other way round from what you might guess: >> is arithmetic and >>> is logical. One more thing to expect: the arithmetic shift rounds toward minus infinity, so −3 shifted right once is −2, not −1.

From gates to a register. The ALU needs no memory: a gate's output depends only on its present inputs. The registers on either side of it do, and they are made of the same kinds of gates wired with feedback, an output led back round to an input, so a pair of NOR gates can hold a bit for as long as the power is on. A clock, a signal that swings between 0 and 1 billions of times a second, decides the one instant at which registers take in a new value. The companion page From gates to a register builds a latch from five gates and a 4-bit register you can clock.

The flags

The flags. After an operation the ALU records four one-bit facts, which conditional branches then test. They are four separate stored bits, not one four-way value: each flag has its own flip-flop (the memory cell built on the From gates to a register page), loaded at the same clock edge as the result, and any combination can be set at once. 0x80 + 0x80 sets C and V together, and 0xFF + 1 sets Z and C. Real CPUs keep these four bits inside a wider status register next to things like interrupt and mode bits; on ARM it is 32 bits wide with N, Z, C and V as its top four.

This lab follows the ARM / Harris & Harris convention: after subtraction, C = 1 means no borrow was needed. x86 stores the opposite sense for subtraction, so if you later read Intel manuals, keep that in mind.

Guided exercises

For each one, predict the result and flags before you look. Each "Load" button sets the lab up for you.

Check yourself

Answer without the lab, then verify.

1. Which single gate type, if you had enough of them, could build everything else on this page?
   Answer

   NAND (or NOR). Both are functionally complete.

2. In 8-bit, what are R, N, Z, C and V after 0x40 + 0x40?
   Answer

   R = 0x80, N = 1, Z = 0, C = 0, V = 1 (64 + 64 = 128 overflows the signed range).

3. A branch instruction wants "jump if A < B as signed numbers" after computing A − B. Which flags does it test?
   Answer

   N ≠ V. If no overflow happened, N alone says the result was negative; if overflow did happen, the sign is inverted, so N must be flipped. XOR-ing them handles both.

4. And "jump if A < B as unsigned numbers"?
   Answer

   C = 0 under the ARM convention (a borrow was needed). Under x86 it would be C = 1.

5. Why is the Z flag computed with a NOR rather than an OR?
   Answer

   OR of all bits is 1 when the result is non-zero. We want 1 when the result is zero, so the OR is inverted.

6. In an 8-bit ripple-carry adder, which result bit is ready last, and what does that imply about speed?
   Answer

   Bit 7 and the carry flag, because they depend on the carry from every column before them. Adder delay grows with width, which is why real CPUs use carry-lookahead or similar.

Build it for real

If "register" and "ALU" still feel abstract, here is the smallest build that makes them physical, in 4 bits, using the same chips as Ben Eater's breadboard computer. You do not have to build it; reading the five steps is enough to see what the words mean. A bit is one wire sitting at 5 V or 0 V, shown by an LED. A register is a chip that remembers a few such wires. An ALU is a chip with no memory whose output wires are a pure function of its input wires.

1. One full adder from five gates. Wire the full adder from the From gates to an ALU page with three chips: a 74HC86 (four XOR gates), a 74HC08 (four AND gates) and a 74HC32 (four OR gates). Three switches give A, B and carry-in, each with a 10 kΩ resistor to ground so an open switch reads 0; two LEDs show sum and carry-out. Flick through all eight rows of the truth table. You have built the box the lab draws as FA.
2. Four of them make the adder. Chain four full adders, each carry-out into the next carry-in and the first carry-in to ground, and you have the ripple-carry adder the lab draws: that is two 74HC86, two 74HC08 and one 74HC32. Or buy the same four adders in one chip, the 74HC283. Either way, two 4-way DIP switches feed A and B, and five LEDs show the sums and the carry-out. Set A to 0111 and B to 0001: the sum LEDs show 1000 the instant the switch closes. There is no clock and no "run"; the outputs just follow the inputs, which is all "ALU" means. Set A to 1111 and B to 0001 and the sums go dark while the carry-out LED lights. That LED is the C flag, and on the 74HC283 it is literally pin 9. The LED on S3 is N. The DIP switches are registers you load by hand.
3. Subtraction and the other flags. Insert a 74HC86 between the B switches and the adder, with a SUB switch on the second input of every gate and on the adder's carry-in. SUB off passes B through; SUB on inverts B and the carry-in adds the 1, so the adder computes A + NOT B + 1, which is A − B. For Z, feed the four sum lines into one gate of a 74HC4002 (a 4-input NOR) and light an LED from its output. For V, overflow means the two numbers entering the adder had the same top bit and the sum's top bit differs: with spare XOR gates and one AND gate from a 74HC08, compute XNOR(A3, B′3) AND XOR(A3, S3), where B′3 is the bit-3 XOR output, the operand the adder actually sees.
4. Registers: the numbers stay put. Put a 74HC173, a 4-bit D register, between each DIP switch and the adder: switches into its D inputs, its Q outputs into the adder and four LEDs, and one push button on the clock pin of both chips. Set the switches to 0111 and press the button: the register LEDs show 0111. Now flip the switches to anything else; the register LEDs do not move. The chip is remembering, and that is the whole of what a register is. Its load-enable pins decide whether a press changes it. To see the memory in pure gates first, wire the D latch from the From gates to a register page with a 74HC02 (four NOR gates), a 74HC08 and a 74HC04 inverter; the 74HC173 is four sharper versions of that cell. The adder now works on "registers A and B", the block diagram at the top of this page, and in this build you are the control unit: the SUB switch is an operation line, and each press of the clock executes one instruction.
5. The payoff: an accumulator. Move four jumpers so the adder's sum outputs feed register A's D inputs instead of the switches. Load B with 0001. Each press of the button now performs A ← A + B and the A LEDs count 0000, 0001, 0010 and so on. Load B with 0011 and it counts in threes; switch SUB on and it counts down. That is one CPU instruction, ADD A, B, per button press, and "the result is written back to a register" stops being a metaphor. Debounce the button first, for instance with a 74HC14 Schmitt inverter and a 10 kΩ resistor with a 1 µF capacitor, or one press adds several times.

74HC283 pins

Worked on the bench

5 − 3   A = 0101  B = 0011  SUB = 1
        B after the XORs = 1100, carry in = 1
        0101 + 1100 + 1 = 1 0010   sum LEDs 0010 (2), carry LED on: no borrow

3 − 5   0011 + 1010 + 1 = 0 1110   sum LEDs 1110 (−2 signed, 14 unsigned)
                                   carry LED off: a borrow happened; N LED on

7 + 1   0111 + 0001     = 0 1000   carry off; V on: both inputs had top bit 0,
                                   the sum has top bit 1

What bites beginners

• CMOS inputs must never float: a pull-down resistor on every switch input, and unused gate inputs tied to ground.
• A 0.1 µF capacitor across each chip's power pins, close to the chip.
• The 74HC283 computes its carries with lookahead logic, so you will not see a ripple on it. To watch the ripple the lab draws, use the four gate-built adders from step 2.

Mapped onto the lab: the DIP switches are rows A and B, the adder and XOR chips are the drawing, the sum LEDs are row R, and the four flag LEDs are the flag cards. The register step is what the lab leaves out, because the lab has no clock.

What's next

• The quiz's two comparisons, signed less-than = N ⊕ V and unsigned less-than = NOT C, are the condition logic a CPU uses for if and loops. Part 4, Signed or unsigned: who decides?, shows every ARM branch built that way and a compiled if using them.
• Part 6, the flag drills, makes the flags reflex: predict N Z C V, pick the branches that fire, recover the type from compiled code.
• Build the bench version above, then swap the 74HC283 for four gate-built adders and watch a real ripple.
• Put a multiplexer in front of the adder so one circuit does ADD, SUB, AND and OR: that is the ALU in Harris & Harris, chapter 5, and the Nand2Tetris ALU in project 2. Wider adders avoid the ripple with carry-lookahead and carry-select designs.
• To build a whole machine from gates to a running program, with a simulator and graded projects, take the Digital Design course.