Digital Circuits Cheatsheet
Adders and the ALU
Use this Digital Circuits reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.
Overview
Adders are the core arithmetic building blocks of digital systems. They are combined into Arithmetic Logic Units (ALUs), which perform the integer operations at the heart of every processor.
Half Adder
Adds two single bits; no carry input.
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Equations: - S = A ⊕ B - C = A · B
Full Adder
Adds two bits plus a carry-in (Cᵢₙ); produces Sum and carry-out (Cₒᵤₜ).
| A | B | Cᵢₙ | Sum | Cₒᵤₜ |
|---|---|---|---|---|
| 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 |
Equations: - S = A ⊕ B ⊕ Cᵢₙ - Cₒᵤₜ = A·B + A·Cᵢₙ + B·Cᵢₙ = A·B + Cᵢₙ·(A ⊕ B)
Implementation: 2 half adders + 1 OR gate.
Ripple-Carry Adder (RCA)
Chain n full adders for n-bit addition. Each stage's Cₒᵤₜ feeds the next stage's Cᵢₙ.
Bit 0: FA → S₀, C₁ Bit 1: FA → S₁, C₂ (Cᵢₙ = C₁) Bit 2: FA → S₂, C₃ (Cᵢₙ = C₂) Bit n-1: FA → Sₙ₋₁, Cₒᵤₜ
| Property | Value |
|---|---|
| Hardware | n full adders |
| Delay | O(n) — carry must ripple through all stages |
| 4-bit delay (typical) | 4 × t_FA |
| Overflow detection | Cₒᵤₜ of MSB ≠ carry into MSB (for signed) |
Carry-Lookahead Adder (CLA)
Eliminates ripple delay by computing all carries in parallel using two signals per bit:
- Generate: Gᵢ = Aᵢ · Bᵢ (this stage always produces a carry)
- Propagate: Pᵢ = Aᵢ ⊕ Bᵢ (this stage passes through a carry)
Carry equations:
C₁ = G₀ + P₀·C₀ C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀ C₃ = G₂ + P₂·G₁ + P₂·P₁·G₀ + P₂·P₁·P₀·C₀ C₄ = G₃ + P₃·G₂ + P₃·P₂·G₁ + P₃·P₂·P₁·G₀ + P₃·P₂·P₁·P₀·C₀
| Property | RCA | CLA |
|---|---|---|
| Delay | O(n) | O(log n) with hierarchy |
| Hardware | Less | More (wider gates) |
| Practical size | Small circuits | 4-bit blocks, then chained |
Modern processors use carry-select and prefix adder variants for even faster addition.
Carry-Select Adder
Computes two n/2-bit sums in parallel (one assuming Cᵢₙ=0, one assuming Cᵢₙ=1), then a MUX selects the correct half once the actual carry is known.
Delay ≈ O(√n) — a practical middle ground between RCA and full CLA.
Subtraction
Use two's complement: A − B = A + B̄ + 1
Adder/Subtractor circuit: - When Sub=0 (add): B passes unchanged, Cᵢₙ=0 → A + B - When Sub=1 (subtract): B is XORed with 1 (inverted), Cᵢₙ=1 → A + B̄ + 1 = A − B
Each bit: Bᵢ_effective = Bᵢ ⊕ Sub; Cᵢₙ of bit 0 = Sub.
Overflow Detection (Two's Complement)
| Condition | Overflow |
|---|---|
| Positive + Positive = Negative | Yes |
| Negative + Negative = Positive | Yes |
| Positive + Negative | Never |
Hardware: Overflow = Cₙ₋₁ ⊕ Cₙ (XOR of carry into MSB and carry out of MSB)
BCD Adder
Add two BCD digits (0–9). After binary addition, if result > 9 or carry out, add 6 (0110) to correct it.
Step 1: Binary add the two BCD digits + Cin Step 2: If (result > 9) OR (carry = 1): add 0110 to result, set carry_out = 1 Step 3: Output is valid BCD
Arithmetic Logic Unit (ALU)
An ALU performs arithmetic and logical operations on two n-bit operands (A and B) selected by an operation code (opcode / function select).
Typical 1-bit ALU operations
| Select (F₁F₀) | Operation | Output |
|---|---|---|
| 00 | AND | A · B |
| 01 | OR | A + B |
| 10 | ADD | A + B (full adder) |
| 11 | SUBTRACT | A − B |
74181 — 4-bit ALU (classic reference)
- 4-bit operands A, B
- 4 function-select inputs (S₀–S₃) + Mode input M
- M=1: logical operations (16 functions)
- M=0: arithmetic operations (16 functions, with carry)
- Outputs: F₀–F₃, carry-out, P̄ (propagate), Ḡ (generate), A=B (comparator)
ALU in a Modern Processor
Instruction ──► Control Unit ──► ALU function select Register A ──► Register B ──► ALU ──► Result ──► destination register └──► Status flags (N, Z, C, V)
Status Flags:
| Flag | Meaning | Set when |
|---|---|---|
| N (Negative) | Result is negative | MSB of result = 1 |
| Z (Zero) | Result is zero | All result bits = 0 |
| C (Carry) | Unsigned overflow | Carry out of MSB |
| V (oVerflow) | Signed overflow | Cₙ₋₁ ⊕ Cₙ = 1 |
Multiplier (Array Multiplier)
Multiply two n-bit numbers using n partial products, each a shifted AND:
1011 (A = 11) × 0110 (B = 6) ------ 0000 (A × b₀ = 0, shift 0) 1011 (A × b₁ = A, shift 1) 1011 (A × b₂ = A, shift 2) 0000 (A × b₃ = 0, shift 3) ------ 1000010 = 66 ✓
An n×n array multiplier needs n² AND gates and n(n−2) full adders. Delay is O(n).
Booth's algorithm reduces the number of partial products for signed multiplication.
Comparator from Subtractor
A − B: if result = 0 → A = B; if carry-out logic indicates → A < B or A > B. For unsigned: borrow (inverted carry) indicates A < B.