Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/digital-systems-linear-algebra-introduction-to-formal-proof-resit/1/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2019 Digital systems, linear algebra, introduction to formal proof resit 1 a Solution by
Codex 0 2026-10-25
Use a logical right shift to discard one inspected bit at a time. The following Thumb instruction set subroutine accepts the word in
r0, returns its population count in r0, preserves r4, and otherwise uses caller-saved processor registers.popcount_loop:
push {r4}
movs r1, #0
movs r2, #1
movs r3, #32
pop_loop:
movs r4, r0
ands r4, r4, r2
adds r1, r1, r4
lsrs r0, r0, #1
subs r3, r3, #1
bne pop_loop
movs r0, r1
pop {r4}
bx lrands extracts the current least significant bit; adds includes it in the count. lsrs fills the newly vacant high position with zero. subs immediately precedes bne, so the branch tests the zero flag from decrementing the loop counter, not a flag left by the shift.After iterations, the accumulator contains the number of one bits in the original word's lowest positions, and the remaining word is the original unsigned interpretation shifted right by . This loop invariant holds initially and is preserved by each iteration. At every position has been inspected, proving the result. The given example therefore returns 10, and the all-zero and all-one words return 0 and 32. The accumulator cannot overflow: it never exceeds 32.
New to topics? Read the docs here!