Bits algorithme de comptage (Brian Kernighan) en un entier complexité temporelle

Quelqu'un peut-il explique pourquoi Brian Kernighan de l'algorithme prend O(log N) pour compter les bits (1s) en un entier. Une simple mise en œuvre de cet algorithme est ci-dessous (en JAVA)

int count_set_bits(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
    return count;
}

Je comprends comment ça fonctionne en désactivant la plus à droite de bit, un par un, jusqu'à ce qu'il arrive à 0, mais je ne sais pas comment nous obtenons O(log N).

  • n est représenté par log(n) bits. (En revanche, les k bits peut représenter les nombres aussi élevé que 2^k.) La vérification de chaque bit prend la constante de temps, de sorte que nous nous retrouvons avec log(n) fois.
  • En Java, il devrait probablement être while( n!=0 ). Sinon, les nombres négatifs ne seront pas comptabilisés correctement.
  • Je vois..juste corrigé
  • softwareengineering.stackexchange.com/questions/304876/...
  • donc, si N est le nombre de bits, alors il est O(N), mais si N est n, alors il est O(log N)
InformationsquelleAutor peter | 2012-09-12