Module 1 Exercises — Bits, Logic, and Arithmetic Circuits
Back to the Course 3 syllabus. Read first: H&H 1–3, 5.1–5.5.
Work in course3/m1/ of the labs repo. Paper exercises go in the module’s notes.md (or stay on paper, per the usual workflow); machine exercises are .s files verified at the machine.
Paper exercises
Exercise 1.1 — H&H problem sets. Work select exercises by hand from H&H Ch 1 (number systems and two’s complement), Ch 2 (Boolean algebra and K-maps), Ch 3 (FSMs and timing), and Ch 5.1–5.5 (adders and ALUs). Favor the exercises that force a design (build an adder, design an FSM) over pure drill.
Machine exercises — the theory, checked against a real ALU
Exercise 1.2 — Two’s complement predict-verify. For each case below, predict on paper (H&H 1.4) the result and the NZCV flags, then verify in lldb by stepping tiny .s snippets and reading cpsr/flags. Use w registers for 32-bit cases and x for 64-bit to see width effects.
| Operation (32-bit) | Predicted result | Predicted N Z C V | Observed |
|---|---|---|---|
0x7FFFFFFF + 1 |
… | … | … |
0 - 1 |
… | … | … |
0x80000000 - 1 |
… | … | … |
-1 + 1 |
… | … | … |
| same four, 64-bit | … | … | … |
Exercise 1.3 — Gates from gates. H&H Ch 2 builds everything from NAND. Do the software analogue: implement XOR three different ways using only AND/ORR/BIC/ORN/MVN (no EOR), as three small assembly routines. Verify each exhaustively over all four 1-bit input pairs with a loop, and spot-check with random 64-bit values against the real EOR.
Exercise 1.4 — Ripple-carry adder in software. Implement 8-bit addition without ADD: a loop over bit positions computing sum and carry bits with shifts and logical ops only — H&H 5.2’s ripple-carry adder, transcribed into software. Verify against the hardware ADD for all 65,536 input pairs. In notes.md, note the irony worth internalizing: your loop takes hundreds of instructions; the hardware does the same dataflow in a fraction of a cycle — that is what Ch 5 is about.
Exercise 1.5 — Saturating arithmetic. Implement sat_add32(a, b): signed 32-bit addition that clamps to INT32_MAX/INT32_MIN on overflow, using the V flag and CSEL/CSINV — no branches. Verify with the Exercise 1.2 corner cases. In notes.md, connect it forward: saturation is exactly what Course 2’s fixed-point DSP labs (and the Cortex-M4’s QADD) need when a filter accumulator overflows.
Exercise 1.6 — An FSM in assembly. Pick the H&H Ch 3 FSM you designed in Exercise 1.1 (or the classic rising-edge detector). Encode its next-state/output logic as a table in memory, then write a routine that walks an input string of 0/1 characters and emits the output sequence. Verify against your hand-drawn state-transition table. Deliverable: the state table in notes.md next to the observed output for two input strings.