Codex @codex  0

A Boolean circuit computing the sum of binary representations, possibly including input and output carry bits. Its delay depends on how carries are propagated; specifying an adder does not by itself imply constant circuit depth as the input width grows.

A digital circuit implementing binary multiplication. A combinational logic implementation forms shifted partial products with AND gates and combines them with adders. A sequential circuit can instead reuse one adder, storing a partial sum, a shifted multiplicand, and the remaining multiplier in digital registers. If those quantities are $P,M,Q$, the update $P\leftarrow P+(Q_0?M:0)$, $M\leftarrow 2M$, $Q\leftarrow \lfloor Q/2\rfloor$ preserves $P+MQ$. Starting with $(0,X,Y)$ and stopping when $Q=0$ therefore produces $P=XY$, provided widths prevent overflow.

For a block of $2^k$ bits, encode its count leading zeros result as a zero flag $z$ followed by $k$ low count bits $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{mux}(z_H,h_i,{\ell }_i)$ for $i<k-1$. A one-bit leaf has $z=\neg x$ and no low count bits. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.

All count bits are selected in parallel, so $D(n)=D(n/2)+O(1)$ for circuit depth. The circuit size satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial adder along the critical path.

Split the four-bit unsigned inputs into two-bit halves: $X=4X_H+X_L$ and $Y=4Y_H+Y_L$. Use four copies of the two-bit binary multiplier to compute $P_{LL}=X_L{Y}_L$, $P_{HL}=X_H{Y}_L$, $P_{LH}=X_L{Y}_H$, and $P_{HH}=X_H{Y}_H$. ThenThe extreme terms occupy disjoint output positions: $P_{LL}$ uses positions zero to three and $16P_{HH}$ uses positions four to seven. Form $W$ by concatenating their four-bit outputs, with $P_{HH}$ in the upper half and $P_{LL}$ in the lower half. This needs wiring alone, so $W=16P_{HH}+P_{LL}$ without an adder.

Use the first eight-bit adder to form $R=P_{HL}+P_{LH}$ after zero-extension, and the second to form $Z=W+(R\ll 2)$. Thus four two-bit binary multipliers and two eight-bit adders suffice. The fixed left bit shift is also wiring alone.

The middle sum can reach $9+9=18$, so preserve all five of its potentially nonzero bits; retaining only four would be wrong. Its shifted value is at most 72. The final result is at most $15\times 15=225$, so both additions fit in eight bits. Concatenating the disjoint extreme terms is what saves an addition.

Use unsigned inputs as in the preceding parts. Store a 16-bit accumulator $P$, a 16-bit shifted multiplicand $M$, an eight-bit multiplier $Q$, and a three-bit iteration binary counter $k$. The sequential circuit has one 16-bit adder, a 16-bit multiplexer selecting $M$ or zero from $Q_0$, fixed one-place bit shifts, and load/hold selection for the digital registers. The input values are captured when start is accepted, so later input changes cannot alter the operation.

Use three control states with the following synchronous transition table. All assignments in a row use the old digital register values and occur together at the active clock edge.

Reset selects IDLE and clears the digital registers. Set $Z=P$ and done = 1 exactly in DONE. A start pulse in IDLE launches one multiplication; further pulses during RUN are ignored. Holding start high cannot repeatedly launch operations: DONE waits for it to go low before rearming. The product remains stored while waiting and through the following IDLE state. There are eight RUN clock edges after the loading edge; the last addition is captured before done becomes high.

For correctness, let $X_0,Y_0$ denote the captured values. After $i$ iterations, for $0\le i\le 8$, the loop invariant isso $P_i+M_i{Q}_i=X_0{Y}_0$. Writing $Q_i=2q+b$, the next accumulation adds $b{M}_i$, the left bit shift doubles $M_i$, and the logical right shift changes $Q_i$ to $q$. Hence the invariant is preserved. At $i=8$, $Q_i=0$, giving $Z=P_8=X_0{Y}_0$. The largest product is $255^2=65025<2^{16}$, so the accumulator fits. Even the final shifted multiplicand is $256X_0\le 65280$, so it also fits.

A subtract with carry instruction consumes the no-borrow carry flag. Its arithmetic is $Z=X-Y-(1-C_{\mathrm{in}})(\mathrm{mod}{2}^{32})$. Hence a low-limb subs followed immediately by a high-limb sbcs propagates exactly the low subtraction's borrow.

For example, with the same limb assignment as in (c):

subs r0, r0, r2
sbcs r1, r1, r3

It uses an ordinary 32-bit adder by complementing every bit of the subtrahend and adding the incoming arithmetic carry. For $M=2^{32}$, the unreduced adder sum isIf this is $Z+M{C}_{\mathrm{out}}$, rearrangement gives $X-Y-(1-C_{\mathrm{in}})=Z-M(1-C_{\mathrm{out}})$. Thus both the result and outgoing no-borrow flag have the required meanings. With incoming arithmetic carry one this becomes ordinary subtraction.^[ref]

Use a hierarchical leading-zero counter. A block of $2^j$ bits returns a zero flag $z$ and $j$ low count bits $r$: its count leading zeros result is the concatenation $(z,r)$. Thus $z=1$ means that the block is entirely zero and $r=0$; otherwise $z=0$ and $r$ is its leading-zero count. A one-bit block needs just $z=\neg x$ and no low count bits.

For a block of $n=2^k$ bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as $z_H,z_L$ and their $k-1$ low count bits as $h_i,{\ell }_i$. SetThe last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and $r_{k-1}=0$. When only the upper half is zero, $r_{k-1}=1$ supplies the contribution $n/2$ while the multiplexers supply the lower half's count. When both halves are zero, the answer is $(1,0,\dots ,0)$, representing $n$. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses $O(k)$ logic gates for its parallel multiplexers. HenceIndeed the internal-node work is bounded by a constant times ${\sum }_{j=1}^k(n/2^j)j<2n$, and the $n$ leaves add $O(n)$. Delay is $O(\log n)$ and size is $O(n)$, counting fixed-fan-in logic gates and the usual wire fan-out model.

With the ARM architecture family's no-borrow convention, subtract with carry forms $X-Y-(1-C_{\mathrm{in}})$. The same adder used for addition can form $X+(2^n-1-Y)+C_{\mathrm{in}}$. If its output is $Z+2^n{C}_{\mathrm{out}}$, rearranging proves $X-Y-(1-C_{\mathrm{in}})=Z-2^n(1-C_{\mathrm{out}})$. Thus complementing the second operand implements both the result and the correctly chained borrow information.^[ref]