To truly understand this stuff... you have to study SIMD. But wait, what SIMD instructions? No no no. The 64-bit register here is being used as a 64-way 1-bit

To truly understand this stuff... you have to study SIMD. But wait, what SIMD instructions? No no no. The 64-bit register here is being used as a 64-way 1-bit SIMD. You can see that addition and the "&" instructions are just simple SIMD. The multiplication instruction can be broken up into complex 64x bitshifts + 64x add instructions all into a single statement. In general, this is called SWAR (SIMD within a register). --------- The "popcount" trick is also SIMD/SWAR (bitshift and add the & 0xcccccccc / 0x33333333 / etc. etc.), and is in fact a "reduction" / "prefix sum" applied over 1-bit values in a 32-bit or 64-bit register applied in a 1-bit SIMD as well. ------------ This achieves very fast results because its innately parallel. A 64-bit processor after all, can be seen as a 64-way parallel 1-bit processor. Learning the parallelization techniques, and applying them in this fashion leads to this kind of super-fast code. Furthermore: PEXT / PDEP from Intel can be seen as "bitwise 64x way gather" and "bitwise 64x way scatter" bit-instructions. The 64-bit register as a 64-way parallel computer is truly a marvelous abstraction.