ALU design fundamentals: Visual walkthrough — Hardware deep dive

Before we touch a single formula, let us agree on the tiniest vocabulary.

Every symbol below is built out of just those three ideas.

Step 1 — Adding ONE column: what output do we even need?

WHAT. In any column of an addition we have up to three 1's arriving: the bit $a_{i}$ from number $A$ , the bit $b_{i}$ from number $B$ , and a $c_{i}$ carried in from the column to the right. We must produce two outputs: the digit we write here (the sum bit $s_{i}$ ) and the digit we carry left (the carry-out $c_{i + 1}$ ).

WHY two outputs. Because $1 + 1 = 10$ in binary — a single column can overflow into the next. One output could never encode "0 with a carry" versus "0 with no carry". We need both.

PICTURE. Below, the three input wires enter a box; two wires leave. That box is called a full adder ("full" because it accepts a carry-in, unlike a "half" adder).

The subscript $i$ just means "column number $i$ ", counting from the right starting at 0. See Full Adder for the gate-level guts.

Step 2 — The sum bit is a PARITY question

WHAT. Let us fill in the truth table: for each of the $2^{3} = 8$ combinations of $(a_{i}, b_{i}, c_{i})$ , what should $s_{i}$ be?

WHY parity. Look at the table in the figure. The sum digit is 1 exactly when an odd number of the three inputs is 1 (one 1, or three 1's). "Odd count of 1's" is precisely what XOR computes when you chain it. So:

$s_{i} = this bit of A a_{i} \oplus this bit of B b_{i} \oplus carry from the right c_{i}$

Each $\oplus$ says "flip me if this input is 1". Start at 0; feeding three 1's flips it three times → ends at 1. Feeding two 1's flips twice → back to 0. That is exactly the "odd" rule.

PICTURE. The truth table with the odd rows highlighted, and the parity chain beside it.

Step 3 — The carry-out is a MAJORITY question

WHAT. Same 8 rows, but now: when do we carry a 1 to the next column?

WHY majority. You carry when two or more of the three inputs are 1 (the running total reaches 2 or 3). "At least two of three" is the majority function. We split it into two readable pieces:

$c_{i + 1} = generate: both operand bits are 1 a_{i} b_{i} + propagate: exactly one is 1 AND a carry came in c_{i} (a_{i} \oplus b_{i})$

$a_{i} b_{i}$ (AND) is 1 only when both $A$ and $B$ contribute a 1 here — a carry is born regardless of $c_{i}$ . This term is called generate.
$a_{i} \oplus b_{i}$ is 1 when exactly one of them is 1. Multiplied by $c_{i}$ , it means "a lone 1 here, plus the incoming carry, makes two" — the carry is passed through. This is called propagate.
The $+$ between them is OR: carry if either reason holds.

PICTURE. The majority table with the "generate" rows and "propagate" rows shaded differently.

We now own a complete 1-bit adder: $s_{i} = a_{i} \oplus b_{i} \oplus c_{i}$ and $c_{i + 1} = a_{i} b_{i} + c_{i} (a_{i} \oplus b_{i})$ . Everything else is copying it.

Step 4 — Chain them: the Ripple-Carry Adder

WHAT. Stack four full adders side by side. Wire each adder's carry-out into the next adder's carry-in. The rightmost carry-in is $c_{0}$ ; the leftmost carry-out is $c_{4}$ .

WHY chain. A single adder handles one column; a number has many columns. The carry must "ripple" leftward exactly as it does when you add on paper — column 0 finishes and hands its carry to column 1, and so on. This structure is literally the Ripple Carry Adder.

$start c_{0} \to FA_{0} \to c_{1} \to FA_{1} \to c_{2} \to FA_{2} \to c_{3} \to FA_{3} \to final c_{4}$

PICTURE. Four adder boxes in a row, the carry wire snaking through them like a red thread.

Step 5 — Subtraction is addition in disguise

WHAT. We want the same box to also compute $A - B$ . In Two's Complement, the negative of a number is "flip every bit, then add 1":

$- B = \overline{B} + 1 ⟹ A - B = A + \overline{B} + 1$

$\overline{B}$ means each bit of $B$ flipped (0↔1). Picture every lamp inverted.
The $+ 1$ is the finishing touch that makes flip-and-add equal true negation.

WHY this is a gift. We already have an adder. If we can (a) optionally flip $B$ and (b) optionally inject a starting $+ 1$ , we get subtraction with no new arithmetic hardware.

PICTURE. $B$ becoming $\overline{B}$ on a number line, and the $+ 1$ nudging it to the true $- B$ position.

Step 6 — One control bit does BOTH tricks at once

WHAT. Introduce a single control wire $S_{sub}$ . Route each bit of $B$ through an XOR gate with $S_{sub}$ , and feed $S_{sub}$ itself into $c_{0}$ :

$b_{i}^{'} = b_{i} \oplus S_{sub}, c_{0} = S_{sub}$

WHY XOR is the perfect switch. Recall $x \oplus 0 = x$ and $x \oplus 1 = \overline{x}$ . So:

$S_{sub} = 0$ : every $b_{i}^{'} = b_{i}$ (unchanged) and $c_{0} = 0$ → the box computes $A + B$ . Addition.
$S_{sub} = 1$ : every $b_{i}^{'} = \overline{b_{i}}$ (flipped) and $c_{0} = 1$ → the box computes $A + \overline{B} + 1 = A - B$ . Subtraction.

XOR is the controllable inverter: pass-through or flip, chosen by one wire. That is why we use XOR here and not a plain OR or AND — only XOR gives you "invert on demand".

PICTURE. The full adder chain with the row of XOR gates on the $B$ inputs and $S_{sub}$ threaded into $c_{0}$ .

Step 7 — Reading the flags (every sign covered)

WHAT. From the 4-bit result $F = F_{3} F_{2} F_{1} F_{0}$ and the carries, we squeeze out four status bits (see Status Flags and Condition Codes):

$Z = \overline{F_{3} + F_{2} + F_{1} + F_{0}}, C = c_{4}, N = F_{3}, V = c_{4} \oplus c_{3}$

$Z$ (Zero): the OR of all result bits, then NOT. The OR is 1 if any bit is 1; NOT makes $Z = 1$ only when all bits are 0 — i.e. the result is exactly zero.
$C$ (Carry): simply $c_{4}$ , the carry falling off the top. For unsigned numbers this is overflow.
$N$ (Negative/Sign): just the top bit $F_{3}$ . In two's complement, MSB $= 1$ means the number is negative — no computation needed.
$V$ (Overflow, signed): $c_{4} \oplus c_{3}$ — the carry into the sign column XOR the carry out of it. If they disagree, the sign bit got corrupted and the signed answer is wrong.

WHY $V = c_{4} \oplus c_{3}$ . The sign bit should only change for legitimate reasons. If a carry enters the sign column but none leaves (or vice-versa), the sign flipped by accident — that is exactly signed overflow, and XOR detects "these two carries disagree".

PICTURE. The 4-bit result with each flag arrow pointing to what it reads.

The one-picture summary

Everything above collapses into a single diagram: four full adders in a row, a row of XOR gates letting $S_{sub}$ flip $B$ and seed $c_{0}$ , and the flag logic tapping the outputs.

Recall Feynman retelling — explain the walkthrough to a 12-year-old

Adding binary is just like adding on paper: in each column you may get three 1's (the two digits plus a "carried" 1). You write down a 1 only when an odd number of them showed up (that is the XOR "flip switch" chain), and you carry a 1 whenever two or more showed up (the majority rule). Line up four of these column-machines and let the carry hop leftward like a domino — that is your adder. Now the sneaky part: to subtract $B$ , flip all of $B$ 's lamps and secretly add 1 at the very start. We do the flipping with a single switch called $S_{sub}$ wired through XOR gates, and we sneak the +1 in by making that same switch the first carry. Flip it off → you add; flip it on → you subtract, with the exact same boxes. Finally we glance at the answer: all-lamps-off means Zero, the top lamp tells the sign, the carry that fell off the top is the unsigned overflow, and if the carry going into the top column disagrees with the one coming out, the sign got scrambled — that is signed overflow. Do everything at once, then let a little selector hand you the answer you asked for.

Connections

Full Adder — the single-column box of Steps 1–3
Ripple Carry Adder — the chaining of Step 4
Two's Complement — why flip-and-add-one negates (Step 5)
Carry Lookahead Adder — removing the ripple delay
Multiplexer — selecting arithmetic vs logic output
Status Flags and Condition Codes — using Z, C, N, V
Datapath and Control Unit — where this ALU lives
← back to parent