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.
Extract successive bytes into indices of the byte-table population count table. The last shift leaves only the original high byte, so that index needs no final mask.
popcount_table:
push {r4}
adr r2, popbyte
movs r3, #255
movs r1, r0
ands r1, r1, r3
ldrb r4, [r2, r1]
lsrs r0, r0, #8
movs r1, r0
ands r1, r1, r3
ldrb r1, [r2, r1]
adds r4, r4, r1
lsrs r0, r0, #8
movs r1, r0
ands r1, r1, r3
ldrb r1, [r2, r1]
adds r4, r4, r1
lsrs r0, r0, #8
ldrb r1, [r2, r0]
adds r0, r4, r1
pop {r4}
bx lrPlace the byte table at an aligned nearby label in the instruction-address range of
adr. That instruction forms the table's address relative to the program counter; it does not load a table entry. Each ldrb uses register-offset addressing: the base is r2, the byte offset is the index register, and the loaded byte is zero-extended. Because entries occupy one byte, the index needs no scaling. ldrb r1, [r2, r1] uses the old r1 to form the address before overwriting it with the result.Every bit belongs to exactly one extracted byte, so adding the four table counts gives the whole word's population count, independently of endianness. The calculation reads four bytes from the table and contains no loop.
Count executed instructions, excluding the caller's branch-with-link and assuming the register-return and stack instructions shown above. The shift loop executes six instructions per iteration, plus four entry instructions and three exit instructions: instructions. The unrolled table subroutine executes 21 instructions, including four byte loads.
If every instruction, including a table load and a branch, costs one time unit, the ratio is in favour of the table version. A more informative simple model assigns cost to each table load and unit cost to the other displayed instructions: its cost is , versus 199 for the loop under the same unit branch assumption. Thus this model favours lookup when .
Real running time depends on the processor and memory system. Taken branches can incur extra instruction-fetch or pipeline costs, favouring the unrolled version; slow flash or cache miss events on the 256-byte table can erode that advantage. Instruction and table placement also matter. These assumptions prevent instruction counts from becoming an unsupported universal cycle claim. For a fixed 32-bit argument both implementations have constant worst-case work; the gain is a constant factor, not a different asymptotic class.
Let the new byte table store and, for , . Thus it stores the number of leading zeros in an eight-bit argument: , , and . All entries fit in one byte.
countlz:
adr r3, lzbyte
movs r1, #0
lsrs r2, r0, #24
bne lz_found
movs r1, #8
lsrs r2, r0, #16
bne lz_found
movs r1, #16
lsrs r2, r0, #8
bne lz_found
movs r1, #24
movs r2, r0
lz_found:
ldrb r2, [r3, r2]
adds r0, r1, r2
bx lrThe high byte is tried first. A failed test proves that byte was zero, so the next right-shifted value is again a byte-sized index without masking: all higher bytes have already been proved zero. The offset in
r1 counts those skipped zero bytes in bits. Adding the table result for the first nonzero byte gives the leading-zero count. If every byte is zero, the last lookup contributes eight to the offset 24, giving 32. The example with high byte one gives 7. At most three conditional branches and one table read are needed; no per-bit loop is used. Articles by others on the same topic
There are currently no matching articles.