14Making Decisions

Last chapter we pulled our hands out of the machine and let it run. A program counter walks down RAM. A fetch that never varies pulls in each line. There's a handful of verbs, and a JMP that can throw the counter back to the top to spin a loop. It genuinely runs programs now. But sit with the one thing it still cannot do. Every jump it makes is unconditional: JMP always jumps, no matter what just happened. So the machine can repeat, but it can't react. It can't loop while a counter is still above zero. It can't stop when a total is finally reached. It can't take one path if a number came out big and another if it came out small. It has no way to look at its own last answer and let that answer change what it does next. That is the difference between a calculator running a fixed script and a computer that decides: a machine bending its own path based on what it just computed. And the whole trick turns out to be tiny. Let the ALU report one bit of news about each result — did it come out zero? did it carry past the top? Stash those bits in a small flags register. Then add two new jumps that check a flag before they leap. Two facts, two conditional jumps, and the loop learns to choose.

01The march that can't choose

Here's the whole machine as we left it. Every block hangs off one shared bus: the PC, the MAR, RAM, the instruction register, the ALU with its operand registers, and the output display. Take one last calm look at a machine that can compute anything straight-line but can't yet make a single choice.

The one power it has for breaking out of a straight run is JMP. Recall exactly what JMP does: it slams a brand-new address into the PC, so the next fetch grabs whatever line that address names. Here's the counter marching on its own, with a JMP button that yanks it anywhere mid-stride. Press it a few times and feel the limit. It jumps every time you ask, no questions asked.

That "no questions asked" is the flaw. A JMP can't say "jump back to the top of the loop, but only if we're not done yet." It has nothing to look at. And the thing it should be looking at is sitting right there in the datapath: the ALU. Every time the machine adds or subtracts, the ALU produces a result. That result is the freshest news the machine has about what it just did. Watch it churn out an answer for any operation you pick.

So what do we feed the jump? Your first instinct is the honest one: keep the result, and let the jump compare it when it gets there. Price that. A jump is a single yes-or-no, so you would need a comparator to boil eight bits down to one — and you would still have to store the old result somewhere for the comparator to read. You have just invented a register that holds facts about the last answer, with eight bits in it instead of one, and a comparator bolted on top. The reduction to one bit is forced, not chosen. So: right beside the ALU we hang a tiny register, the flags register. Its job is to catch a few one-bit facts about the result the ALU just made. Not the number itself — just yes-or-no notes about it. Our toy keeps exactly two of these facts: did the result come out zero? (the zero flag) and did it carry past the top bit? (the carry flag). Here are the two flag bits, latched from the ALU's output like any other register. Flip the ALU's result and watch the facts update.

But why a register? Why not run a wire from the zero-detect circuit straight to the jump and skip the storage? Trace it and watch the answer die. The SUB lands its result. Then the machine fetches the next instruction — and that fetch drives the bus, reloads the instruction register, and hands the ALU whatever operands the next line wants. By the time a jump one or two instructions later asks "was it zero?", ask it out loud: where is the answer now? Nowhere. A wire holds nothing; it only carries what is being driven onto it right now. That is the whole reason the flags register exists — the fact has to outlive the instruction that made it. And the same trace hands us the loading rule for free. The flags must load only on the edge that writes an ALU result. Latch them on every edge instead and the jump's own fetch would erase the very fact it came to read.

And why two? Not taste either — count the questions a loop actually asks. "Am I done?" and "Am I past it?" That really is the whole list. Subtract one number from the other and read the zero flag: zero means they were equal, so subtract-then-test-zero answers A == B. Read the carry flag instead and, as we will see once the adder is on screen, it answers A >= B. Those two bits cover every unsigned comparison there is. A != B is the zero flag low. A < B is the carry flag low. Two is not a number the toy happened to land on. It is the number the questions needed.

Two bits. That's the entire memory the machine keeps about its own last move, and it's enough. The rest of the chapter is just this: build the circuit that computes each flag, then build the jumps that read them. Start with the simpler flag.

02The zero flag

"Is this number zero?" sounds like it needs arithmetic, but it's the opposite. It needs no arithmetic at all, just a definition. A byte is zero when every one of its eight bits is off. Not "the sum is small" — literally all eight bits reading 0 at once. Flip any single bit on and the byte is no longer zero. Play with that below. The ZERO lamp lights only in the one arrangement where the whole byte is dark.

So detecting zero is really detecting "are all eight bits off?" And we already have the exact gate for an all-or-nothing question. Recall the AND gate: its output goes high only when every input is 1, and a single 0 anywhere drags it low. It's the demanding gate, the one that insists on unanimity.

There's one twist to bridge. AND fires when its inputs are all 1, but we want to fire when the byte's bits are all 0. So we slip a NOT in front of each bit first. Invert every one of the eight, so an all-zero byte becomes all-ones. Then feed those eight inverted lines into one big AND. Now the AND is satisfied exactly when the original byte was zero. That's the whole zero-detect circuit: eight inverters into one wide AND, and its single output is the zero flag. Step through it and watch one stray bit veto the verdict.

Now put that circuit next to the one you may already be picturing, because they are not two circuits. Eight inverters feeding a wide AND fires when none of the eight bits is on. But "not any of them" is precisely what a NOR says. That is De Morgan's law, the identity you already own: invert every input and AND them, and what you have built is an OR with its output inverted — a NOR. So the zero-detect we just derived from the definition is an eight-input NOR. One circuit, two faces. Draw it whichever way you like; the silicon does not care, and now neither do you.

And like any fact worth keeping, the flag isn't left dangling on a wire. It's latched into the flags register on the clock edge, right when the ALU's result is latched too. Recall the edge-triggered register: it looks at its input only at the instant the clock rises, and holds that value steady until the next tick. The zero flag is just one such bit, sampling the zero-detect circuit's answer once per beat.

One flag down. The zero flag answers "is the result exactly nothing?" That's the question every counting loop lives and dies on. Now the second flag, which is subtler, because it's the one people get wrong.

03The carry flag

Our registers are eight bits wide, so the biggest number one can hold is 255. Add two bytes whose sum climbs past that, and something has to give: the answer no longer fits. Watch the 8-bit adder chew through two bytes, and pay attention to the very top column. When it overflows, a carry is born that has nowhere to land. It falls off the left edge, out of a ninth bit the register doesn't have.

That stray bit falling off the top is the carry. Because it's lost, the byte that stays behind is the true sum wrapped around. The count rolls over like an odometer running out of digits, back through zero. Eight bits give 256 patterns, so the arithmetic the machine actually does is modulo 256: every result is the real answer with multiples of 256 quietly subtracted off until it fits. Walk the wheel and watch a value climb past the top and reappear at the bottom.

Now the trap. This is the single most-confused pair of ideas in the whole build, so let's not open with the warning — let's open with an addition. Four bits: 1111 + 0001. The answer is 0000, and a bit drops off the top. Before you read on, commit: did that go wrong? Say yes and you are right. Unsigned, that is 15 + 1 = 16, and 16 will not fit in four bits, so the answer came out 0. Say no and you are also right. Read the same bits as signed and 1111 is −1, so it is −1 + 1 = 0, which is exactly correct. Same bits, both verdicts true — the question was underspecified. That is the whole lesson. The carry flag answers one specific question: did a bit fall off the top of an unsigned add? That is all it means — unsigned wrap out of the most-significant bit. It is not the same thing as signed overflow, the Chapter-5 idea where two same-signed numbers add to a result whose sign has flipped. That is also exactly when the sign column's carry-in and carry-out disagree, because that column is the only place a same-signed pair can change sign. Read the very same addition through both lenses below. The unsigned lens asks "did a bit fall off the top?" (the carry). The signed lens asks "did the sign go wrong?" (overflow). They can disagree — on 15 + 1 they do, the carry fired and the overflow did not — and in our toy machine, only the carry is captured as a flag. Never call the carry flag "overflow detection." It detects a wrap, not a sign error.

With that settled, the carry flag is simple to wire. It's just the carry-out of the top adder, latched into the flags register beside the zero flag on the same clock edge. Two facts, one little register, both fed straight from the ALU. Here they are together. Set an ALU result and watch both flags update as one.

So what does that carry-out mean when the adder is subtracting? Do one by hand. The machine has no subtractor: it computes 3 - 1 as 3 + 255, because 255 is how eight bits spell −1. That sums to 258. The byte left behind is 2 — correct — and 258 is past 255, so a bit carries off the top. The carry fires on a plain, boring subtraction that did not go wrong at all. Read it the right way round and it is not a broken flag, it is a different fact: the carry fired because the subtraction never had to borrow. Borrowing is what you do when the top number is too small. So during a subtract, carry set means A >= B, and carry clear means A < B. Check it: 0 − 1 is 0 + 255 = 255, which never reaches 256, so no carry — and sure enough 0 is not at least 1. That is what makes the carry flag worth having.

Now the machine keeps a running two-bit opinion of its last arithmetic: Z for "came out zero," C for "carried out the top." All that's left is to give the instruction set a way to act on that opinion.

04Jumps that check first

We already have the raw mechanism for changing course, and it's worth seeing again, because the new instructions add almost nothing to it. A JMP is nothing but a store aimed at the program counter: it drives the operand onto the bus and lets the PC latch it instead of RAM. The next fetch then starts wherever that address points. Watch the operand overwrite the PC.

JZ — "jump if zero" — must do something JMP cannot. Before you read on: which new control lines does it need? Now look. Here is JMP's execute step in Fig 1's vocabulary: raise IO to put the operand on the bus, raise J to let the PC latch it. Two lines. JZ's list is those same two lines, same order, one character changed — J becomes J AND Z. One AND gate, the Z flag on one input, sitting on one enable wire. That is the entire idea of a conditional jump: take that PC-overwrite and gate it on a flag. JZ writes the operand into the PC only when the zero flag is set. If the flag is clear, the write is suppressed. The PC just does its ordinary +1, so the machine falls through to the next line as if the JZ weren't there. Fall-through costs no hardware at all: the +1 was already winning by default. Watch a subtract land on zero, the Z flag snap high, and the PC get overwritten with the target. That's a jump that only happened because the last answer was zero.

JC — "jump if carry" — is the identical trick reading the other flag. It takes the branch only when the carry flag is set, and falls through otherwise. So the two conditional jumps are one mechanism pointed at two facts. The general shape is a fork: the flag is checked, and the machine goes one of two ways. Flip the flag below and watch a single conditional jump either leap to the target or fall straight through to the next instruction.

So let JC do some real work. SUB then JC is this machine's entire ability to say "A is at least B" — because the carry during a subtract means no borrow, and no borrow means A >= B. Fall through instead and you have just learned A < B. That is the other half of the comparison kit. The zero flag tells the machine equal or not. The carry flag tells it which way. Two one-bit facts, and there is no unsigned comparison left that the toy cannot make.

Step back and notice what we just built, because it's bigger than two opcodes. A plain instruction has one successor: the next line. A conditional jump has two possible successors, and the flag picks between them at runtime. That branch — a fork in the path chosen by a computed condition — is precisely the "if this, do that; otherwise, do the other" that hides inside the textbook definition of an algorithm. Sequence, we had. Repetition, JMP gave us. This is the missing third: selection. Here it is as the pure decision it is.

But keep the fork on the hardware, because a test like n >= 5 is not something this machine can do. It owns two one-bit facts and two jumps that read them. There is no comparator and no >= instruction. So the test has to be compiled down into what the toy actually has: load n, SUB 5, then JC. Carry set means no borrow, which means n was at least 5, so the branch is taken. That is what every high-level condition really is, here and on the silicon in your laptop — a subtract, then one flag test. The abstraction is not free. It is translated, and one AND gate is still down there doing the deciding.

Three control structures now: go in order, repeat, and choose. That is genuinely everything you need to express any computation at all. The theorem is Böhm and Jacopini's, from 1966, and we are borrowing it, not proving it here. What it says is that any flowchart can be rewritten using only sequence, selection, and one loop. The toy is, quietly, complete. Let's prove it does something useful.

05The countdown loop

The canonical use of all this is a loop that ends itself: start a counter at some value, do a little work each pass, knock the counter down by one, and keep going until it hits zero. That "down by one" is a decrement, just subtract 1. Here the earlier chapters pay off again. The machine has no subtractor, so it computes it as A + (−1), building −1 by the two's-complement trick. That is what the SU line in Fig 1 actually is. Raise SU and it inverts B on its way into the adder and forces the carry-in to 1 — flip and add one, the two's-complement reflex you already know, spent as a single wire instead of an instruction. So there really is no subtractor in there. There is an adder, and one control line that lies to it about B. Watch a value step down with no subtractor anywhere in sight.

Now assemble the pattern. Each pass, decrement the counter. The subtract sets the zero flag for free as a side effect. Then a single JZ asks the flag — not zero yet? then fall through and JMP back to the top. Is it zero? Take the JZ and leap out of the loop. That's the whole shape of every bounded loop ever written. Run it and watch the counter walk down to zero, then the branch finally fire to break out.

And to see it as a real program rather than an animation, here's our little interpreter again. It's the same fetch–advance–execute loop from last chapter, now taught the two conditional jumps, running an actual countdown from a starting value down to zero. It fetches, checks the flag, branches or falls through, and prints each step so you can read the decision happening.

Read that trace and you're watching a machine decide: subtract, is it zero? no — jump back; subtract, is it zero? no — jump back; … subtract, is it zero? yes — fall out and halt. The loop knows when it's done. Nobody told it. It looked at its own last answer and chose.

That's Chapter 14. Two one-bit facts about each ALU result, latched into a tiny flags register. The zero flag comes from a circuit that inverts all eight bits and ANDs them. The carry flag catches the unsigned wrap out of the top bit (and, we were careful to say, is not signed overflow). Then two jumps that read them, JZ and JC, each just a plain JMP gated on a flag. That gives the machine the one thing it lacked: the power to branch. With sequence, repetition, and selection all in hand, our toy can now run any bounded loop and any decision. It is a real, complete little computer. But look one last time at who's still deciding. Every one of those choices — which control lines to raise, on which micro-step, given this opcode and these flags — is being made by a fixed rule we worked out by hand. And a fixed rule that maps inputs to outputs, with no memory of its own, is a thing you've already built twice: a lookup table. The machine's whole brain is about to turn out to be furniture from Chapter 11 — a ROM. That's next.