Building an ALU: 1-bit slice, n-bit ALU, subtraction, flags Z N C V

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• CALL at address 2000 (4 bytes): what is pushed? from Lesson 1.3.2
• What do the flags Z, N, C, V mean? from Lesson 1.1.3
• How do you negate a two's-complement number? from Lesson 0.2.2

1 · The Hook

🎣

The ALU is the part of the CPU that actually computes. It looks like a mystery box, but it is only full adders, a few gates and a multiplexer, copied once per bit. Build one bit, copy it n times, add one trick for subtraction, and you have the ALU every instruction in Phase 1 relied on.

2 · Predict First

🤔

You have an adder that computes a + b + carry-in. Without building a separate subtractor, how can it compute a − b?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Feed it NOT b and set carry-in = 1: a + (NOT b) + 1 = a + (−b) = a − b, because NOT b + 1 is the two's-complement negation of b.

One bit of the ALU

A 1-bit ALU slice takes bits aᵢ, bᵢ and a carry-in cᵢ and computes several results in parallel:

• aᵢ AND bᵢ,
• aᵢ OR bᵢ,
• the full-adder sum aᵢ ⊕ bᵢ ⊕ cᵢ (and carry-out cᵢ₊₁, Lesson 0.2.3).

A multiplexer picks one of them using the operation select lines. With 4 results (say AND, OR, ADD, XOR), the MUX needs 2 select lines.

n-bit ALU

Place n slices side by side. All slices share the same select lines; the carry-out of slice i feeds the carry-in of slice i + 1 (a ripple-carry adder inside the ALU).

Subtraction

Add a B-invert control: each bᵢ passes through an XOR gate with B-invert, so B-invert = 1 sends NOT bᵢ. Set the carry-in of slice 0 to 1 at the same time. Then the adder computes a + NOT b + 1 = a − b. In practice B-invert and the first carry-in are the same control line.

Control lines and operation count

An ALU that supports k operations needs ⌈log₂ k⌉ control bits to select one (if the operation is encoded). Example: 12 operations → 4 control bits.

Flag hardware

• Z = NOR of all n result bits (1 only if every bit is 0).
• N = the result's MSB.
• C = carry out of the MSB slice, cₙ.
• V = cₙ₋₁ ⊕ cₙ: overflow happens exactly when the carry into the MSB differs from the carry out of it. This is the same rule as Lesson 0.2.2 (same-sign operands, other-sign result), written in carries.

Worked subtraction, 4 bits

a = 0101 (5), b = 0011 (3). Add 0101 + 1100 + 1:

• bit 0: 1 + 0 + 1 = 10 → s₀ = 0, c₁ = 1
• bit 1: 0 + 0 + 1 = 1 → s₁ = 1, c₂ = 0
• bit 2: 1 + 1 + 0 = 10 → s₂ = 0, c₃ = 1
• bit 3: 0 + 1 + 1 = 10 → s₃ = 0, c₄ = 1

Result 0010 = 2. C = c₄ = 1; V = c₃ ⊕ c₄ = 1 ⊕ 1 = 0; Z = 0; N = 0.

4 · Visual

One ALU slice: three results computed in parallel, the MUX (operation select) picks one.

5 · Worked Examples

Example 1 Easy

An ALU supports 20 operations, selected by an encoded control field. How many control bits?

Solution

⌈log₂ 20⌉ = 5.

Example 2 Medium

4-bit ALU: compute 0110 + 0101. Give the result, C and V (use c₃ and c₄).

Solution

6 + 5 = 11 = 1011. Carries: bit 0: 0+1 = 1 (c₁ = 0); bit 1: 1+0 = 1 (c₂ = 0); bit 2: 1+1 = 10 (c₃ = 1); bit 3: 0+0+1 = 1 (c₄ = 0). Result 1011, C = 0, V = c₃ ⊕ c₄ = 1 (two positives gave a negative).

Example 3 GATE

How many 2-input XOR gates does an n-bit ALU need for the B-invert function, and what must happen to the carry-in of bit 0 during subtraction?

Solution

n XOR gates (one per bit of b), and carry-in₀ must be 1 (the "+1" of two's-complement negation).

6 · GATE Traps

⚠️

• Subtraction needs both B-invert and carry-in = 1; inverting alone gives a − b − 1.
• V = cₙ₋₁ ⊕ cₙ, not cₙ alone (that is C).
• The MUX chooses among results that are all computed at once; the ALU does not compute only the selected one.
• Control bits = ⌈log₂(number of operations)⌉ for an encoded select.

7 · Memory Hook

🧠

"Invert and carry one." That turns an adder into a subtractor. "Overflow = carry in ≠ carry out at the top."

8 · Connect the Dots

Phase 1 used the ALU as a black box; this lesson opened it: slices, a MUX, B-invert and flag gates. Next: the weak spot of this design, the ripple carry, and the carry-lookahead adder that removes it.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markControl bits

An ALU implements 9 operations with an encoded operation field. Minimum number of control bits?

Numerical answer: ________

Q2MCQ1 markOverflow hardware

With carries cₙ₋₁ (into the MSB) and cₙ (out of the MSB), signed overflow is:

• (A) cₙ₋₁ ⊕ cₙ
• (B) NOT cₙ
• (C) cₙ
• (D) cₙ₋₁ AND cₙ

Q3NAT2 marksSubtraction result

A 4-bit ALU computes 0011 − 0101 (3 − 5) as 0011 + 1010 + 1. What is the 4-bit result as a signed decimal?

Numerical answer: ________

Q4MSQ2 marksFlags after subtraction

For the 4-bit computation 0011 − 0101 above (0011 + 1010 + 1), which flags are 1?

• (A) C
• (B) N
• (C) Z
• (D) V

Q5NAT1 markZ-flag gate

The Z flag of a 32-bit ALU is one NOR gate over the result bits. How many inputs does that gate have?

Numerical answer: ________

10 · Rule Card

• ALU slice: AND, OR, sum computed together; MUX (operation select) picks one; slices chained by carries.
• a − b = a + NOT b + 1 (B-invert XORs + carry-in₀ = 1).
• Control bits = ⌈log₂ #operations⌉.
• Z = NOR(result); N = MSB; C = cₙ; V = cₙ₋₁ ⊕ cₙ.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

1-bit ALU sliceoperation select linesn-bit ALUB-invertsubtraction as a + NOT b + 1ALU control bitsZ flag as NORV = cₙ₋₁ ⊕ cₙ

12 · Answer Vault