Arithmetic Logic Units

Every instruction a processor executes eventually funnels through one circuit: the Arithmetic Logic Unit, or ALU. When a CPU adds two numbers, compares them, masks a bit field, or checks whether a loop counter has hit zero, the same block of combinational logic does the work. It is reconfigured on the fly by a few control bits. The ALU is where the Ripple-Carry Adder you built for addition stops being a single-purpose circuit. It becomes one operating mode among many. It is selected the same way a multiplexer picks a data path. The motivating engineering problem is economy of hardware and uniformity of interface. A processor's datapath must support add, subtract, AND, OR, XOR, comparisons, and shifts. Yet the instruction decoder and register file only want to talk to one functional unit. That unit needs just one set of input and output wires. Building six separate circuits and wiring six sets of buses would waste die area. It would also complicate control logic. Instead, engineers unify all these operations behind a single two-input, one-output block. Its behavior is chosen by a small operation-select code. This is exactly the same abstraction a 4-to-1 multiplexer uses to choose among data sources. The ALU also introduces a second, equally important output: status flags. Beyond the numeric result, real programs need to know several things. They must know whether an addition overflowed. They must know whether a subtraction produced zero (a loop-termination test). They must also know whether the result was negative. These one-bit signals — Zero, Negative, Carry, Overflow — are computed as byproducts of the same adder hardware. They are fed to the control unit, where they drive conditional branches. This is the last piece of "pure combinational logic" tier before you meet Registers and Register Files. There, the ALU's output gets latched into storage. It becomes part of a real, clocked datapath. This article builds a complete multi-bit ALU from primitives you already have: adders, gates, and multiplexers. You will see how a single adder is reused for both addition and subtraction via two's-complement tricks. You will see how bitwise logic operations are computed in parallel with arithmetic. You will see how a select signal chooses the final output. You will also see how status flags fall out almost for free. We verify correctness bit by bit and reason about gate delay. This ensures the design is not just plausible but provably right. It is also predictably fast.

Key takeaways

An ALU is a combinational circuit that computes one of several functions (add, subtract, AND, OR, XOR, etc.) of two n-bit inputs, chosen by an operation-select code.
A single ripple-carry (or faster) adder handles both addition and subtraction: subtraction is addition of the two's-complement negation, enabled by XOR-ing the second operand with a control bit and feeding that bit in as carry-in.
Bitwise logic units (AND, OR, XOR, NOT) run in parallel with the adder on every cycle; a final multiplexer, driven by the same operation code, selects which result becomes the output.
Status flags — Zero, Negative, Carry-out, Overflow — are cheap extra outputs derived from the adder's result and carry chain, and they drive conditional branches later in the pipeline.
Critical path length equals the adder's carry-propagation delay plus one multiplexer stage, so ALU speed is essentially adder speed; this is why fast-adder designs matter.
The ALU is the direct ancestor of the arithmetic core in every modern CPU, GPU integer pipeline, and microcontroller, and it feeds directly into Registers and Register Files and instruction datapaths.

The core insight

An ALU computes many functions of two operands in parallel using shared adder and logic hardware, then a multiplexer — steered by a few control bits — selects the one result the instruction actually needs.

The idea

An Arithmetic Logic Unit is a combinational circuit with two n-bit data inputs (call them A and B), a small operation-select input (often called `ALUOp` or `Sel`), an n-bit Result output, and a handful of single-bit status flags. It is purely combinational: no clock, no memory, just wires and gates whose output is a function of the current inputs. This matters because it means the ALU's behavior can be fully specified with a truth table (in principle) or, more practically, with the structural composition of smaller verified blocks: adders, gates, and multiplexers, each of which you can reason about independently and then compose. The central design trick that makes an ALU efficient rather than a pile of disjoint circuits is hardware sharing under two's-complement arithmetic. Recall that in Two's Complement Representation, negation is "invert all bits and add one." This means subtraction, `A − B`, can be computed as `A + (¬B) + 1`, which is exactly an addition — the same ripple-carry adder used for `A + B`, just with `B` bitwise-inverted and a carry-in of 1 instead of 0. A single XOR gate per bit, controlled by one signal (`Binvert` or `Sub`), toggles between "pass B through" and "invert B," and that same signal is wired to the adder's carry-in. One adder, one control bit, two arithmetic operations. The second idea is parallel computation, deferred selection. Rather than decide up front which operation to perform and then route the operands to a specialized circuit, an efficient ALU computes all candidate results simultaneously — the adder computes A+B or A−B, the AND gates compute A∧B, the OR gates compute A∨B, the XOR gates compute A⊕B — and only at the very last stage does a multiplexer, driven by the operation-select bits, choose which of these already-computed values becomes the output. This costs extra gates (all the unused results are silently discarded every cycle) but it costs no extra time beyond the multiplexer's delay, because everything happens in parallel. This is a classic space-for-time tradeoff, and it is the same philosophy you saw when a decoder pre-computes all $2^n$ minterms before a single one is selected.

How it works

Consider building a 1-bit ALU slice first, then composing $n$ of them (with carry chaining) into an $n$ -bit ALU — the same "bit-slice" strategy used for ripple-carry adders.

Per-bit slice inputs: `a`, `b` (1-bit operands), `CarryIn`, `Binvert` (1 = subtract), `Op` (2-bit function select: 00=AND, 01=OR, 10=ADD/SUB, 11=SLT-support). Per-bit slice outputs: `Result`, `CarryOut`, plus a `Set` output (used only by the least-significant bit's neighbor to build "set-less-than"). ``` FUNCTION ALU_BIT(a, b, CarryIn, Binvert, Op): // Step 1: optionally invert b for subtraction b_eff = Binvert XOR b // if Binvert=1, this bit is flipped // Step 2: compute all candidate results in parallel and_result = a AND b_eff or_result = a OR b_eff sum, CarryOut = FULL_ADDER(a, b_eff, CarryIn) // FULL_ADDER is the verified 1-bit adder // Step 3: choose the result via a small mux keyed on Op IF Op == 00: Result = and_result ELSE IF Op == 01: Result = or_result ELSE IF Op == 10: Result = sum ELSE IF Op == 11: Result = Set // wired in from the MSB slice, see below RETURN Result, CarryOut ``` ``` FUNCTION FULL_ADDER(a, b, CarryIn): sum = a XOR b XOR CarryIn CarryOut = (a AND b) OR (CarryIn AND (a XOR b)) RETURN sum, CarryOut ``` Chaining $n$ of these slices with `CarryOut[i]` feeding `CarryIn[i+1]` (bit 0 gets `CarryIn = Binvert`, which supplies the "+1" for two's-complement negation) gives a full $n$ -bit ALU core. The complete $n$ -bit ALU wraps this with global control and flag logic: ``` FUNCTION ALU_N(A[0..n-1], B[0..n-1], Op, Binvert): CarryIn0 = Binvert // "+1" trick for subtraction carry = CarryIn0 FOR i = 0 TO n-1: Result[i], carry = ALU_BIT(A[i], B[i], carry, Binvert, Op) CarryOutFinal = carry // ---- status flags, computed from the same wires, no extra adder needed ---- Zero = (Result == all-zero-bits) // n-input NOR of Result bits Negative = Result[n-1] // sign bit, arithmetic ops only Overflow = (A[n-1] == B_eff[n-1]) AND (Result[n-1] != A[n-1]) // only meaningful when Op = ADD/SUB Carry = CarryOutFinal // only meaningful for ADD/SUB RETURN Result, Zero, Negative, Overflow, Carry ``` Two subtleties deserve spelling out because they are the classic sources of bugs.

Overflow is not the same as carry-out. Signed overflow occurs when two operands of the same sign produce a result of the opposite sign — e.g., adding two large positives yields a negative-looking result because it wrapped past the representable range. The formula `Overflow = (sign(A) == sign(B_eff)) AND (sign(Result) != sign(A))` captures exactly this, and it is computed from bits you already have (the top-bit adder's inputs and output) — no extra adder logic required, just three extra gates.

Zero-detection is a wide NOR, not a comparison. `Zero` is true exactly when every bit of `Result` is 0, computed by ORing all result bits together and inverting (an $n$ -input NOR, or a tree of 2-input NORs/ORs for speed). It is used directly by branch instructions: `beq` (branch if equal) is implemented as "subtract, then check Zero."

Figure

A 4-bit ALU built from bit-slices, a shared adder chain, and a result-select mux

Complexity & correctness

Time complexity. The dominant cost is the carry chain: bit $i$ 's full adder cannot produce `CarryOut[i]` until `CarryIn[i]` (from bit $i-1$ ) is stable. For an $n$ -bit ripple-carry ALU this gives a worst-case critical path of

T_{\text{ALU}} = n \cdot t_{\text{FA}} + t_{\text{XOR}} + t_{\text{MUX}}

where $t_{\text{FA}}$ is one full adder's carry-propagation delay, and the trailing terms account for the input inverter (Binvert XOR) and the final result-select multiplexer, both of which add a constant number of gate delays independent of $n$ . This is $O(n)$ time — linear in operand width — exactly the same bound as the plain ripple-carry adder, because the adder is the bottleneck; the AND/OR/XOR logic units are $O(1)$ -depth per bit and run in parallel with the adder, contributing nothing extra to the critical path. This is precisely why real processors replace the ripple-carry core with a carry-lookahead or carry-select adder ( $O(\log n)$ delay) once operand widths reach 32 or 64 bits: the ALU's speed is bottlenecked entirely by its adder, so a faster adder gives a faster ALU for free everywhere else.

Space complexity. Each bit slice uses $O(1)$ gates (one XOR for invert, one AND, one OR, one full adder ≈ 5 gates, one 4-to-1 mux ≈ a handful of transmission gates or NAND-based mux logic), so total gate count is $O(n)$ — linear in operand width, with a modest constant factor (roughly 10–15 two-input gate equivalents per bit for a 4-function ALU). This is efficient: a naïve design that built six separate n-bit circuits and then multiplexed their $n$ -bit outputs would cost strictly more gates for the adder logic alone (subtract and add would each need their own adder) without any compensating speed benefit, since the shared design already achieves the same $O(n)$ time.

Correctness argument. We prove the ALU computes the intended function by structural induction, mirroring the ripple-carry adder proof and extending it. Base case (bit 0). With `CarryIn[0] = Binvert`, bit 0 computes `a0 XOR b_eff0 XOR Binvert`. When `Binvert = 0` (addition), this is `a0 XOR b0 XOR 0`, the correct LSB sum with no incoming carry — correct. When `Binvert = 1` (subtraction), `b_eff0 = NOT b0`, and the carry-in of 1 supplies the "+1" of two's-complement negation, so bit 0 computes `a0 + (NOT b0) + 1` mod 2, which is exactly `(a0 − b0) mod 2` — correct by the definition of two's-complement subtraction. Inductive step. Assume bits $0..i-1$ have correctly computed the low-order $i$ bits of $A + B_{\text{eff}}$ (where $B_{\text{eff}} = B$ or $\text{NOT } B$ depending on Binvert) together with the correct carry-out $c_i$ representing the true arithmetic carry out of position $i-1$ . Bit $i$ 's full adder receives this correct $c_i$ as its `CarryIn`, and by the full-adder's own correctness (verified when you built the Ripple-Carry Adder), it produces the correct sum bit and correct carry-out for position $i$ . By induction, all $n$ bits — and hence the full $n$ -bit addition or subtraction — are correct. Logic and select correctness. AND, OR, and XOR outputs are computed bit-independently and are trivially correct by the definition of the gates. The final multiplexer is a standard $k$ -to-1 selector (built from the same multiplexer primitive covered elsewhere); its correctness reduces to the multiplexer's own truth table, which passes through exactly the input line addressed by `Op` and no other. Flag correctness. `Zero` is correct by definition of NOR (output is 1 iff every input is 0). `Overflow`'s formula is the standard signed-overflow detector: overflow can only occur when both operands have the same sign (adding a positive and a negative can never overflow, since the true sum's magnitude is bounded by the larger operand), and if they do, overflow has occurred exactly when the result's sign differs from that shared operand sign — this is a direct case analysis over the four sign combinations of $A$ and $B_{\text{eff}}$ .

Honest tradeoffs. The bit-slice ALU is simple, modular, and easy to verify — but its $O(n)$ carry chain becomes a real bottleneck at 32/64-bit widths, motivating carry-lookahead adders at the cost of more complex (though still $O(n)$ -gate) circuitry. Computing all operations in parallel wastes power (every unused ALU function still switches its transistors every cycle) in exchange for zero extra latency; low-power designs sometimes clock-gate or operand-gate unused paths, trading a little complexity for real energy savings.

Worked example

Trace a 4-bit ALU (bits numbered 3..0, MSB to LSB) computing `A − B` where `A = 0110` (6) and `B = 0011` (3), expecting `Result = 0011` (3), with `Op = 10` (ADD/SUB) and `Binvert = 1`. Step 1 — invert B and set carry-in-0:

bit	a	b	b_eff = b XOR Binvert
3	1	0	1
2	1	0	1
1	0	1	0
0	0	1	0

`CarryIn[0] = Binvert = 1` (this supplies the "+1" of two's-complement negation). Step 2 — ripple the full adders, bit 0 to bit 3:

bit	a	b_eff	CarryIn	sum = a⊕b_eff⊕CarryIn	CarryOut = (a·b_eff)+(CarryIn·(a⊕b_eff))
0	0	0	1	1	0
1	0	0	0	0	0
2	1	1	0	0	1
3	1	1	1	1	1

Reading `sum` bits MSB→LSB: `Result = 0011` = 3. Correct: $6 - 3 = 3$ . ✓ Step 3 — flags:

Carry (final CarryOut, bit 3) = 1. For subtraction using this scheme, `CarryOut = 1` conventionally signals "no borrow occurred," i.e., $A \geq B$ — consistent, since $6 \geq 3$ .
Zero = NOR(0,0,1,1) = 0. Result is nonzero — correct, since $3 \neq 0$ .
Negative = Result[3] = 0. Result's sign bit is 0 (positive) — correct, since $3 > 0$ .
Overflow: sign(a) at bit 3 = 1, sign(b_eff) at bit 3 = 1 — same sign, so overflow is possible; check `Result[3] != a[3]`: `0 != 1` is true, so at first glance this looks like overflow — but wait, we must use the actual overflow formula `(a[3] == b_eff[3]) AND (Result[3] != a[3])`. Here `a[3]=1`, `b_eff[3]=1` (equal, condition met), and `Result[3]=1`, `a[3]=1` (equal, so `Result[3] != a[3]` is false). Overflow = false — correctly, no overflow, since $6-3=3$ is well within the 4-bit signed range $[-8,7]$ .

Now a second trace exposing the overflow flag doing real work: `Op=10, Binvert=0` (addition), `A = 0101` (5), `B = 0100` (4), both positive, sum should be 9 — but 9 overflows the 4-bit signed range $[-8,7]$ .

bit	a	b	CarryIn(0)=0	sum	CarryOut
0	1	0	0	1	0
1	0	0	0	0	0
2	1	1	0	0	1
3	0	0	1	1	0

`Result = 1001` (binary), which as a signed 4-bit number is $-7$ — clearly wrong as unsigned 9, and the flag catches exactly this: `a[3]=0`, `b[3]=0` (same sign, positive), `Result[3]=1 != a[3]=0` → Overflow = true. The hardware correctly flags that a signed interpretation of this addition is invalid, even though the raw bit pattern was computed with total arithmetic correctness by the adder.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Confusing Carry-out with Overflow	Carry-out is an unsigned wraparound signal; Overflow is a signed sign-mismatch signal — they mean different things and can each be set independently	Compute Overflow with the explicit `(sign(A)==sign(B_eff)) AND (sign(Result)!=sign(A))` formula, never assume `Overflow = CarryOut`
Forgetting to feed Binvert into CarryIn[0]	Subtraction needs both "invert B" and "+1"; omitting the +1 computes $A + \bar B$ , off by one from $A - B$	Tie `CarryIn[0] = Binvert` explicitly in the top-level wiring
Treating Zero-detect as a comparator	Students sometimes build an equality comparator for `Zero` instead of a NOR of the result bits, duplicating logic	`Zero` is always "is Result all-0-bits," computed with a NOR/AND-of-inverted-bits tree, independent of the operation
Assuming logic-op flags are meaningful	Overflow/Carry are defined for arithmetic; running AND/OR through the same flag logic gives meaningless bits	Gate the flags so Overflow/Carry are only asserted (or only interpreted) when `Op` selects ADD/SUB
Ripple-carry ALU assumed to scale linearly in speed with word size for free	Delay grows with $n$ , not constant, so doubling word width roughly doubles worst-case latency	For wide ALUs (32/64-bit), replace the ripple carry chain with carry-lookahead or carry-select structure

Pioneers & history

The ALU concept crystallizes ideas from the earliest stored-program computer designs, where a single arithmetic circuit was recognized as the natural hub for all numeric computation rather than a collection of bespoke adders and comparators.

Origins · 1 minJohn von Neumann and how this was discovered

John von Neumann

1903–1957 · Institute for Advanced Study, Princeton, 1945

Von Neumann's 1945 "First Draft of a Report on the EDVAC" formalized the stored-program architecture with a distinct central arithmetical unit, the conceptual ancestor of the modern ALU: a single hardware block responsible for all arithmetic and logical operations, fed operands from memory and returning results to it. This separation of an arithmetic core from memory and control became the template every subsequent processor design, including the ALU described in this article, still follows.

History

1945

— von Neumann's EDVAC report describes a dedicated "central arithmetical unit" separate from memory and control.

1951

— Whirlwind and early stored-program machines implement dedicated adder/subtracter circuits reused across operations.

1967

— Fairchild and Texas Instruments ship early TTL "arithmetic logic unit" MSI chips as standalone components.

1970

— The 74181, a 4-bit ALU integrated circuit with selectable arithmetic and logic functions, becomes a minicomputer-era standard building block.

1971

— Intel's 4004 microprocessor integrates a 4-bit ALU on a single chip, folding decades of discrete-ALU design into silicon.

Where this matters

Every general-purpose CPU core — x86, ARM, RISC-V, MIPS — contains one or more ALUs at the heart of its execute stage; the `74181` TTL chip, an early standalone 4-bit ALU, was so influential that its logic diagram is still used as a teaching artifact decades later. GPUs replicate thousands of simplified integer/float ALU-like units across their cores to achieve massive data parallelism. Microcontrollers embedded in everything from thermostats to automotive systems use small, low-power ALUs whose functional coverage (add/sub/and/or/shift/compare) is tuned to the instruction set they support. Compiler back ends target the specific operation-select encoding an ALU exposes, and instruction-set architectures document exactly which `ALUOp` codes correspond to which opcodes. In every one of these systems, once you understand the bit-slice pattern in this article, the natural next question is: what happens to the ALU's output on the next clock edge — which is precisely where Registers and Register Files and clocked datapaths pick up the story, latching results and routing them back as the next instruction's operands.

Ask the tutor: How would you extend this bit-slice ALU to support a barrel shifter for logical and arithmetic shifts without slowing down the critical path?

Why not just build six separate circuits for add, subtract, AND, OR, etc. and select among their outputs?

You could, and early discrete designs sometimes did something close to this, but it wastes hardware. Addition and subtraction, in particular, need almost identical circuitry — a full ripple-carry (or faster) adder — differing only in whether B is inverted and whether the initial carry-in is 0 or 1. Building two separate adders duplicates the most expensive part of the ALU (the carry chain) for no benefit, since a single adder plus one XOR gate per bit and one control signal already covers both operations. The unified design achieves the same functionality with substantially fewer gates and, because everything still runs in parallel, no loss of speed.

Does adding more operations (like shifts or set-less-than) slow the ALU down?

Not necessarily, and this is the appeal of the parallel-compute-then-select design. Adding a new function typically means adding one more parallel computation path (e.g., a barrel shifter, or a small comparator for set-less-than) and widening the final multiplexer by one more input line. The multiplexer's delay grows only logarithmically with the number of inputs (a $k$ -to-1 mux built from 2-to-1 stages has $O(\log k)$ depth), so adding several more functions barely touches the critical path, which is still dominated by the adder's $O(n)$ carry chain. The real cost of more functions is extra area and power, not extra latency.

How does set-less-than (SLT) fit into this bit-slice design?

Set-less-than needs to output 1 in bit 0 (and 0 elsewhere) exactly when A < B, interpreted as signed numbers. A clean trick: compute `A − B` using the normal subtract path, then take the sign bit of the result adjusted for overflow (XOR the raw sign bit with the Overflow flag, since overflow flips which operand is actually larger) from the MSB slice, and route that single bit down into bit 0's `Op=11` mux input as the `Set` signal. Every other bit's `Op=11` output is forced to 0. This reuses the existing subtract hardware entirely — no new adder, just a few extra gates and one extra wire carried from the top slice to the bottom.

Why do processors eventually replace ripple-carry adders inside the ALU with carry-lookahead adders?

Because the ALU's speed is bottlenecked entirely by the adder's carry chain, which is O(n) in the operand width for ripple-carry designs. At 8 or 16 bits this delay is tolerable, but at 32 or 64 bits (standard word sizes in modern CPUs), a linear carry chain becomes the single slowest path in the entire processor, capping the clock frequency. Carry-lookahead adders precompute carries using extra logic in O(log n) depth, at the cost of more gates, and swapping one for the other inside the ALU's bit-slice structure changes nothing else about the design — the AND/OR/XOR logic and the final mux stay exactly the same.

What exactly are 'status flags' and why do they matter beyond the ALU itself?

Status flags — commonly Zero, Negative, Carry, and Overflow — are single-bit outputs computed as byproducts of the ALU's arithmetic, summarizing properties of the result that the numeric output alone doesn't make convenient to test. A control unit uses these flags, not the full n-bit result, to decide whether a conditional branch (`beq`, `blt`, `bgt`) should be taken, because comparing the flag values is far cheaper than re-examining the entire result word. In many instruction sets these flags are latched into a dedicated status register after each ALU operation, feeding directly into the branch-decision logic of the pipeline's control path.

Is the ALU's design specific to a particular instruction set, or is it a general pattern?

The bit-slice, shared-adder, parallel-compute-then-select pattern is architecture-agnostic; it is the standard blueprint used across essentially every instruction set, from MIPS and RISC-V to x86 and ARM. What differs between architectures is the encoding of the operation-select signals, the exact set of supported functions (some ALUs support shifts and multiplies internally, others delegate those to separate functional units), and the specific flag conventions (some architectures define Carry for subtraction as "borrow occurred" rather than "no borrow occurred"). The underlying combinational-logic strategy — adders plus gates plus a selecting multiplexer — remains essentially universal.

Why is the ALU considered purely combinational, and why does that matter for a CPU's design?

It is combinational because its output depends only on the current values of its inputs (A, B, Op, Binvert) with no internal memory or clock — remove the inputs and the outputs immediately change with no "state" retained. This matters because it lets the ALU be freely inserted into a clocked datapath: registers on either side of it latch its inputs and outputs on clock edges, while the ALU itself just needs to settle (reach a stable output) within one clock period. This clean separation between "combinational computation" (the ALU) and "state storage" (covered next in Registers and Register Files) is exactly what makes synchronous digital design tractable and analyzable stage by stage.