Comment compter le nombre de bits d'un entier de 32 bits?

considèrent également les fonctions intégrées de vos compilateurs.

sur le compilateur GNU par exemple, vous pouvez simplement utiliser:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

dans le pire des cas, le compilateur générera un appel à une fonction. Dans le meilleur des cas, le compilateur émet un processeur instructions pour faire le même travail plus rapide.

le GCC intrinsèques même travailler sur plusieurs plates-formes. Popcount deviendra mainstream dans l'architecture x86, donc il c'est logique de commencer à utiliser l'intrinsèque maintenant. D'autres architectures ont le popcount depuis des années.

sur x86, Vous pouvez dire au compilateur qu'il peut prendre en charge l'instruction popcnt avec -mpopcnt ou -msse4.2 pour activer également les instructions vectorielles qui ont été ajoutées dans la même génération. Voir GCC x86 options . -march=nehalem (ou -march= quel que soit le CPU que vous voulez que votre code assume et accorde pour) pourrait être un bon choix. Exécuter le binaire résultant sur un CPU plus ancien résultera en une erreur d'instruction illégale.

pour faire des binaires optimisés pour la machine sur laquelle vous les construisez, utilisez -march=native (avec gcc, clang ou ICC).

MSVC fournit un intrinsèque pour le x86 popcnt " instruction , mais à la différence de gcc, il est vraiment un intrinsèque pour l'instruction matérielle et nécessite un soutien matériel.

en utilisant std::bitset<>::count() au lieu d'un

en théorie, tout compilateur qui sait comment popcount efficacement pour le CPU cible devrait exposer cette fonctionnalité par ISO C++ std::bitset<> . En pratique, vous pourriez être mieux avec le bit-hack et/shift/ADD dans certains cas pour certaines CPU cibles.

pour les architectures cibles où le matériel popcount est une extension optionnelle (comme x86), tous les compilateurs n'ont pas un std::bitset qui en profite lorsqu'il est disponible. Par exemple, MSVC n'a aucun moyen d'activer le support popcnt au moment de la compilation , et utilise toujours une recherche de table , même avec /Ox /arch:AVX (ce qui implique SSE4.2, bien que techniquement il y ait un bit de caractéristique séparé pour popcnt .)

mais au moins vous obtenez quelque chose de portable qui fonctionne partout, et avec gcc / clang avec les bonnes options de cible, vous obtenez le popcount matériel pour les architectures qui le supportent.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Voir asm de gcc, clang, cpi, et MSVC sur le Godbolt compilateur explorer.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt émet ceci:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11 émet (pour le int arg version):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

cette source n'est pas spécifique à x86 ou spécifique à GNU, mais ne compile correctement que pour x86 avec gcc/clang / icc.

notez également que la solution de repli de gcc pour les architectures sans popcount d'instruction simple est une recherche de table byte-at-a-time. Ce n'est pas merveilleux pour bras, par exemple .

à mon avis, la" meilleure " solution est celle qui peut être lue par un autre programmeur (ou le programmeur original deux ans plus tard) Sans commentaires abondants. Vous pouvez bien vouloir la solution la plus rapide ou la plus intelligente que certains ont déjà fourni, mais je préfère la lisibilité plutôt que l'intelligence à tout moment.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

si vous voulez plus de vitesse (et en supposant que vous le documentez bien pour aider vos successeurs), vous pouvez utiliser une recherche de table:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

bien que ceux-ci dépendent de tailles de type de données spécifiques de sorte qu'ils ne sont pas que portable. Mais, puisque de nombreuses optimisations de performance ne sont pas portables de toute façon, ce n'est peut-être pas un problème. Si vous voulez la portabilité, Je m'en tiens à la solution lisible.

De Hacker Délice, p. 66, Figure 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

exécute en ~ 20-ish instructions (dépendant de l'arche), pas de branchement.



Hacker's Delight is delightful! Fortement recommandé.

je pense que le chemin le plus rapide-sans utiliser les tables de recherche et popcount - est le suivant. Il compte les bits avec seulement 12 opérations.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Cela fonctionne parce que vous pouvez compter le nombre total de bits en divisant en deux moitiés, en comptant le nombre de bits dans les deux moitiés, puis de les ajouter. Aussi connu sous le nom de Divide and Conquer paradigme. Nous allons rentrer dans le détail..

v = v - ((v >> 1) & 0x55555555); 

le nombre de les bits en deux bits peuvent être 0b00 , 0b01 ou 0b10 . Essayons de régler ça sur 2 bits..

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

c'est ce qui était requis: la dernière colonne montre le nombre de bits mis dans chaque paire de deux bits. Si le numéro à deux bits est >= 2 (0b10) , alors and produit 0b01 , sinon il produit 0b00 .

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

cette déclaration devrait être facile à comprendre. Après la première opération, nous avons le le nombre de bits définis dans tous les deux bits, maintenant nous résumons ce nombre dans tous les 4 bits.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Nous avons alors résumer le résultat ci-dessus, nous donnant le nombre total de bits 4 bits. La dernière déclaration est la plus délicate.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

continuons...

v + (v >> 4)

c'est similaire à la deuxième instruction; nous comptons les bits définis en groupes de 4 à la place. Nous savons-en raison de notre précédent les opérations que chaque grignoter est le nombre de bits. Voyons un exemple. Supposons que nous ayons le byte 0b01000010 . Cela signifie que le premier nibble a son jeu de 4bits et le second a son jeu de 2bits. Maintenant, nous ajoutons ces grignotines ensemble.

0b01000010 + 0b01000000

Il nous donne le nombre de bits dans un octet, dans la première grignoter 0b01100010 et, par conséquent, nous masque les quatre derniers octets de tous les octets du nombre (jeter).

0b01100010 & 0xF0 = 0b01100000

Maintenant, chaque octet est le nombre de bits. Nous devons les additionner tous ensemble. L'astuce consiste à multiplier le résultat par 0b10101010 qui a une propriété intéressante. Si notre nombre a quatre octets, A B C D , il en résultera un nouveau nombre avec ces octets A+B+C+D B+C+D C+D D . Un nombre de 4 octets peut avoir un maximum de 32 bits, qui peut être représenté par 0b00100000 .

Tout ce dont nous avons besoin maintenant est le premier octet qui a la somme de tous les bits octets, et nous nous entendons par >> 24 . Cet algorithme a été conçu pour les mots 32 bit mais peut être facilement modifié pour les mots 64 bit .

je me suis ennuyé, et chronométré un milliard d'itérations de trois approches. Le compilateur est gcc-O3. La CPU est ce qu'ils ont mis dans le Macbook Pro.

le plus rapide est le suivant, à 3,7 secondes:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

deuxième place va au même code mais Recherche 4 octets au lieu de 2 demi-mots. Qui a pris environ 5,5 secondes.

la troisième place va à l'approche "d'addition latérale", qui a pris 8,6 secondes.

la quatrième place va à __builtin_popcount () de GCC, à une honteuse 11 secondes.

l'approche un-bit-at-a-time était beaucoup plus lente, et j'en ai eu marre d'attendre qu'elle soit terminée.

donc si vous vous souciez avant tout de la performance, utilisez la première approche. Si vous vous souciez, mais pas assez pour dépenser 64Kb de RAM dessus, utilisez la deuxième approche. Sinon l'utilisation de la lisible (mais lent) un-peu-à-un-temps approche.

Il est difficile de penser à une situation où vous souhaiteriez utiliser le bit-tourner approche.

Edit: résultats similaires here .

si vous utilisez Java, la méthode intégrée Integer.bitCount le fera.

unsigned int count_bit(unsigned 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;
}

Laissez-moi vous expliquer cet algorithme.

cet algorithme est basé sur L'algorithme diviser pour mieux régner. Supposons qu'il y ait un entier 8bit 213(11010101 en binaire), l'algorithme fonctionne comme ceci(chaque fois fusionner deux blocs voisins):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

c'est une de ces questions où il est utile de connaître votre micro-architecture. Je viens de chronométrer deux variantes sous gcc 4.3.3 compilé avec -O3 en utilisant C++ inlines pour éliminer la fonction Appel overhead, un milliard d'itérations, en gardant la somme en cours d'exécution de tous les comptes pour s'assurer que le compilateur ne supprime rien d'important, en utilisant rdtsc pour le chronométrage (précision du cycle d'horloge).

inline int pop2(unsigned x, unsigned y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x+y) & 0x000000FF;
}

Le non modifiée Hacker Plaisir pris 12.2 gigacycles. Ma version parallèle (en comptant deux fois plus de bits) fonctionne en 13,0 gigacycles. 10,5 s total écoulé pour les deux ensembles sur un Duo de base de 2,4 GHz. 25 gigacycles = un peu plus de 10 secondes à cette fréquence d'horloge, donc je suis sûr que mes timings sont corrects.

cela a à voir avec les chaînes de dépendances d'instruction, qui sont très mauvaises pour cet algorithme. Je pouvais presque doubler la vitesse de nouveau en utilisant une paire de registres 64 bits. En fait, si j'étais intelligent et ajouté x+y un peu plus tôt je pourrais raser certains changement. La version 64 bits avec quelques petites modifications sortirait à peu près égal, mais compter deux fois plus de bits à nouveau.

avec des registres SIMD 128 bits, encore un autre facteur de deux, et les ensembles D'instruction SSE ont souvent astucieux raccourcis, aussi.

il n'y a aucune raison pour que le code soit particulièrement transparent. L'interface est simple, l'algorithme peut être référencé en ligne à de nombreux endroits, et il se prête à un test unitaire complet. Programmeur qui tombe dessus pourrait même apprendre quelque chose. Ces opérations de bits sont extrêmement naturelles au niveau de la machine.

OK, j'ai décidé de mettre au banc la version 64 bits modifiée. Pour cette taille(non signée long) = = 8

inline int pop2(unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return x & 0xFF;
}

Qui semble correcte (je ne suis pas d'essais avec soin, tout de même). Maintenant, le timing est de 10.70 gigacycles / 14.1 gigacycles. Ce dernier chiffre a totalisé 128 milliards de bits et correspond à 5,9 s écoulés sur ce machine. La version non-parallèle accélère un tout petit peu car je tourne en mode 64 bits et il aime les registres 64 bits un peu mieux que les registres 32 bits.

voyons s'il y a un peu plus de OOo pipelining à avoir ici. Ce fut un peu plus compliqué, alors j'ai testé un peu. Chaque terme s'élève à 64, la somme totale étant de 256.

inline int pop4(unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  enum { m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF };

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    return x & 0x000001FF;
}

j'étais excité pendant un moment, mais il s'avère que gcc joue des trucs en ligne avec-O3 même bien que je n'utilise pas le mot clé inline dans certains tests. Quand j'ai laissé gcc jouer des trucs, un milliard d'appels à pop4 () prend 12,56 gigacycles, mais j'ai déterminé que c'était des arguments pliants comme des expressions constantes. Un nombre plus réaliste semble être 19,6 gc pour une autre accélération de 30%. Ma boucle de test ressemble maintenant à ceci, en s'assurant que chaque argument est assez différent pour empêcher gcc de jouer des trucs.

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

256 milliards de bits en 8.17 s écoulés. Fonctionne à 1,02 s pour 32 millions de bits comme référencé dans le 16-bit table lookup. Je ne peux pas comparer directement, parce que l'autre banc ne donne pas une vitesse d'horloge, mais il semble que j'ai giflé la morve de L'édition de table de 64KB, qui est une utilisation tragique de cache L1 en premier lieu.

mise à Jour: a décidé de faire de l'évidence et de créer pop6() par l'ajout de plus de quatre lignes dupliquées. On en est arrivé à 22,8 gc, 384 milliards de bits en 9,5 s écoulés. Donc il y a encore 20% à 800m pour 32 milliards. bit.

pourquoi ne pas diviser itérativement par 2?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

je suis d'accord que ce n'est pas le plus rapide, mais" meilleur " est quelque peu ambigu. Je dirais cependant que "best" devrait avoir un élément de clarté

pour un milieu agréable entre un 2 ³² table de recherche et itérant à travers chaque bit individuellement:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

de http://ctips.pbwiki.com/CountBits

Le Hacker Plaisir de la bit-tourner devient beaucoup plus clair quand vous écrivez les modèles de bits.

unsigned int bitCount(unsigned int x)
{
  x = (((x >> 1) & 0b01010101010101010101010101010101)
       + x       & 0b01010101010101010101010101010101);
  x = (((x >> 2) & 0b00110011001100110011001100110011)
       + x       & 0b00110011001100110011001100110011); 
  x = (((x >> 4) & 0b00001111000011110000111100001111)
       + x       & 0b00001111000011110000111100001111); 
  x = (((x >> 8) & 0b00000000111111110000000011111111)
       + x       & 0b00000000111111110000000011111111); 
  x = (((x >> 16)& 0b00000000000000001111111111111111)
       + x       & 0b00000000000000001111111111111111); 
  return x;
}

la première étape ajoute les bits pairs aux bits impairs, produisant une somme de bits dans chaque deux. Les autres étapes ajoutent des morceaux d'ordre élevé à des morceaux d'ordre faible, doublant la taille des morceaux tout le long, jusqu'à ce que nous avons le compte final de prendre la totalité de l'int.

ce n'est pas la solution la plus rapide ou la meilleure, mais j'ai trouvé la même question à ma façon, et j'ai commencé à penser et à penser. enfin j'ai réalisé que cela peut être fait comme ceci si vous obtenez le problème du côté mathématique, et dessinez un graphique, alors vous trouvez que c'est une fonction qui a une certaine partie périodique, et alors vous réalisez la différence entre les périodes... alors voilà:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}

cela peut être fait dans O(k) , où k est le nombre de bits mis.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

la fonction que vous recherchez est souvent appelée la" somme latérale "ou" population count " d'un nombre binaire. Knuth en parle dans Pre-Fascicle 1A, pp11-12 (bien qu'il y ait une brève référence dans le Volume 2, 4.6.3-(7).)

Le locus classicus est Peter Wegner l'article "Une Technique de Comptage dans un Ordinateur Binaire", de la les Communications de l'ACM , Volume 3 (1960) Numéro 5, page 322 . Il y donne deux algorithmes différents, un optimisé pour les nombres prévus pour être "clairsemé" (i.e., avoir un petit nombre de uns) et un pour le cas opposé.

quelques questions en suspens: -

1. Si le nombre est négatif, alors?
2. si le nombre est 1024 , alors la méthode" itérativement diviser par 2 " itérera 10 fois.

nous pouvons modifier l'algo pour supporter le nombre négatif comme suit: -

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

maintenant pour surmonter le deuxième problème, nous pouvons écrire l'algo comme:-

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

pour référence complète voir:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

  private int get_bits_set(int v)
    {
      int c; // c accumulates the total bits set in v
        for (c = 0; v>0; c++)
        {
            v &= v - 1; // clear the least significant bit set
        }
        return c;
    }

je pense que la méthode de Brian Kernighan sera également utile... Il passe par autant d'itérations qu'il y a de bits prédéfinis. Donc si nous avons un mot de 32 bits avec seulement le haut bit réglé, alors il ne passera qu'une fois dans la boucle.

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

, Publié en 1988, le Langage de Programmation C 2e Ed. (par Brian W. Kernighan et Dennis M. Ritchie) le mentionne dans l'exercice 2-9. Le 19 avril 2006, Don Knuth m'a fait remarquer que cette méthode "a été publiée pour la première fois par Peter Wegner dans CACM 3 (1960), 322. (Également découvert indépendamment par Derrick Lehmer et publié en 1964 dans un livre édité par Beckenbach.) "

j'utilise le code ci-dessous qui est plus intuitive.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Logique : n et (n-1) permet de réinitialiser le dernier bit de n.

P. S: je sais que ce n'est pas une solution O(1), mais une solution intéressante.

Que voulez-vous dire par"meilleur algorithme"? Le code court - circuité ou le code à jeun? Votre code a l'air très élégant et il a un temps d'exécution constant. Le code est également très court.

mais si la vitesse est le facteur principal et non la taille du code, alors je pense que le suivant peut être plus rapide:

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

je pense que ce ne sera pas plus rapide pour une valeur 64 bits mais une valeur 32 bits peut être plus rapide.

j'ai écrit une macro bitcount rapide pour les machines RISC vers 1990. Il n'utilise pas l'arithmétique avancée (multiplication, division, %), les récupérations de mémoire (beaucoup trop lentes), les branches (beaucoup trop lentes), mais il suppose que le CPU a un changeur de baril de 32 bits (en d'autres termes, >> 1 et >> 32 prennent la même quantité de cycles.) Il suppose que les petites constantes (telles que 6, 12, 24) ne coûtent rien à charger dans les registres, ou sont stockées dans des temporaireset réutilisées encore et encore.

avec ces hypothèses, il compte 32 bits en environ 16 cycles / instructions sur la plupart des machines RISC. Notez que 15 instructions / cycles est proche d'une limite inférieure sur le nombre de cycles ou d'instructions, parce qu'il semble prendre au moins 3 instructions (masque, shift, operator) pour couper le nombre d'addends en deux, donc log_2(32) = 5, 5 x 3 = 15 instructions est un quasi-lowerbound.

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

voici un secret pour la première étape et la plus complexe:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

donc si je prends la première colonne (A) ci-dessus, décalez-la à droite de 1 bit, et soustrayez-la de AB, j'obtiens la sortie (CD). L'extension à 3 bits est similaire; vous pouvez le vérifier avec une table booléenne à 8 lignes comme la mienne ci-dessus si vous le souhaitez.

• Ne Gillies

si vous utilisez C++ une autre option est d'utiliser le template metaprogramming:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

utilisation serait:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

vous pouvez bien sûr étendre ce modèle à l'utilisation de différents types (même la taille de bit auto-détectable), mais je l'ai gardé simple pour la clarté.

edit: j'ai oublié de mentionner c'est bien parce que c' devrait travailler dans n'importe quel compilateur C++ et qu'il est fondamentalement juste déroulez votre boucle pour vous si une valeur constante est utilisée pour le nombre de bits (en d'autres termes, je suis assez sûr que c'est la méthode générale la plus rapide que vous trouverez)

j'aime particulièrement cet exemple du dossier fortune:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

Je l'aime mieux parce qu'il est si joli!

Java JDK1.5

entier.bitCount (n);

où n est le nombre dont les 1 doivent être comptés.

vérifier aussi

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }

j'ai trouvé une implémentation du comptage de bits dans un tableau avec l'utilisation de L'instruction SIMD (SSSE3 et AVX2). Il a en 2-2.5 fois Meilleure performance que si elle utilise la fonction intrinsèque __popcnt64.

version SSSE3:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

AVX2 version:

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}

Je L'utilise toujours dans la programmation compétitive et c'est facile à écrire et efficace:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Il y a beaucoup algorithme de compter les bits; mais je pense que le meilleur est le plus rapide! Vous pouvez voir les détails sur cette page:

Peu Tourner Les Hacks

je suggère celui-ci:

Comptage de bits définis dans 14, 24 ou 32 bits à l'aide de mots de 64 bits instructions

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

cette méthode nécessite un CPU 64 bits avec une division de module rapide pour être efficace. La première option ne prend que 3 Opérations, la deuxième 10 et la troisième 15.

voici un module portable ( ANSI-C ) qui peut référencer chacun de vos algorithmes sur n'importe quelle architecture.

votre CPU a 9 octets? Aucun problème: -) pour le moment il implémente 2 algorithmes, l'algorithme K&R et une table de recherche byte wise. La table de recherche est en moyenne 3 fois plus rapide que L'algorithme K&R. Si quelqu'un peut trouver un moyen de rendre l'algorithme "Hacker's Delight" portable n'hésitez pas à l'ajouter.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

.

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif

32 bits ou pas ? Je suis venu avec cette méthode en Java après avoir lu " cracking the coding interview " 4th edition exercice 5.5 ( chap 5: Bit Manipulation). Si le bit le moins significatif est 1 incrément count , alors déplacez à droite l'entier.

public static int bitCount( int n){
    int count = 0;
    for (int i=n; i!=0; i = i >> 1){
        count += i & 1;
    }
    return count;
}

je pense que celui-ci est plus intuitif que les solutions avec constante 0x333333, peu importe leur vitesse. Cela dépend de votre définition de "meilleur algorithme" .

Fast solution C# à l'aide de pré-calculée tableau de Byte bit compte avec branchement sur la taille de l'image.

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}