calculating the number of bits using K&R method with infinite memory

Question

I got answer for the question, counting number of sets bits from here.

http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

long count_bits(long n) {      
  unsigned int c; // c accumulates the total bits set in v 
  for (c = 0; n; c++)  
    n &= n - 1; // clear the least significant bit set 
  return c; 
} 

It is simple to understand also. And found the best answer as Brian Kernighans method, posted by hoyhoy... and he adds the following at the end.

Note that this is an question used during interviews. The interviewer will add the caveat that you have "infinite memory". In that case, you basically create an array of size 232 and fill in the bit counts for the numbers at each location. Then, this function becomes O(1).

Can somebody explain how to do this ? If i have infinite memory ...

Answer 1

int counts[MAX_LONG];

void init() {
   for (int i= 0; i < MAX_LONG; i++)
   {
       counts[i] = count_bits[i]; // as given
   }
}


int count_bits_o1(long number)
{
   return counts[number];
}

You can probably pre-populate the array more wiseley, i.e. fill with zeros, then every second index add one, then every fourth index add 1, then every eighth index add 1 etc, which might be a bit faster, although I doubt it...

Also, you might account for unsigned values.

Answer 2

The fastest way I have ever seen to populate such an array is ...

array[0] = 0;
for (i = 1; i < NELEMENTS; i++) {
    array[i] = array[i >> 1] + (i & 1);
}

Then to count the number of set bits in a given number (provided the given number is less than NELEMENTS) ...

numSetBits = array[givenNumber];

If your memory is not finite, I often see NELEMENTS set to 256 (for one byte's worth) and add the number of set bits in each byte in your integer.