Google's “Director of Engineering” Hiring Test

If you have a collection of data, and you want to know the number of 1 bits, and you want to do it with a minimum of resources... what is the process?

For example, standard bit-shifting and masking the lowest bit to set a counter is one way to do this. Possibly there are other, faster ways, such as using a lookup table (a byte or more can be "counted" at a time). Of course, because so many people were doing this, intel added a popcnt instruction which probably is more efficient (faster) than either of the above, at the expense of more CPU real estate, heat, etc.

Turns out counting 1 bits in a dataset is a super-important problem that shows up in a lot of situations.