calculer le nombre de bits en utilisant la méthode K & R avec la mémoire infinie

Question

J'ai eu la réponse à la question, en comptant le nombre de bits de sets à partir d'ici.

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

Il est simple à comprendre aussi. Et trouvé la meilleure réponse que la méthode Brian Kernighans, posté par hoyhoy ... et il ajoute ce qui suit à la fin.

Notez qu'il s'agit d'une question utilisée lors des entrevues. L'interviewer ajoutera la mise en garde que vous avez "mémoire infinie". Dans ce cas, vous créez essentiellement un tableau de taille 232 et remplissez le nombre de bits pour les nombres à chaque emplacement. Ensuite, cette fonction devient O (1).

Quelqu'un peut-il expliquer comment faire cela? Si j'ai la mémoire infinie ...

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

Vous pouvez probablement pré-remplir le tableau plus Wiseley, soit remplacés par des zéros, puis chaque seconde index ajouter un, puis chaque quatrième indice ajouter 1, alors chaque huitième indice ajouter 1 etc, pourrait être un peu plus rapide, bien que j'en doute ...

En outre, vous pouvez tenir compte des valeurs non signées.

Answer 2

La façon la plus rapide que j'ai jamais vu pour remplir un tel tableau est ...

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

ensuite pour compter le nombre de bits fixés dans un nombre donné (à condition que le nombre donné est inférieur à Nelements). ..

numSetBits = array[givenNumber]; 

Si votre mémoire n'est pas finie, je vois souvent Nelements fixés à 256 (pour la valeur d'un octet) et ajouter le nombre de bits fixés dans chaque octet dans votre entier.