Combinational means no memory
In the last guide we built gates from a transistor switch, wrote truth tables, and proved with NAND completeness that one humble gate can express any boolean function. That gives us raw power but no organization — a heap of gates is hard to think about. This guide packages gates into three reusable blocks every processor uses by the thousand. The whole family shares one defining property: they are combinational, meaning the output depends only on the inputs right now, with no memory of the past.
Picture a vending machine of pure logic: feed in the same coins and you always get the same snack, instantly, no matter what you bought yesterday. That "no yesterday" is the line between combinational logic and the sequential logic of the next guide, which does remember. The price of remembering is a clock and feedback; combinational blocks have neither. They are just a tangle of gates that settles, after a tiny delay while signals ripple through, to one answer fixed by the inputs.
The multiplexer: a switch made of gates
The most useful combinational block is the multiplexer, or mux — a data selector. It has several data inputs, a few select inputs, and one output, and it simply forwards the chosen input to the output. A railway points-lever is the perfect picture: many tracks feed in, the lever (the select lines) decides which one continues, and the rest are ignored. A 2-to-1 multiplexer picks between inputs A and B using one select bit S: when S is 0 the output is A, when S is 1 it is B. In gates that is just out = (A AND NOT S) OR (B AND S) — proof that a "choice" is nothing more mysterious than a handful of ANDs and an OR.
Muxes widen cleanly. A 4-to-1 mux needs 2 select bits to count 00, 01, 10, 11 and pick among four inputs; in general, k select lines choose among 2^k inputs, and a wider mux is just more AND gates feeding one big OR. You can also build a 4-to-1 mux out of three 2-to-1 muxes arranged in a little tree — choice composed from smaller choices, which is exactly the kind of layering the earlier rung's abstraction story promised.
Why care so much about a switch? Because choosing is the heart of computing. Later you'll see a mux decide whether the next instruction comes from the program counter plus one or from a branch target; whether an operand is a register value or an immediate; which of several results to write back. The select lines, you'll find, are exactly the control signals that a control unit produces. A processor is, to a first approximation, a great many muxes steered by control. Master this one block and the datapath stops looking like magic.
The decoder: the mux turned inside out
A decoder is the mux's mirror image. A mux funnels many inputs down to one; a decoder fans one small number out to many lines, lighting exactly one of them. An n-to-2^n decoder takes n input bits as a binary number and raises a single output line — the one whose number matches the input. With 3 inputs you get 8 outputs, and feeding in 101 (which is 5) makes output line 5 go high while the other seven stay low. It is a one-hot translator: turn a compact binary code into a row of switches where precisely one is on.
Where does this earn its keep? Address decoding. When a processor wants the register numbered 5, a decoder turns the 5 into the single enable line that wakes that register and no other; the same idea picks one memory word out of millions. A decoder is also how an opcode becomes control: feed the operation code in, and exactly one "do this operation" line goes high. Mux and decoder are a matched pair — one selects an input, the other selects a destination — and together they route data anywhere on a chip.
The full adder: teaching silicon to add
Now the headline act. How does a machine add? Exactly the way you add by hand, column by column, carrying when a column overflows. The cell that does one column is the full adder. It takes three input bits — the two operand bits in this column plus a carry-in from the column to its right — and produces two outputs: a sum bit (the result digit for this column) and a carry-out (the bit pushed left into the next column). All five values are single bits, so the whole thing is just a little truth table you can build from a few gates.
Full adder truth table (a, b, cin -> sum, cout) a b cin | sum cout 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 sum = a XOR b XOR cin cout = (a AND b) OR (cin AND (a XOR b)) <- carry if any two are 1
Read the table once and a pattern pops out. The sum bit is 1 whenever an odd number of the three inputs are 1 — that is the XOR, the parity. The carry-out is 1 whenever at least two of the three inputs are 1 — that is the majority. So a full adder is just "parity for the sum, majority for the carry". This is exactly the logic of grade-school addition: 1 plus 1 is 0 carry 1, and 1 plus 1 plus a carry is 1 carry 1.
Stacking adders: a whole word at a time
One full adder handles one column. To add two 32-bit numbers, chain 32 of them: wire each adder's carry-out into the next adder's carry-in, exactly as the carry flows leftward when you add on paper. That chain is the ripple-carry adder, the simplest way to add a whole word. Feed in two 32-bit operands and a carry-in of 0, and 32 sum bits ripple out the top.
- Place 32 full adders side by side, bit 0 (rightmost) to bit 31 (leftmost).
- Feed each column its two operand bits; set the very first carry-in to 0 for addition.
- Connect every carry-out to the next adder's carry-in, so carries ripple left like in hand arithmetic.
- The 32 sum bits are your answer; the final carry-out signals an unsigned overflow.
Here is the elegant part that ties back to earlier guides. Because we store negative numbers in two's complement, the same adder also subtracts. To compute A minus B, feed in the bitwise NOT of B and set the first carry-in to 1 — that quietly forms (NOT B) + 1, which is exactly negative B, so the adder computes A + (negative B). One block, both operations, chosen by a single control line driving the carry-in and the invert. That is why a real chip does not need a separate subtractor; the ALU reuses one adder. Subtraction is addition wearing a disguise.
The honest catch: the carry has to ripple
The ripple-carry adder is correct, but it has a real cost, and pretending otherwise would mislead you. Each column's carry-out cannot be computed until the carry from the column to its right has arrived. So the carry must travel through all 32 adders in turn, one gate-delay after another, before the top bit is trustworthy. The chain is only as fast as its slowest path — and that longest path, the critical path, runs the full width of the word. A ripple-carry adder's delay grows linearly with the number of bits, which for a 64-bit machine is painfully slow.
This delay matters because, as the very first guide warned, the longest combinational path sets a ceiling on the clock. If your adder is the slowest thing the clock must wait for, a slow adder literally slows the whole processor. So architects do not settle for ripple-carry in real ALUs. Faster designs — the carry-lookahead adder, the carry-select adder, and the parallel-prefix adder — all spend extra gates to compute carries in parallel instead of waiting for them to ripple, trading silicon area for speed. We won't open them here, but note the recurring bargain: you buy a shorter critical path with more hardware.