Nvidia Interview Question

"Popcount"

This is a popoular question, and hopefully you know that the MIT HAKMEM is a solution to this. But assuming you don't really know how to think on your own, the solution posed here is good enough for you to grasp.

The "POPCOUNT" question is to count how many bits are set in an unsigned 32-bit number. So basically, the brute force solution is this:

     for (int i = 0; i < 32; ++i)
         if (bits & (1<< i))
             ++count;
// count now holds how many bits are set

This is actually not so bad, right? Well, if you are actually trying to figure out how many bits are set, you need a solution that is near constant time. Because you are dealing with OS-specific code now. So it better be faster than just looping through the number of bits and counting them. (Especially, if written in a high level language)

Therefore, they'll give you a hint (assuming you can understand the interviewer). They will propose, say you can use anything, how would you make this run faster? The hint is so vague and if you haven't dealt much with this type of stuff, you are virtually screwed :)

But here's something they should tell you, assuming you have a look-up table to count up how many bits are in a byte, how would you calculate how many bits are set within a 32-bit unsigned integer? Well, that makes it so much easier to answer :) All that's needed is to manipulate the bytes when passing into the lookup table.

Therefore, say you are looking at a lookup table with 256 entries, indexed by 0 - 255. The index is the actualy byte that you are trying to calculate. The result gives you the actual count.

For example,

      bitCount[x] gives you the number of bits that are set within this 8-bit byte, namely x.

Therefore, you have to split the 32-bit unsigned integer into 8-bit bytes when passing them into this lookup table, and you just sum up the result. Easy right? Indeed.
Here's the code:

// assume y holds the 32-bit unsigned integer value
for (int i = 0; i < 4; ++i)
     sum += bitCount[ (y>>(8*i)) & 0xff ];
The "& 0xff" part tells the compiler to just get the low-end order 8-bit byte.

This was straight forward after figuring out that you could have a lookup table that yields all the results.