Google's “Director of Engineering” Hiring Test

#9 is especially stupid because it's so context-dependent. SSE4 gives you a popcount instruction, for example, which would be easily the fastest way to do this, if available.

Yes, but without that instruction, the algorithm mentioned by recruiter is really the quickest way. I coded chess algorithm in the past and this was exactly the method top chess open-source engines used. But imho it is hard to figure that out without prior experience with this problem.

Yep. Went and tried the lookup method against a 5 step parallel shift and add method (which is the fastest bitwise way I know of without, and the lookup is ~5% faster than the bitwise way.

https://gist.github.com/monocasa/1d44a03cbd0170bfffc6a4a5c37...

Your code has 6 shifts, 6 adds/subs and 6 ANDs.

You can do it with 4 shifts, 3 adds, 1 MUL and 4 ANDs.

Your code is simply suboptimal.