вычисление количества бит с использованием метода K & R с бесконечной памятью

Question

Я получил ответ на вопрос, отсчитывая отсюда количество битов набора.

Как посчитать количество битов набора в 32-разрядном целом числе?

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; 
} 

Это также легко понять.И нашел лучший ответ как метод Брайана Керниганса, опубликованный hoyhoy ... и он добавляет следующее в конце.

Обратите внимание, что этот вопрос используется во время интервью.Интервьюер добавит предостережение о том, что у вас «бесконечная память».В этом случае вы в основном создаете массив размером 232 и заполняете счетчики битов для чисел в каждом месте.Затем эта функция становится O (1).

Может кто-нибудь объяснить, как это сделать?Если у меня бесконечная память ...

Answer 1

Самый быстрый способ, которым я когда-либо видел заполнение такого массива, это ...

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

Затем подсчитать количество установленных бит в данном числе (при условии, что данное число меньше, чем NELEMENTS)...

numSetBits = array[givenNumber];

Если ваша память не ограничена, я часто вижу NELEMENTS, установленный на 256 (для одного байта), и добавляю количество битов в каждом байте в ваше целое число.

Answer 2

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];
}

Вероятно, вы можете предварительно заполнить массив более разумно, то есть заполнить нулями, затем каждый второй индекс добавить один, затем каждый четвертый индекс добавить 1, затем каждый восьмой индекс добавить 1 и т. Д., Что может быть немного быстрее, хотя я сомневаюсь в этом ...

Кроме того, вы могли бы учитывать значения без знака.