Google's “Director of Engineering” Hiring Test

So… someone care to explain to me where I'm going egregiously wrong, apparently? Because, at least on my machine with the code I spewed out quickly, the Kerningham way of counting bits is ~6x slower than a lookup table (including generating the table itself).

http://sprunge.us/IIEH

The Kerningham way code seems faster for very sparse arrays (i.e. only one bit set per uint16), but slower otherwise.

You weren't doing anything wrong. He discusses two methods: https://graphics.stanford.edu/~seander/bithacks.html#CountBi... https://graphics.stanford.edu/~seander/bithacks.html#CountBi... The second option will probably beat a byte lookup table. GCC switched from a lookup table to similar code. If this still isn't fast enough, try using SIMD registers and the Harley/Seal method based on carry save adders (http://www.hackersdelight.org/hdcodetxt/popArrayHS.c.txt). If you like this sort of bit twiddling, you probably would enjoy Henry Warren's Hacker's Delight.