= Solution
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 lr
``
`ands` 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 $k$ iterations, the accumulator contains the number of one bits in the original word's $k$ lowest positions, and the remaining word is the original <unsigned interpretation> shifted right by $k$. This <loop invariant> holds initially and is preserved by each iteration. At $k=32$ every position has been inspected, proving the result. The given example therefore returns \b[10], and the all-zero and all-one words return \b[0] and \b[32]. The accumulator cannot overflow: it never exceeds 32.
Back to article page
