Compter le nombre de 1 dans la représentation binaire

Question

Une façon efficace de compter le nombre de 1 dans la représentation binaire d'un nombre en O(1) si vous avez assez de mémoire pour jouer avec. Il s'agit d'une question d'entretien que j'ai trouvée sur un forum en ligne, mais qui n'avait pas de réponse. Quelqu'un peut-il suggérer quelque chose, je ne vois pas comment le faire en O(1) temps ?

Answer 1

C'est le poids de Hamming alias le comptage de la population. Le lien mentionne des mises en œuvre efficaces. Citation :

Avec une mémoire illimitée, nous pourrions simplement créer une grande table de consultation du poids de Hamming de chaque entier de 64 bits.

Answer 2

J'ai une solution qui compte les bits dans O(Number of 1's) temps :

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (n-1)
    return count

Dans le pire des cas (lorsque le nombre est 2^n - 1, tous les 1 en binaire), il vérifiera chaque bit.

Edit : Je viens de trouver un très bel algorithme à temps constant et à mémoire constante pour le comptage des bits. Le voici, écrit en C :

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

Vous pouvez trouver la preuve de son exactitude ici .

Answer 3

Veuillez noter que : n&(n-1) élimine toujours le 1 le moins significatif.

Nous pouvons donc écrire le code pour calculer le nombre de 1 de la manière suivante :

count=0;
while(n!=0){
  n = n&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

La complexité du programme serait : nombre de 1 dans n (qui est constamment < 32).

Answer 4

J'ai vu la solution suivante sur un autre site web :

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Answer 5

public static void main(String[] args) {

    int a = 3;
    int orig = a;
    int count = 0;
    while(a>0)
    {
        a = a >> 1 << 1;
        if(orig-a==1)
            count++;
        orig = a >> 1;
        a = orig;
    }

    System.out.println("Number of 1s are: "+count);
}