From Logic Gates to a 32-bit ALU

This is Lesson 1, Part 2 of the Computer Architecture From First Principles series. Part 1 got us from bits to two's-complement integers and left off right at the boundary between mathematics and hardware. Here we cross that boundary: starting from four logic gates, we'll build an adder, then a subtractor riding on the same adder, then a full Arithmetic Logic Unit, and we'll do it by hand-tracing real 0s and 1s through every stage so none of it stays abstract.

Where We Left Off

Part 1 established two facts we're going to lean on hard in this post.

First, an n-bit two's-complement signed integer ranges over -2^(n-1) to 2^(n-1) - 1, and the negative of a value x is obtained by inverting every bit of x and adding 1. For an 8-bit example, +5 is 00000101; inverting gives 11111010; adding 1 gives 11111011, which is -5.

Second — and this is the part that actually matters for hardware design — that representation was chosen specifically so that the same binary adder circuit can perform both addition and subtraction, and both signed and unsigned addition. That is not an accident of notation. It's an engineering decision that pays for itself the moment you have to build the circuit, because it means you don't need a second piece of silicon for subtraction. You need one adder and one row of inverters.

By the end of this post you'll see exactly why that works, gate by gate.

The Alphabet of Gates: NOT, AND, OR, XOR

Everything downstream — adders, multiplexers, register files, caches, out-of-order schedulers — bottoms out in a small handful of logic gates.

There are technically more primitive gates (NAND and NOR are each individually "universal," meaning you can build any Boolean function from just one of them repeated), but for reasoning about circuits it's more natural to work with NOT, AND, OR, and XOR. We'll treat NAND/NOR as an implementation detail for a future post on transistor-level design — CMOS specifically prefers NAND/NOR because they map to fewer transistors than AND/OR do.

A gate is nothing more than a physical device that implements a Boolean function: it takes one or more binary inputs and produces a binary output, and that output is a deterministic function of the current inputs only — no memory, no history.

That "no memory" property is the definition of combinational logic, and it's worth holding onto, because everything in this post is combinational. Memory doesn't show up until Part 3.

NOT — Negation

Y = ¬A

A | Y
--+--
0 | 1
1 | 0

NOT is the only single-input gate we need. It flips its input. In CMOS this is the simplest gate to build physically (a single pull-up/pull-down transistor pair), which is part of why it shows up everywhere as a building block for other gates.

AND — Conjunction

Y = A ∧ B

A B | Y
----+---
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1

AND outputs 1 only when both inputs are 1. Think of it as a "gatekeeper": it only lets a 1 through if everything upstream of it also agreed. This is exactly the operation your C code reaches for when you mask bits — x & 0x0F is, gate for gate, an array of AND gates comparing each bit of x against the corresponding bit of the mask.

OR — Disjunction

Y = A ∨ B

A B | Y
----+---
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

OR outputs 1 if at least one input is 1. Where AND is a gatekeeper, OR is a "collector" — it merges signals. x | (1 << 3) (setting bit 3) is, in hardware, one OR gate per bit, with all but one input tied to 0.

XOR — The Arithmetic Gate

Y = A ⊕ B

A B | Y
----+---
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

XOR outputs 1 when its inputs differ. This is the one gate on this list that isn't just Boolean bookkeeping — it's genuinely arithmetic. Notice what XOR computes if you think of A and B as single-bit numbers: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 in binary, whose low bit is 0. XOR reproduces the low bit of binary addition exactly. That is not a coincidence, and it's the seed from which the rest of this post grows.

XOR is what makes addition possible in hardware — it is the "sum without carry" operation, repeated at every bit position.

The Half Adder: One Bit of Addition

Suppose we want to add two single bits, A and B. There are exactly four possible input combinations, and here's what binary addition actually produces for each:

The result of adding two 1-bit numbers can be as large as 2, which needs two bits to represent — a carry bit and a sum bit. So a 1-bit adder circuit needs two outputs, not one.

Read the carry and sum columns off that table separately:

A B | Carry Sum
----+----------
0 0 |   0    0
0 1 |   0    1
1 0 |   0    1
1 1 |   1    0

Look closely: the Sum column is exactly the XOR truth table from the previous section, and the Carry column is exactly the AND truth table. That gives us the equations directly, with zero derivation needed because we already built these two gates:

Sum   = A ⊕ B
Carry = A ∧ B

Wired up, this is a half adder:

Two gates, two inputs, two outputs. Worked example: A = 1, B = 1. XOR gives 1 ⊕ 1 = 0, so Sum = 0. AND gives 1 ∧ 1 = 1, so Carry = 1. Read together as Carry Sum = 10, which is binary for 2 — correct, since 1 + 1 = 2.

The half adder's limitation is right there in its name: it's only "half" of what you need, because it has no way to accept a carry coming in from a less-significant bit position. Chain two half adders together naively and you have nowhere to plug in the carry from bit 0 when you're computing bit 1. We need a third input.

The Full Adder: Adding Three Bits at Once

A full adder takes three single-bit inputs — A, B, and a carry-in, Cin — and produces two outputs, S (sum) and Cout (carry-out). The third input is what lets us chain adders together: the carry-out of bit position i becomes the carry-in of bit position i+1.

Here's the complete truth table — all eight combinations of three inputs:

A	B	Cin	S	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

Deriving the Equations from the Truth Table

Let's not just quote the equations — let's derive them the way a digital design course does, by pattern-matching against the truth table directly.

Sum column first. Read down the S column: 0,1,1,0,1,0,0,1. Count the number of 1s among A, B, Cin in each row. Row by row: 0 ones → S=0; 1 one → S=1; 1 one → S=1; 2 ones → S=0; 1 one → S=1; 2 ones → S=0; 2 ones → S=0; 3 ones → S=1. The pattern is unmistakable: S is 1 exactly when an odd number of the three inputs are 1. That's the defining property of XOR extended to three inputs:

S = A ⊕ B ⊕ Cin

You can sanity-check this associativity claim by noting XOR of two bits already gives you "sum ignoring carry" for those two bits; XOR-ing the third bit in folds its parity into the same odd/even count. Three-input XOR is exactly "1 if an odd number of inputs are 1," which matches every row above.

Carry column next, using a Karnaugh-map style grouping argument instead of just asserting the formula. Lay the truth table out as a grid, with AB on the rows (in Gray-code order so that adjacent rows differ in only one bit) and Cin on the columns:

          Cin=0   Cin=1
AB = 00     0       0
AB = 01     0       1
AB = 11     1       1
AB = 10     0       1

The rule for reading a map like this is: find rectangular blocks of adjacent 1-cells (adjacent meaning they differ in exactly one variable), and each block collapses to a single AND term made of only the variables that stayed constant across that block.

There are four 1-cells: (AB=01, Cin=1), (AB=11, Cin=1), (AB=11, Cin=0), (AB=10, Cin=1). Group them into three overlapping pairs of adjacent cells (overlap is fine — we're building an OR of AND terms, and covering a cell twice doesn't change its value):

(AB=11, Cin=0) and (AB=11, Cin=1) are adjacent (only Cin changes) → A and B are both fixed at 1 across the pair → term A ∧ B.
(AB=01, Cin=1) and (AB=11, Cin=1) are adjacent (only A changes, B and Cin both stay 1) → term B ∧ Cin.
(AB=11, Cin=1) and (AB=10, Cin=1) are adjacent (only B changes, A and Cin both stay 1) → term A ∧ Cin.

Every 1-cell in the grid is covered by at least one of those three pairs, and no 0-cell is covered by any of them. So the carry-out is the OR of the three terms:

Cout = (A ∧ B) ∨ (A ∧ Cin) ∨ (B ∧ Cin)

which is the "majority function" — Cout is 1 whenever at least two of the three inputs are 1. That's an intuitive result once you see it: a carry out of a bit position happens exactly when two or more of the things you're adding at that position are 1, regardless of which two.

A full adder is most commonly built as two half adders plus an OR gate — add A and B with one half adder, add that partial sum to Cin with a second half adder, and OR together the two carry outputs. This is exactly the composition described in GeeksforGeeks's writeup on realizing a full adder from half adders, and it's a nice illustration of how larger combinational blocks compose from smaller ones instead of being derived from a truth table every time.

A Worked Example

Let's run actual bits through it. Take A = 1, B = 1, Cin = 1 — the bottom row of the truth table.

S = A ⊕ B ⊕ Cin = 1 ⊕ 1 ⊕ 1. Compute left to right: 1 ⊕ 1 = 0, then 0 ⊕ 1 = 1. So S = 1.

Cout = (A∧B) ∨ (A∧Cin) ∨ (B∧Cin) = (1∧1) ∨ (1∧1) ∨ (1∧1) = 1 ∨ 1 ∨ 1 = 1.

So the full adder reports Cout S = 11, meaning 3 in binary — and indeed 1 + 1 + 1 = 3. The circuit is doing exactly what "three inputs, sum with carry" should do.

One more, mixed case: A = 1, B = 0, Cin = 1. S = 1 ⊕ 0 ⊕ 1 = 0. Cout = (1∧0) ∨ (1∧1) ∨ (0∧1) = 0 ∨ 1 ∨ 0 = 1. Result: Cout S = 10, which is 2 — matches 1 + 0 + 1 = 2. Both derived equations agree with the original truth table on every row, which is the whole point of doing the derivation instead of just asserting it.

Propagation Delay: Why Ripple-Carry Adders Are Slow

Every real gate takes a nonzero amount of time to settle after its inputs change — this is propagation delay, driven by the physics of charging and discharging transistor gate capacitance. It's typically measured in picoseconds for a modern process node, but it is never zero, and that matters enormously once you start chaining gates together.

Look again at the full adder's carry equation: Cout = (A∧B) ∨ (A∧Cin) ∨ (B∧Cin). Structurally this is two logic levels deep — an AND level feeding an OR level — so in the worst case, a change on Cin takes about two gate-delays to show up on Cout (Cin feeds two of the three AND terms, those ANDs feed the OR). Call that delay t_FA for "full adder carry delay."

Now recall how we chain full adders to build a wide adder: bit 0's Cout feeds bit 1's Cin, bit 1's Cout feeds bit 2's Cin, and so on, all the way up. This structure is called a ripple-carry adder, and the name is literal — the carry has to physically ripple, one full adder at a time, from the least significant bit all the way to the most significant bit before the final sum bits are guaranteed correct.

For an n-bit ripple-carry adder, the worst-case delay from input to a fully-settled output grows linearly with n: roughly n × t_FA. For a 32-bit adder that's 32 sequential carry-propagation stages before you can trust the top bit. This linear scaling is the textbook motivation for why nobody builds a 64-bit or 128-bit ALU as a plain ripple chain in a high-frequency core — the critical path would eat your clock period alive.

A concrete illustration used in several digital-design treatments: with a per-gate delay around 100 picoseconds and roughly 300 picoseconds of carry delay per full adder stage, a 32-bit ripple-carry adder's worst-case delay comes out to roughly 32 × 300 ps ≈ 9.6 ns.

That single number, if it were your entire critical path, would already cap your clock somewhere around 100 MHz — nowhere near the multi-gigahertz clocks real CPUs run at.

The ALU obviously isn't the only thing on the critical path, but it's exactly this kind of arithmetic that makes ripple-carry adders unacceptable for the width and frequency of a real processor.

It helps to actually draw the ripple as a function of time rather than just quoting a delay number. Picture the same 4-bit addition from the worked example above, but now with a rough timeline of when each stage's carry becomes valid, assuming (for round numbers) t_FA = 1 time unit per stage:

Stage 3's sum bit — the most significant bit of the result — is not trustworthy until every stage below it has finished settling. Widen this to 32 bits and the same staircase just gets 28 steps longer. That staircase, not the gate count, is the real argument against ripple-carry at wide bit-widths.

Preview: Carry-Lookahead Adders

The fix — briefly, as a preview, not a full derivation — is to stop waiting for the carry to physically ripple through every stage.

Instead, compute each stage's carry directly from the original inputs using extra "generate" and "propagate" logic, in parallel, ahead of time. This is the carry-lookahead adder (CLA).

It trades more gates and more wiring for a shallower critical path — often reducing delay for wide adders enough that the total delay grows closer to logarithmically with n instead of linearly, especially when CLA blocks are arranged hierarchically.

Using rough figures from the same class of illustrative example above, a 32-bit CLA built from 4-bit lookahead blocks can land around 3.3 ns versus the ripple-carry adder's 9.6 ns — roughly a 3× improvement for the same word width.

We'll leave the actual generate/propagate derivation for a dedicated post later in this series. For now, just carry (no pun intended) the idea that the ripple-carry adder is the conceptually simplest adder, not the fastest one, and real ALUs use faster carry structures once word width and clock target demand it.

Ripple-carry adders are the easiest adder to understand and the first one every digital design course teaches — and also the one real high-frequency ALUs avoid at wide bit-widths, precisely because of this linear delay problem.

Chaining Full Adders into a 32-bit Adder

With the delay caveat noted, the ripple-carry adder is still worth building by hand once, because it's the conceptual backbone everything else refines. Chain 32 full adders, tie Cin of the first one to 0 (there's no carry coming in from "bit -1"), and feed each subsequent Cin from the previous stage's Cout:

Cin0 = 0
For i = 0 to 31:
    (Si, Couti) = FullAdder(Ai, Bi, Cini)
    Cin(i+1) = Couti

Congratulations: that's a 32-bit adder, and it's already a legitimate CPU component — this exact structure, or a faster carry-structure variant of it, sits inside the ALU of essentially every general-purpose processor.

Let's trace a small worked example by hand across a 4-bit slice, since tracing all 32 bits would be repetitive rather than illuminating. Add A = 0111 (7) and B = 0001 (1), expecting 1000 (8):

bit:        3    2    1    0
A:          0    1    1    1
B:          0    0    0    1
Cin:        1    1    1    0   (each Cin is the previous Cout)
 
bit 0: A=1 B=1 Cin=0 → S = 1⊕1⊕0 = 0,  Cout = (1∧1)∨(1∧0)∨(1∧0) = 1
bit 1: A=1 B=0 Cin=1 → S = 1⊕0⊕1 = 0,  Cout = (1∧0)∨(1∧1)∨(0∧1) = 1
bit 2: A=1 B=0 Cin=1 → S = 1⊕0⊕1 = 0,  Cout = (1∧0)∨(1∧1)∨(0∧1) = 1
bit 3: A=0 B=0 Cin=1 → S = 0⊕0⊕1 = 1,  Cout = (0∧0)∨(0∧1)∨(0∧1) = 0
 
Result S3 S2 S1 S0 = 1 0 0 0, final Cout (bit 4) = 0

1000 is 8 in binary, and the carry didn't overflow the 4-bit field (final Cout = 0), so the result is exactly right and fits: 7 + 1 = 8. Notice how the carry rippled through all four stages before bit 3 could settle — that's the propagation-delay story from the previous section, made concrete.

Subtraction for Free: Two's Complement Meets the Adder

This is where Part 1's two's-complement work stops being an abstract numbering scheme and starts being the reason your ALU doesn't need a second circuit for subtraction.

Recall the two's-complement negation rule: to compute -B, invert every bit of B and add 1. Written as an equation:

-B = ¬B + 1

Substitute that into ordinary subtraction, A - B = A + (-B):

A - B = A + ¬B + 1

Look at the right-hand side. A + ¬B + 1 is just an addition — of A, the bitwise-inverted B, and a constant +1.

We already have an adder that takes two n-bit operands and a single carry-in bit. If we route ¬B in as the second operand and tie the adder's Cin to 1 instead of 0, the adder computes A + ¬B + 1 in exactly one pass through the same hardware we already built.

No second circuit, no separate subtractor block — just a row of n XOR gates in front of the B input (to conditionally invert it) and a control line wired into Cin.

When the control line Sub? is 0: each Bi' XOR gate passes Bi through unchanged (Bi ⊕ 0 = Bi), Cin of the first stage is 0, and the chain computes ordinary A + B.

When Sub? is 1: each Bi' XOR gate inverts Bi (Bi ⊕ 1 = ¬Bi), and Cin of the first stage is 1, so the chain computes A + ¬B + 1, which we just showed equals A - B.

One control bit, one row of XOR gates bolted onto an adder you already had to build for ADD. This is precisely the property Part 1 called out as "a beautiful architectural property" — two's complement was chosen so that the representation does the hard work, letting the hardware stay dumb and reusable.

Worked Example: 5 − 3

Use 4 bits for readability. A = 5 = 0101. B = 3 = 0011.

Invert B: 0011 → 1100. Set Cin = 1 (subtract mode). Now add A + ¬B with Cin = 1:

bit:        3    2    1    0
A:          0    1    0    1
¬B:         1    1    0    0
Cin:        1    1    1    1   (bit 0's Cin comes from the Sub? control line = 1)
 
bit 0: A=1 ¬B=0 Cin=1 → S = 1⊕0⊕1 = 0,  Cout = (1∧0)∨(1∧1)∨(0∧1) = 1
bit 1: A=0 ¬B=0 Cin=1 → S = 0⊕0⊕1 = 1,  Cout = (0∧0)∨(0∧1)∨(0∧1) = 0
bit 2: A=1 ¬B=1 Cin=0 → S = 1⊕1⊕0 = 0,  Cout = (1∧1)∨(1∧0)∨(1∧0) = 1
bit 3: A=0 ¬B=1 Cin=1 → S = 0⊕1⊕1 = 0,  Cout = (0∧1)∨(0∧1)∨(1∧1) = 1
 
Result S3 S2 S1 S0 = 0 0 1 0, final Cout (bit 4, discarded) = 1

0010 is 2. 5 - 3 = 2. Correct — and note the final carry-out gets discarded, exactly as Part 1 showed for the 5 + (-3) example, where the top carry bit falls off the end of the register and the remaining bits are the right answer.

Beyond Addition: AND, OR, XOR as First-Class Operations

An adder-subtractor is already useful, but it's nowhere near a complete instruction set. Real programs need to mask bits, set flags, test conditions, and toggle values, none of which is arithmetic in the "numbers" sense — it's bitwise logic applied independently to every bit position. A CPU's ALU needs at least:

ADD
SUB
AND
OR
XOR
SHIFT
COMPARE

The good news is that we've already built the gate for each bitwise operation — AND, OR, and XOR are literally the same three gates from the very first section of this post, just instantiated once per bit position instead of once total. A 32-bit bitwise AND is 32 independent AND gates, each looking only at bit i of A and bit i of B; there's no carry chain, no cross-bit dependency, and (unlike the adder) no propagation-delay horror story — every bit position resolves in parallel, in the time of a single gate.

This is worth sitting with for a second if you come from a software background: x & mask, x | flag, x ^ toggle in C are not "the CPU doing something clever" — they are the most literal, most directly-hardware-mapped operations in the entire instruction set. There is essentially zero abstraction between the C bitwise operator and the silicon.

So the ALU's job is not to invent new circuits for AND/OR/XOR — those already exist as flat, replicated gate arrays. The job is to build one bundle containing the adder-subtractor and the bitwise units side by side, all fed the same A and B, and then pick which one's output actually reaches the outside world on a given cycle. That "pick one" step is a new primitive we haven't built yet.

COMPARE deserves a special mention, because it's usually not a fifth circuit at all — it rides on the subtractor we already have.

Recall the flags Part 1 introduced: Zero, Negative, Carry, Overflow. To evaluate A == B, the ALU quietly computes A - B in SUB mode and checks whether every bit of the result is 0 — that's the Zero flag, a single wide NOR gate over the sum bits, costing almost nothing extra.

To evaluate A < B for signed operands, it inspects the Negative and Overflow flags of that same subtraction rather than building a dedicated less-than circuit.

Worked example: A = 0011 (3), B = 0011 (3). Subtract mode gives A + ¬B + 1, and by the same derivation as the 5 - 3 example above, A - B = 0000. All four result bits are 0, so Zero = 1, meaning A == B reads as true.

COMPARE, in other words, is not new hardware — it's the subtractor's output examined differently.

SHIFT is the other operation on the original list, and it's the odd one out: it needs no gates at all in its simplest form, only wiring. A logical left-shift-by-1 of a 4-bit value just relabels which wire feeds which output position, with a 0 wired into the newly vacated low bit:

0110 (6) shifted left by 1 gives 1100 (12) — a shift-by-1 doubles the value, which is exactly what multiplying by 2 does in binary. A real barrel shifter that can shift by any amount in one cycle is built from a tree of muxes rather than fixed wiring, since the shift amount itself is a runtime value, not a wiring choice fixed at design time — but that's a mux-tree structure detailed enough to deserve its own post rather than a paragraph here.

The Multiplexer: The "Choice" Primitive

2-to-1 Mux

A multiplexer ("mux") is a circuit that selects one of several input signals to pass through to a single output, based on a separate select signal. The simplest version picks between two inputs using one select bit:

If S = 0, Y = A. If S = 1, Y = B. As a Boolean equation:

Y = (¬S ∧ A) ∨ (S ∧ B)

Read it literally: the ¬S ∧ A term only survives (can only be 1) when S = 0, gating A through; the S ∧ B term only survives when S = 1, gating B through. Since S can't be both 0 and 1 at once, exactly one of the two terms is ever "live," and the OR just forwards whichever one is currently alive. This is itself a small combinational circuit — two AND gates, one NOT gate, one OR gate — not a magical primitive, but it earns its own name because of how often it recurs.

Worked example: A = 1, B = 0, S = 1. Y = (¬1 ∧ 1) ∨ (1 ∧ 0) = (0 ∧ 1) ∨ (1 ∧ 0) = 0 ∨ 0 = 0. That matches S=1 → Y=B=0 directly.

4-to-1 Mux for Operation Select

An ALU choosing among four operations (say ADD, AND, OR, XOR) needs to select among four candidate results, which takes two select bits (S1 S0) instead of one, since two bits can encode four distinct codes: 00, 01, 10, 11.

Every operation unit runs on every cycle, on every instruction, whether or not its result is used — this is a deliberate simplicity trade-off in combinational design. It's cheaper (in gate count and design complexity) to compute all four results in parallel and throw three away than to build control logic that only powers up the relevant unit. The mux's job is exclusively to choose which of the four already-computed results becomes visible as Result.

Assign each opcode a 2-bit select code, an entirely arbitrary but fixed choice:

S1 S0 | Operation
------+----------
 0  0 |   ADD
 0  1 |   AND
 1  0 |   OR
 1  1 |   XOR

Building a 4-bit ALU by Hand

Let's put every piece from this post together — full adders, the subtract control line, bitwise gate arrays, and the 4:1 mux — into one small ALU, and run real numbers through it.

Take A = 0110 (6) and B = 0011 (3). We'll compute all four operations in parallel, then use the mux to pick one.

ADD (S1 S0 = 00). Chain four full adders, Cin0 = 0, Sub? = 0 so B passes through unmodified:

bit:        3    2    1    0
A:          0    1    1    0
B:          0    0    1    1
Cin:        0    0    0    0   (rippled forward below)
 
bit 0: A=0 B=1 Cin=0 → S=0⊕1⊕0=1, Cout=(0∧1)∨(0∧0)∨(1∧0)=0
bit 1: A=1 B=1 Cin=0 → S=1⊕1⊕0=0, Cout=(1∧1)∨(1∧0)∨(1∧0)=1
bit 2: A=1 B=0 Cin=1 → S=1⊕0⊕1=0, Cout=(1∧0)∨(1∧1)∨(0∧1)=1
bit 3: A=0 B=0 Cin=1 → S=0⊕0⊕1=1, Cout=(0∧0)∨(0∧1)∨(0∧1)=0
 
ADD result: 1001 = 9

6 + 3 = 9. Correct, and the final carry-out is 0, so it fits cleanly in 4 bits.

AND (S1 S0 = 01). Four independent AND gates, one per bit position, no carry chain at all:

bit:  3  2  1  0
A:    0  1  1  0
B:    0  0  1  1
AND:  0  0  1  0

0110 ∧ 0011 = 0010, which is 2. Check against the source integers: 6 ∧ 3 — bit 1 is the only position where both operands have a 1 — matches.

OR (S1 S0 = 10). Four independent OR gates:

bit: 3  2  1  0
A:   0  1  1  0
B:   0  0  1  1
OR:  0  1  1  1

0110 ∨ 0011 = 0111, which is 7.

XOR (S1 S0 = 11). Four independent XOR gates:

bit:  3  2  1  0
A:    0  1  1  0
B:    0  0  1  1
XOR:  0  1  0  1

0110 ⊕ 0011 = 0101, which is 5.

All four results exist simultaneously, sitting on four parallel buses feeding the 4:1 mux:

ADD → 1001
AND → 0010
OR  → 0111
XOR → 0101

Now suppose the instruction being executed calls for XOR. The control unit (which we haven't built yet — that's a later post) drives S1 S0 = 11 onto the mux select lines. The mux ignores the other three buses entirely and forwards the XOR bus:

Result = 0101  (since S1 S0 = 11 selects XOR)

That's a complete 4-bit ALU cycle: two operands, four candidate results computed in parallel, one selected and forwarded, all inside a single combinational pass with no clock or memory involved anywhere in the circuit.

Scaling to 32 Bits and Beyond

Nothing about the 4-bit ALU above is conceptually different from a 32-bit one. It's the same four blocks (adder-subtractor, AND array, OR array, XOR array) and the same 4:1 mux, just replicated across 32 bit positions instead of 4.

This "replicate a 1-bit or 4-bit slice across the full word width" pattern is exactly how hardware description languages like Verilog and VHDL describe wide ALUs in practice, as covered in Harris & Harris's Digital Design and Computer Architecture. You write the 1-bit slice once, generate it N times, and let synthesis tools stitch the bit-slices together with the appropriate carry wiring.

The one piece that doesn't trivially replicate is the adder's carry chain, for exactly the propagation-delay reason covered earlier. That's why real 32-bit and 64-bit ALUs use carry-lookahead, carry-select, or carry-save structures instead of a plain ripple chain once word width or clock target makes the linear ripple delay unacceptable.

Everything else — the bitwise units, the mux — parallelizes for free, with zero cross-bit dependency, regardless of word width.

A real ALU also typically does more than the four operations traced above: shifts (barrel shifters, a mux-tree structure worth its own post), comparisons (usually built from the subtractor, by examining the sign and zero flags of A - B rather than adding new hardware), and flag generation (Zero, Negative, Carry, Overflow — the same flags introduced in Part 1).

We're deliberately stopping at ADD/SUB/AND/OR/XOR here because those four already contain every idea — truth tables, Boolean derivation, propagation delay, and multiplexed selection — that the rest of the ALU's operations reuse.

Where the ALU Lives in a Real CPU

Zooming out: the ALU we just built is one box inside a much larger pipeline, conventionally in the "Execute" stage.

After an instruction has been fetched and decoded, and after its operands have been read out of the register file, they land on the ALU's A and B inputs. The decoded opcode drives the mux select lines, and the Result bus feeds either a register write-back or a memory address computation.

Every one of the diagrams in this post — the full adder, the ripple chain, the subtract XOR row, the 4:1 mux — is a real, physically-present piece of silicon sitting on that path in something built along conventional lines like a MIPS, RISC-V, or ARM core, not a simplification that gets thrown away once you leave the classroom.

What's still missing is time.

Everything in this post is purely combinational — outputs are a pure function of current inputs, computed in one continuous chain of gate delays, with no notion of "before" or "after."

A CPU obviously needs to remember things across cycles: the contents of a register, the program counter, the state a pipeline is currently in. That's exactly the gap Part 3 closes.

Quick Reference

A compact summary of every equation derived in this post, for lookup without re-reading the derivations:

Circuit	Equation
NOT	`Y = ¬A`
AND	`Y = A ∧ B`
OR	`Y = A ∨ B`
XOR	`Y = A ⊕ B`
Half adder — sum	`Sum = A ⊕ B`
Half adder — carry	`Carry = A ∧ B`
Full adder — sum	`S = A ⊕ B ⊕ Cin`
Full adder — carry-out	`Cout = (A∧B) ∨ (A∧Cin) ∨ (B∧Cin)`
Two's-complement negation	`-B = ¬B + 1`
Subtraction via adder	`A - B = A + ¬B + 1`
2:1 mux	`Y = (¬S∧A) ∨ (S∧B)`
Ripple-carry delay (n bits)	`≈ n × t_FA` (linear in n)