I looked into it a little more, and coded up some benchmarks, and it turns out I was wrong. His solution is like this: int bits(unsigned long n, char* b) {

I looked into it a little more, and coded up some benchmarks, and it turns out I was wrong. His solution is like this: int bits(unsigned long n, char* b) { int retval = __builtin_popcountll(n); while(n) { *b[0] = __builtin_ctzll(n); n &= n-1; *b[1] = __builtin_ctzll(n); n &= n-1; *b[2] = __builtin_ctzll(n); n &= n-1; *b[3] = __builtin_ctzll(n); n &= n-1; b += 4; } return retval; } Unrolled four times, this is faster than the naive code unrolled by the compiler, but slower than the jump table. Unrolled eight times, that is ~10% faster than the jump table, which really surprised me. How can a loop be faster than non-branching code? The crucial difference is that his version begins filling the pipeline immediately. The compiler unrolled version needs to wait on the popcnt before it can begin working, and the jump table needs to wait on both the popcnt and the subsequent jump. Despite the fact that the jump table is 100% branchless after the initial jump, its speed advantage down the stretch can't make up for the author's early start, nor can it make up for the author's eventual branch misprediction and subsequent pipeline stall. Very strange. Cool, but strange. I think the lesson here is to not jump to conclusions and post your faulty misconceptions about performance on the internet before you benchmark it.