←back to thread

Google's “Director of Engineering” Hiring Test

(www.gwan.com)
1764 points fatihky | 1 comments | 13 Oct 16 15:15 UTC | HN request time: 0.231s | source
Show context
Merovius ◴[13 Oct 16 22:00 UTC] No.12704419[source]▶
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.

replies(1): >>12717342 #
1. tjalfi ◴[16 Oct 16 06:45 UTC] No.12717342[source]▶
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.