---
title: Multiplexers, Decoders, and the ALU
module: Digital Logic
moduleNumber: 3
lessonNumber: 3
order: 303
summary: >
  The combinational building blocks that make a datapath. We build the 2:1 and 4:1
  multiplexer and tie it back to HCL's case expression, the n-to-2^n decoder, a
  one-bit full adder (sum is XOR, carry is majority), the ripple-carry adder that
  chains them, and finally the ALU — a function unit that selects among add, sub,
  and, and xor under a control input and exposes condition flags.
topics: [Digital Logic]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §4.2 Logic Design and the Hardware Control Language"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §2 Basic Organization of a Computer"
---

The [last lesson](/computer-architecture/digital-logic/combinational-logic-and-hcl)
described combinational logic in HCL and claimed the `case` expression is a
multiplexer. This lesson cashes that in. We build the standard combinational
**function units** (multiplexers, decoders, adders, and finally the arithmetic
logic unit) that together form the computational core of a processor's datapath.
Every block here is pure combinational logic: a Boolean function of its current
inputs.

## The multiplexer: a data selector

A **multiplexer** (mux) routes one of several data inputs to a single output,
chosen by a set of **select** lines. A $2{:}1$ mux has two data inputs $d_0, d_1$,
one select bit $s$, and output $y = s\,?\,d_1 : d_0$. As a Boolean function,
$y = \overline{s}\,d_0 + s\,d_1$: when $s = 0$ the first AND passes $d_0$ and the
second is killed; when $s = 1$ the reverse. A $4{:}1$ mux needs two select bits to
name one of four inputs.

$$
% caption: A 2:1 mux (left) selects d0 or d1 with one select bit s; a 4:1 mux
% caption: (right) selects one of four inputs with two select bits s1 s0. The
% caption: select value, read as a binary number, names the chosen input.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  mux/.style={draw, fill=acc!8, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % 2:1 mux drawn as a trapezoid via a tall thin box
  \node[mux, minimum width=12mm, minimum height=18mm] (m2) at (0,0) {2:1};
  \node[anchor=east] at (-1.6,0.5) {$d_0$};
  \node[anchor=east] at (-1.6,-0.5) {$d_1$};
  \draw (-1.6,0.5) -- (-0.6,0.5);
  \draw (-1.6,-0.5) -- (-0.6,-0.5);
  \draw (m2.east) -- ++(1.2,0) node[anchor=west,text=acc] {$y$};
  \node[anchor=north] at (0,-1.3) {$s$};
  \draw (0,-1.1) -- (m2.south);
  % 4:1 mux
  \node[mux, minimum width=12mm, minimum height=30mm] (m4) at (6,0) {4:1};
  \foreach \i/\y in {0/1.05,1/0.35,2/-0.35,3/-1.05}
    \node[anchor=east] at (4.4,\y) {$d_\i$};
  \draw (4.4,1.05) -- (5.4,1.05);
  \draw (4.4,0.35) -- (5.4,0.35);
  \draw (4.4,-0.35) -- (5.4,-0.35);
  \draw (4.4,-1.05) -- (5.4,-1.05);
  \draw (m4.east) -- ++(1.2,0) node[anchor=west,text=acc] {$y$};
  \node[anchor=north] at (5.6,-1.9) {$s_1$};
  \node[anchor=north] at (6.4,-1.9) {$s_0$};
  \draw (5.6,-1.7) -- (5.6,-1.5);
  \draw (6.4,-1.7) -- (6.4,-1.5);
\end{tikzpicture}
$$

Inside, a $4{:}1$ mux is one AND per data input — each gated by the select
combination that names it — feeding one OR. Writing the two select bits as
$s_1 s_0$, the Boolean form is

$$
y = \overline{s_1}\,\overline{s_0}\,d_0 \;+\; \overline{s_1}\,s_0\,d_1 \;+\;
    s_1\,\overline{s_0}\,d_2 \;+\; s_1\,s_0\,d_3.
$$

Each product is a data input ANDed with a **decoded** select: the four select
combinations are the one-hot outputs of a 2-to-4 decoder. So a mux is a
decoder driving a bank of AND gates whose outputs OR together — one figure below
made of parts from this same lesson.

$$
% caption: A 4:1 mux built from gates. The select bits s1 s0 are decoded into four
% caption: one-hot lines; each ANDs with one data input; the four AND outputs OR
% caption: into y. Only the line matching the select value passes its data.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  g/.style={draw, minimum width=11mm, minimum height=7mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\y/\sel in {0/3.0/{$\overline{s_1}\,\overline{s_0}$},
                          1/2.0/{$\overline{s_1}\,s_0$},
                          2/1.0/{$s_1\,\overline{s_0}$},
                          3/0.0/{$s_1\,s_0$}}{
    \node[g] (a\i) at (1.6,\y) {AND};
    \node[anchor=east] at (0.1,\y+0.18) {$d_\i$};
    \draw (0.1,\y+0.18) -- (0.95,\y+0.18);
    \node[anchor=east] at (0.1,\y-0.18) {\sel};
    \draw (0.6,\y-0.18) -- (0.95,\y-0.18);
  }
  \node[g, fill=acc!8, minimum height=30mm] (or) at (4.4,1.5) {OR};
  \foreach \i/\y in {0/3.0, 1/2.0, 2/1.0, 3/0.0}
    \draw (a\i.east) -- (a\i.east -| 3.85,\y) -- (3.85,1.5);
  \draw (3.85,3.0) -- (3.85,0.0);
  \draw (or.east) -- ++(1.2,0) node[anchor=west, text=acc] {$y$};
\end{tikzpicture}
$$

Trace a selection. With $s_1 s_0 = 10$, the decoded line $s_1\overline{s_0}$ is
$1$ and the other three are $0$; the third AND passes $d_2$ while the others
force $0$, so the OR sees only $d_2$ and $y = d_2$. Change the select to $01$ and
the second AND opens instead, routing $d_1$. The select value, read as a binary
number, is the index of the data input that reaches the output — a data selector,
exactly as promised.

This is the hardware behind HCL's `case`: a `case` with $n$ selects compiles to a
mux tree, with the top-of-list priority resolving overlapping selects. Mutually
exclusive selects, like a one-hot control field, give a clean $n{:}1$ mux where
the select code names the chosen input directly. Muxes are everywhere in a
datapath: choosing whether the ALU's second operand comes from a register or an
immediate, choosing which value to write back, choosing the next instruction
address.

## The decoder: select one of $2^n$ lines

A **decoder** takes an $n$-bit input and asserts exactly
**one** of $2^n$ output lines — the one whose index equals the input value. It is
**one-hot**: output line $i$ is $1$ iff the input equals $i$, all others $0$. Each
output is one minterm of the input bits, so a $2$-to-$4$ decoder is four AND gates
fed by the inputs and their complements.

$$
% caption: A 2-to-4 decoder. The 2-bit input a1 a0 drives exactly one of four
% caption: output lines high — the one whose index equals the input. Each output is
% caption: a minterm: y2 is high only when a1 a0 = 10.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  dec/.style={draw, fill=acc!8, minimum width=16mm, minimum height=28mm,
              inner sep=2pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[dec] (d) at (0,0) {2-to-4\\decoder};
  \node[anchor=east] at (-1.8,0.35) {$a_1$};
  \node[anchor=east] at (-1.8,-0.35) {$a_0$};
  \draw (-1.8,0.35) -- (d.west |- 0,0.35);
  \draw (-1.8,-0.35) -- (d.west |- 0,-0.35);
  \foreach \i/\y/\note in {0/1.05/{$=\!00$}, 1/0.35/{$=\!01$}, 2/-0.35/{$=\!10$}, 3/-1.05/{$=\!11$}}{
    \draw (d.east |- 0,\y) -- ++(1.5,0) node[anchor=west,text=acc] {$y_\i$};
    \node[anchor=west] at (2.9,\y) {\note};
  }
\end{tikzpicture}
$$

Decoders pick out one item from a numbered set: the natural job is **address
decoding**, turning a register number or memory address into a single "select this
word" line, which is how the register file and memory array in the next two
lessons choose which storage cell to touch.

## The full adder

Arithmetic starts at one bit column. Adding two bits $a$ and $b$ plus an incoming
**carry** $c_{in}$ produces a **sum** bit and an outgoing **carry**. This is a
**full adder**, and its two outputs are functions we have already met:

$$
\text{sum} = a \oplus b \oplus c_{in}, \qquad
c_{out} = (a \cdot b) + (a \cdot c_{in}) + (b \cdot c_{in}).
$$

The sum is $1$ when an **odd** number of the three inputs are $1$: that is the
three-input XOR (parity). The carry is $1$ when **at least two** of the three
inputs are $1$: the **majority** function from lesson 1. Check the corner: with
$a = b = c_{in} = 1$, sum $= 1 \oplus 1 \oplus 1 = 1$ and $c_{out} = 1$, i.e. $1 +
1 + 1 = 11_2 = 3$, sum $1$ carry $1$. Correct.

$$
% caption: A one-bit full adder as two function blocks. A 3-input XOR computes the
% caption: parity (sum = a XOR b XOR cin); a majority block computes the carry out
% caption: (1 when at least two of a, b, cin are 1). Each input fans to both blocks.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  g/.style={draw, fill=acc!8, minimum width=30mm, minimum height=11mm,
            inner sep=2pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % two function blocks, stacked
  \node[g] (xor) at (0.4,1.4) {3-input XOR\\(parit\/y)};
  \node[g] (maj) at (0.4,-1.4) {majorit\/y\\$ab+ac_{in}+bc_{in}$};
  % a: trunk at x=-4.6, taps into the top row of each block
  \node[anchor=east] at (-4.8,2.2) {$a$};
  \draw (-4.8,2.2) -- (-4.6,2.2);
  \draw (-4.6,2.2) -- (-4.6,-1.1) -- (-1.1,-1.1);
  \draw (-4.6,1.7) -- (-1.1,1.7);
  \fill (-4.6,1.7) circle (1.1pt);
  % b: enters at the XOR's middle row, trunk at x=-4.3 drops to the majority row
  \node[anchor=east] at (-4.8,1.4) {$b$};
  \draw (-4.8,1.4) -- (-1.1,1.4);
  \draw (-4.3,1.4) -- (-4.3,-1.4) -- (-1.1,-1.4);
  \fill (-4.3,1.4) circle (1.1pt);
  % cin: enters between the blocks, trunk at x=-4.0 feeds both bottom rows
  \node[anchor=east] at (-4.8,0.6) {$c_{in}$};
  \draw (-4.8,0.6) -- (-4.0,0.6);
  \draw (-4.0,1.1) -- (-4.0,-1.7) -- (-1.1,-1.7);
  \draw (-4.0,1.1) -- (-1.1,1.1);
  \fill (-4.0,0.6) circle (1.1pt);
  % outputs
  \draw (xor.east) -- ++(1.8,0) node[anchor=west,text=acc] {sum};
  \draw (maj.east) -- ++(1.8,0) node[anchor=west,text=acc] {$c_{out}$};
\end{tikzpicture}
$$

## Ripple-carry: chaining full adders

To add two $n$-bit numbers, place $n$ full adders side by side, one per bit
position, and feed each adder's carry-out into the next adder's carry-in. The
carry **ripples** from the low bit to the high bit. The carry into bit $0$ is the
overall carry-in $c_0$ (set it to $1$ for subtraction, below), and the carry out of
the top bit is the overall carry-out.

$$
% caption: A 4-bit ripple-carry adder. Each full adder FAi adds ai, bi, and the
% caption: carry ci from the stage below, producing sum si and carry c(i+1). The
% caption: carry chain runs right-to-left from c0 to c4.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  fa/.style={draw, fill=acc!8, minimum width=15mm, minimum height=14mm,
             inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\x in {0/0, 1/2.6, 2/5.2, 3/7.8}{
    \node[fa] (f\i) at (\x,0) {FA$_\i$};
    % operand inputs from the top
    \draw (\x-0.35,1.6) node[anchor=south] {$a_\i$} -- (\x-0.35,0.7);
    \draw (\x+0.35,1.6) node[anchor=south] {$b_\i$} -- (\x+0.35,0.7);
    % sum output to the bottom
    \draw (\x,-0.7) -- (\x,-1.5) node[anchor=north,text=acc] {$s_\i$};
  }
  % carry chain right to left: c0 -> f0 -> f1 -> ... -> c4
  \draw (9.0,0) node[anchor=west] {} ;
  \draw (8.55,0) -- (9.3,0) node[anchor=west,text=acc] {$c_4$};
  \draw (f3.west) -- (f2.east);
  \draw (f2.west) -- (f1.east);
  \draw (f1.west) -- (f0.east);
  \draw (-1.3,0) node[anchor=east] {$c_0$} -- (f0.west);
  % label one carry on the wire
  \node[anchor=south] at (1.3,0.05) {$c_1$};
  \node[anchor=south] at (3.9,0.05) {$c_2$};
  \node[anchor=south] at (6.5,0.05) {$c_3$};
\end{tikzpicture}
$$

Ripple-carry is correct but slow, and the
[critical-path accounting](/computer-architecture/digital-logic/combinational-logic-and-hcl)
of the last lesson says exactly how slow. Each stage's carry-out is the majority
function, a two-level AND-OR circuit, so the carry chain costs about **2 gate
delays per bit**: $c_1$ settles at $2\Delta$, $c_2$ at $4\Delta$, and $c_{64}$ at
$128\Delta$. The top sum bit needs $c_{63}$ plus one more XOR, so a 64-bit ripple
adder is roughly $130$ gate delays deep. At 25 ps per level that is $3.2$ ns for
one addition: a 300 MHz clock in a machine whose other blocks settle ten times
faster. The delay is **linear in $n$**, and the adder sits on the critical path
of nearly every instruction. Real adders spend gates to buy depth.

## Carry-lookahead: computing carries in parallel

The ripple is slow because each carry waits for the previous one. But bit $i$'s
**relationship** to the carry is determined before the carry arrives. From $a_i$
and $b_i$ alone:

- if $a_i = b_i = 1$, the column **generates** a carry no matter what comes in:
  $g_i = a_i \cdot b_i$;
- if exactly one of $a_i, b_i$ is $1$, the column **propagates** an incoming
  carry: $p_i = a_i \oplus b_i$.

Every $g_i$ and $p_i$ is ready after **one** gate level, all in parallel. The
carry recurrence $c_{i+1} = g_i + p_i\,c_i$ then unrolls by substitution:

$$
\begin{aligned}
c_1 &= g_0 + p_0 c_0 \\
c_2 &= g_1 + p_1 g_0 + p_1 p_0 c_0 \\
c_3 &= g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0 \\
c_4 &= g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 + p_3 p_2 p_1 p_0 c_0.
\end{aligned}
$$

Read $c_2$ aloud: bit $1$ generated a carry, or it propagated one that bit $0$
generated, or both columns propagated the original $c_0$. Each right-hand side is
a two-level AND-OR circuit of signals available after one level, so **all four
carries of a 4-bit group settle in about 3 gate delays**, independent of one
another, no ripple.

The unrolling cannot continue forever: $c_{16}$ written this way is an OR of
17 terms, one an AND of 16 inputs, and the
[fan-in cost](/computer-architecture/digital-logic/transistors-gates-and-boolean-functions)
of such wide gates eats the savings. So the trick is applied **hierarchically**.
A 4-bit group condenses itself into a group generate and group propagate,

$$
G = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0, \qquad
P = p_3\,p_2\,p_1\,p_0,
$$

which record whether the group produces a carry and whether it passes one along —
the same two facts as for a single column, now at group scale. A second-level
lookahead unit treats the groups as super-columns and computes every group's
carry-in from the $(G, P)$ pairs and $c_0$ in two more levels.

$$
% caption: A carry-lookahead tree over 16 bits. Each 4-bit block computes its
% caption: internal carries plus a group (G, P) in parallel; the second-level unit
% caption: computes c4, c8, c12 from the four (G, P) pairs and c0. Two levels cover
% caption: 16 bits; three cover 64. Depth grows with log n, not n.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  blk/.style={draw, fill=acc!8, minimum width=20mm, minimum height=11mm,
              inner sep=2pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[blk] (b3) at (0,0) {bits 12-15};
  \node[blk] (b2) at (2.7,0) {bits 8-11};
  \node[blk] (b1) at (5.4,0) {bits 4-7};
  \node[blk] (b0) at (8.1,0) {bits 0-3};
  \node[draw, minimum width=92mm, minimum height=11mm, align=center]
    (root) at (4.05,2.4) {second-level lookahead:\\$c_4$, $c_8$, $c_{12}$ from all ($G$, $P$) and $c_0$};
  % G,P up-arrows (left offset), carry down-arrows (right offset)
  \foreach \i/\x in {3/0, 2/2.7, 1/5.4, 0/8.1}{
    \draw[->] (\x-0.3,0.55) -- (\x-0.3,1.85);
  }
  \foreach \x in {0, 2.7, 5.4}{
    \draw[->, acc, thick] (\x+0.3,1.85) -- (\x+0.3,0.55);
  }
  \node[anchor=east] at (-0.35,1.2) {$G_3$, $P_3$};
  \node[anchor=west, text=acc] at (0.35,1.2) {$c_{12}$};
  \node[anchor=west, text=acc] at (3.05,1.2) {$c_8$};
  \node[anchor=west, text=acc] at (5.75,1.2) {$c_4$};
  \node[anchor=west] at (7.9,1.2) {$G_0$, $P_0$};
  % c0 into the root and into block 0
  \draw[->] (9.9,2.4) node[anchor=west] {$c_0$} -- (root.east);
  \draw[->] (9.9,0) node[anchor=west] {$c_0$} -- (b0.east);
\end{tikzpicture}
$$

Count the depth for 64 bits: one level for all $g_i, p_i$, two for group
$(G, P)$s, two per tree level for the carries coming back down, one XOR for the
sums: on the order of **a dozen gate delays** regardless of width, against
$130$ for the ripple. At 25 ps per level that is roughly $0.3$ ns instead of
$3.2$. The price is the lookahead logic itself, a few extra gates per bit; every
serious adder pays it. The pattern — replace a linear chain with a
$\log$-depth tree — is the same one the equality net of the previous lesson used,
and it recurs throughout hardware design.

## The ALU: a function unit with a control input

An **arithmetic logic unit** packages several operations into one block and uses a
**control** input to select which result appears at the output. The standard
teaching ALU (CS:APP's) takes two word operands $A$ and $B$ and a small function
code, and produces a result plus **condition flags**.

$$
% caption: An ALU. Two word operands A and B enter; a control code selects which
% caption: operation drives the result; condition flags (zero, sign, carry,
% caption: overflow) report properties of that result.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ALU body as a notched block (use a wide trapezoid-ish box)
  \node[draw, fill=acc!8, minimum width=30mm, minimum height=26mm,
        align=center] (alu) at (0,0) {ALU};
  % operands in from the left
  \node[anchor=east] at (-3.0,0.6) {$A$};
  \node[anchor=east] at (-3.0,-0.6) {$B$};
  \draw (-3.0,0.6) -- (alu.west |- 0,0.6);
  \draw (-3.0,-0.6) -- (alu.west |- 0,-0.6);
  % control in from the top
  \node[anchor=south] at (0,1.9) {function code};
  \draw (0,1.85) -- (alu.north);
  % result out to the right
  \draw (alu.east |- 0,0.4) -- ++(1.8,0) node[anchor=west,text=acc] {result};
  % f\/lags out from the bottom
  \draw (alu.south -| -1.0,0) -- ++(0,-1.0) node[anchor=north] {ZF};
  \draw (alu.south -| 0.0,0) -- ++(0,-1.0) node[anchor=north] {SF};
  \draw (alu.south -| 1.0,0) -- ++(0,-1.0) node[anchor=north] {CF/OF};
  % operation legend to the right, clear of wires
  \node[anchor=west, align=left] at (2.6,-0.6)
    {\footnotesize 00: add\\01: subtract\\10: AND\\11: XOR};
\end{tikzpicture}
$$

Internally the ALU computes **all** the operations in parallel and a final mux
picks the selected one — exactly the `case`-to-mux pattern. Two details make it
practical. First, **subtraction reuses the adder**: $A - B = A + \overline{B} + 1$,
so feeding the adder the complement of $B$ and setting the carry-in $c_0 = 1$ turns
add into subtract with no extra adder. Second, the **flags** are computed from the
result: **ZF** (zero) is $1$ when every result bit is $0$, **SF** (sign) is the top
result bit, **CF** (carry) is the adder's carry-out, and **OF** (overflow) signals
signed overflow. These flags are what conditional branches later test. Not every
ISA keeps all four: Y86-64's condition codes hold only `ZF`, `SF`, and `OF` — it
has no unsigned branches — while `CF` is needed in ISAs like x86-64, whose
unsigned [`ja`/`jb` family](/computer-architecture/machine-level-x86-64/control-flow)
reads it.

### One bit of the ALU

Slice the ALU at a single bit position and every idea in this lesson appears in
one small circuit. The slice computes AND, OR, and the full adder's sum for its
bit, all three at once, and an operation mux steers one to the result. An
**invert** control sits in front of the adder's $b$ input, choosing between
$b_i$ and $\overline{b_i}$; drive `invert = 1` and $c_0 = 1$ together and the
chained slices compute $a + \overline{b} + 1 = a - b$.

$$
% caption: A one-bit ALU slice. AND, OR, and the adder's sum are all computed in
% caption: parallel; the op mux selects one as the result. The invert mux feeds the
% caption: adder b or NOT b, so invert = 1 with carry-in 1 turns add into subtract.
% caption: Chaining cout to the next slice's cin ripples the design to n bits.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  g/.style={draw, minimum width=12mm, minimum height=8mm, inner sep=1pt},
  mx/.style={draw, fill=acc!8, minimum width=12mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % function blocks
  \node[g] (and) at (3.0,2.4) {AND};
  \node[g] (or) at (3.0,1.4) {OR};
  \node[g, minimum height=10mm] (add) at (3.0,0.2) {add};
  % a input from the top-left, trunk fans to all three upper inputs
  \node[anchor=south] at (0.9,2.95) {$a$};
  \draw (0.9,2.95) -- (0.9,0.4);
  \draw (0.9,2.58) -- (2.4,2.58);
  \draw (0.9,1.58) -- (2.4,1.58);
  \draw (0.9,0.4) -- (2.4,0.4);
  \fill (0.9,2.58) circle (1.1pt);
  \fill (0.9,1.58) circle (1.1pt);
  % binvert mux and b input
  \node[mx, minimum height=8mm] (bm) at (-0.4,1.0) {$b$ or $\overline{b}$};
  \draw (-2.2,1.0) node[anchor=east] {$b$} -- (-1.0,1.0);
  \node[anchor=south] at (-0.4,2.95) {invert};
  \draw (-0.4,2.95) -- (-0.4,1.4);
  % b trunk fans to all three lower inputs
  \draw (0.2,1.0) -- (1.3,1.0);
  \draw (1.3,2.22) -- (1.3,0.0);
  \draw (1.3,2.22) -- (2.4,2.22);
  \draw (1.3,1.22) -- (2.4,1.22);
  \draw (1.3,0.0) -- (2.4,0.0);
  \fill (1.3,1.0) circle (1.1pt);
  \fill (1.3,1.22) circle (1.1pt);
  % carry in and carry out
  \draw (2.7,-0.95) node[anchor=north] {$c_{in}$} -- (2.7,-0.3);
  \draw[->] (3.3,-0.3) -- (3.3,-0.75) -- (4.6,-0.75)
    node[anchor=west] {$c_{out}$ to next slice};
  % op mux
  \node[mx, minimum height=16mm] (m) at (5.6,1.4) {mux};
  \draw (3.6,2.4) -- (4.4,2.4) -- (4.4,1.9) -- (5.0,1.9);
  \draw (3.6,1.4) -- (5.0,1.4);
  \draw (3.6,0.2) -- (4.4,0.2) -- (4.4,0.9) -- (5.0,0.9);
  \node[anchor=south] at (5.6,2.95) {op};
  \draw (5.6,2.95) -- (5.6,2.2);
  \draw (m.east) -- ++(1.2,0) node[anchor=west, text=acc] {result$_i$};
\end{tikzpicture}
$$

Work one subtraction through the 4-bit version. Compute
$6 - 3$: $a = 0110$, $b = 0011$, so $\overline{b} = 1100$, and with $c_0 = 1$
the adders produce $0110 + 1100 + 1 = 1\,0011$. The carry out of the top bit
falls off the end, leaving $0011 = 3$. Discarding that carry is the modular
wraparound of
[two's-complement arithmetic](/computer-architecture/foundations/integer-representation),
and the ALU's OF logic checks the top two carries to flag the cases where
wraparound changes the sign incorrectly.

```c [alu.hcl]
word aluResult = [
    fn == ALU_ADD : A + B;
    fn == ALU_SUB : A - B;
    fn == ALU_AND : A & B;
    fn == ALU_XOR : A ^ B;
];
bool ZF = (aluResult == 0);   /* zero flag: result is all zeros */
```

The HCL reads as a four-way `case` on the function code. The gates it stands for:
an adder/subtractor, an AND array, an XOR array, and a $4{:}1$
mux steering one result out under `fn`, with a zero-detect net on the side.

## Faster adders and hardware multiply

CS:APP builds the ripple adder, sketches lookahead, and moves on. The public
adder literature is deeper, and the same generate/propagate algebra underlies all
of it.

**Prefix adders.** The recurrence $c_{i+1} = g_i + p_i c_i$ is an instance of a
**parallel prefix** computation: define a combine operator on $(g, p)$ pairs,
$(g', p') \bullet (g, p) = (g' + p' g,\; p' p)$, and every carry is a prefix
"sum" under $\bullet$. Because $\bullet$ is associative, the prefixes can be
computed by a balanced tree in $\log_2 n$ depth — which is what carry-lookahead
does, stated abstractly. Different tree shapes trade depth against wiring:
**Kogge–Stone** (1973) is shallowest and widest (lots of wires, minimal depth),
**Brent–Kung** (1982) is deeper but far sparser, and **Ladner–Fischer** and
**Han–Carlson** sit between. A modern 64-bit adder in a high-frequency core is
usually a hybrid of these, chosen to fit the wire budget of its slot. All of them
compute exactly the carries this lesson unrolled by hand; they differ only in how
they share the sub-products.

**Multiplication.** The ALU here does add, subtract, AND, XOR — not multiply,
because multiply does not fit the two-level template. An $n \times n$ multiply is
$n$ shifted partial products summed, and the public techniques attack both halves.
**Booth's algorithm** (1951) and its radix-4 modified form roughly halve the
number of partial products by recoding the multiplier. A **Wallace tree** (1964)
or **Dadda tree** (1965) then sums those partial products in $\log$ depth using
carry-save adders — full adders wired to defer the carry instead of rippling it —
collapsing the sum to two numbers that one final fast adder combines. That is why
a hardware multiply, naively $O(n)$ additions, costs only a handful of gate levels
more than a single add.

**Where the ALU went.** The single-function-code ALU is the SISD picture. Modern
cores replicate it: a superscalar processor has several integer ALUs plus separate
multiply, divide, and floating-point units, and **SIMD** vector units (x86's
AVX-512, ARM's SVE) apply one operation across many lanes of a wide register in
parallel — the same one-bit slice tiled 512 ways with the carry chains broken at
lane boundaries. The condition flags this lesson emits are still the interface a
branch reads, unchanged since the 8086.

> **Takeaway.** A multiplexer selects one of several data inputs by a select code
> and is the hardware behind HCL's `case`; a decoder turns an $n$-bit value into one
> hot output line. A full adder computes sum $= a \oplus b \oplus c_{in}$ and carry
> $=$ majority; chaining them gives a ripple-carry adder whose delay grows linearly
> at about two gate levels per bit, and carry-lookahead's generate/propagate tree
> cuts that to logarithmic depth. The ALU computes several operations at once and
> muxes out the one its control input selects, reusing the adder for subtraction
> via $A + \overline{B} + 1$ and emitting the condition flags branches later test.

So far every block forgets its inputs the instant they change. The
[next lesson](/computer-architecture/digital-logic/memory-elements-latches-flip-flops-and-clocking)
adds **memory** by deliberately introducing the feedback combinational logic
forbade.