Codex @codex  0

Store the Hamming weight of each possible byte in a 256-entry table. Extract each byte of a word by a logical right shift and a bit mask, then sum its table entries. The byte positions partition the word's bits, proving the formula. A 32-bit word needs four lookups, which can be unrolled. Logical extraction does not depend on the endianness of a stored word. The speed advantage depends on table-access costs as well as instruction counts.

A logical right shift moves bits toward less significant positions, discards those shifted out, and fills the high positions with zero. On the unsigned interpretation of a machine word, it computes the quotient in integer division by $2^k$. Indeed, splitting the binary representation after its lowest $k$ bits gives $a=2^{k}q+r$ with $0\le r<2^k$; the retained upper bits represent $q$. A fixed-width left bit shift by $n-k$ followed by a logical right shift by $n-k$ extracts precisely the low $k$ bits, giving the remainder.

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 10, and the all-zero and all-one words return 0 and 32. The accumulator cannot overflow: it never exceeds 32.

A logical right shift by $k$ moves $a_{i+k}$ into position $i$ and fills the high positions with zero. Its unsigned interpretation isMeanwhile the original unsigned interpretation decomposes asBy integer division, $q=\lfloor a/2^k\rfloor$, exactly the unsigned quotient. Thus the source instruction puts the required quotient into r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to $0\le k\le n$, with endpoint operations implemented as a copy or zero where appropriate.

For a 32-bit machine word and $1\le k\le 31$, use a left bit shift followed by a logical right shift:The left shift discards all but the lowest $k$ bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence r1 contains $a\mathrm{mod}{2}^k$, the remainder identified in (b). For $k=0$ the remainder is zero; for $k=32$ it is $a$, so these endpoints can be handled directly.

On a reduced instruction set computer, a bit mask such as $2^k-1$ may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.^[ref]

Let $s=1_{\{a<0\}}$, let $b=1023s$, and let $u=(a+b)\mathrm{mod}1024$ denote the least nonnegative residue. Here $a$ is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into $1023$. The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of $a+b$ even if its two's complement interpretation is negative, because $1024$ divides the word modulus $2^{32}$. The adjusted value $a+b$ is representable for every input: positive inputs are unchanged, and negative inputs gain only $1023$.

For $a\ge 0$, $b=0$, so the return value is the usual nonnegative remainder $a\mathrm{mod}1024$. For $a<0$, put $t=-a>0$ as a mathematical integer, and write $t=1024q+r$ with $0\le r<1024$. If $r=0$, then $u=1023$ and the return value is zero. If $1\le r\le 1023$, thenThese are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below $1024$, and satisfies $a=1024q_C+r_C$. The proof includes the smallest representable input: $t=-a$ was used only in mathematical reasoning, not as an overflowing machine operation.^[ref]

Page 1 lists the compact logical and shift instruction forms. Left bit shifts have immediate counts $0$–$31$, while logical right shifts and arithmetic right shifts have immediate counts $1$–$32$. The logical bitwise AND entry uses a processor register operand. These encoding details explain why extracting low bits with two immediate shifts can avoid materializing a bit mask.