Even or odd, count the set bits, multiply by shifting
The same program in M68K, MIPS, RISC-V, Z80.
Four questions about the number 37, answered without a single mul or div between them: is it even,
how many of its bits are set, what is it times ten, and is bit 5 one.
37 is 100101 in binary, and every answer below is easier to see in that form than in the decimal.
The counting loop is the one worth taking apart, because and rbx, rcx with rcx one less than
rbx does something that is not obvious at all: it clears the lowest set bit of rbx and leaves
every other bit alone.
Watch it on 37. Subtracting one turns the lowest set bit into a zero and every zero below it into a one:
rbx | rbx - 1 | and |
|---|---|---|
100101 | 100100 | 100100 |
100100 | 100011 | 100000 |
100000 | 011111 | 000000 |
Three passes, three set bits, and the loop stops because there is nothing left. The point is that the
loop runs once per set bit rather than once per bit, so a sixty four bit register with two bits set
takes two passes and not sixty four. It is known as Kernighan's algorithm, and a processor with the
right extension does the whole count in one instruction, popcnt.
test rax, 1 and and rax, 1 compute exactly the same bits, and the difference is what happens
afterwards: test throws the answer away and keeps only the flags, so rax still holds 37 for the
three sections below it to use.
r12 comes out at 25, which is 37 again, because masking the low byte of a number that already fits
in a byte changes nothing. That is not a bug, and a mask on a bigger number, and r12, 0xFF applied
to 1000, would leave E8.