使用带有无限内存的K＆R方法计算比特数

Question

我得到了问题的答案，从这里计数组数位数。

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

它是简单也理解。并找到最好的答案作为布赖恩Kernighans方法，张贴hoyhoy ......并在最后添加以下内容。

请注意，这是访谈中使用的一个问题。面试官会补充说明你有“无限记忆”。在这种情况下，您基本上会创建一个大小为232的数组，并在每个位置填写数字的位数。然后，这个函数变成O（1）。

有人可以解释如何做到这一点？如果我有无限的记忆...

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

你或许可以预填充阵列更wiseley，即补零，然后每第二个索引添加一个，然后每第四个指标加1，然后每第八指标添加1等，其中可能会快一点，但我怀疑它...

此外，你可能会考虑无符号值。

Answer 2

我见过来填充这样的阵列是最快的方法...

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

然后计数在给定数量的组的位的数目（设置给定数量大于NELEMENTS以下）。 ..

numSetBits = array[givenNumber]; 

如果你的内存是不是有限的，我经常看到设置为256 NELEMENTS（一个字节的值），并添加在您的整数时，每个字节组的位数。