Puzzle of the Week: select count(*) on bit vectors
Recently I mentioned
that counting the number of set (a.k.a on, 1) bits in a bit vector is fast. Well, that's definitely not true. This puzzle is about that problem. A naive approach is this C function:
count_bits_naive (unsigned char *buf, int len)
int n = 0;
for (; len > 0; len--, buf++)
for (; *buf; *buf >>= 1)
n += *buf & 1;
I want to see how much one can speed up this code. Valueable responses would include code, statistics, and theoretical analysis. Assume a 32 or 64-bit machine.
I've got a quite interesting idea about that myself, not sure how it does in reality. BTW, like the sample code above, assume for simplicity that you can trash the array in place.
Submit your solutions through comment system or via email (preferrably) before Sunday April 17, 2005.