Array of 10000 having 16bit elements, find bits set (unlimited RAM) - Google interview

Question

This was asked in my Google interview recently and I offered an answer which involved bit shift and was O(n) but she said this is not the fastest way to go about doing it. I don't understand, is there a way to count the bits set without having to iterate over the entire bits provided?

Answer 1

Brute force: 10000 * 16 * 4 = 640,000 ops. (shift, compare, increment and iteration for each 16 bits word)

Faster way:

We can build table 00-FF -> number of bits set. 256 * 8 * 4 = 8096 ops

I.e. we build a table where for each byte we calculate a number of bits set.

Then for each 16-bit int we split it to upper and lower

for (n in array)    byte lo = n & 0xFF; // lower 8-bits    byte hi = n >> 8;   // higher 8-bits    // simply add number of bits in the upper and lower parts     // of each 16-bits number    // using the pre-calculated table    k += table[lo] + table[hi]; } 

60000 ops in total in the iteration. I.e. 68096 ops in total. It's O(n) though, but with less constant (~9 times less).

In other words, we calculate number of bits for every 8-bits number, and then split each 16-bits number into two 8-bits in order to count bits set using the pre-built table.

Answer 2

There's (almost) always a faster way. Read up about lookup tables.