Comment compter le nombre de bits définis dans un entier 32 bits?

868

8 bits représentant le nombre 7 ressemblent à ceci:

00000111

Trois bits sont définis.

Quels sont les algorithmes pour déterminer le nombre de bits définis dans un entier 32 bits?

Matt Howells
la source
101
C'est le poids de Hamming BTW.
Purfideas
11
Qu'est-ce qu'une application réelle pour cela? (Cela ne doit pas être pris comme une critique - je suis juste curieux.)
jonmorgan
8
Calcul du bit de parité (recherchez-le), utilisé comme simple détection d'erreur dans la communication.
Dialecticus
8
@Dialecticus, calculer un bit de parité est moins cher que calculer le poids de Hamming
finnw
15
@spookyjon Disons que vous avez un graphe représenté comme une matrice d'adjacence, qui est essentiellement un ensemble de bits. Si vous souhaitez calculer le nombre d'arêtes d'un sommet, cela revient à calculer le poids de Hamming d'une ligne dans le jeu de bits.
fuz

Réponses:

850

Ceci est connu sous le nom de « poids Hamming », «popcount» ou «addition latérale».

Le «meilleur» algorithme dépend vraiment du processeur sur lequel vous vous trouvez et de votre modèle d'utilisation.

Certains processeurs ont une seule instruction intégrée pour le faire et d'autres ont des instructions parallèles qui agissent sur les vecteurs de bits. Les instructions parallèles (comme les x86 popcnt, sur les processeurs où il est pris en charge) seront presque certainement les plus rapides. Certaines autres architectures peuvent avoir une instruction lente implémentée avec une boucle microcodée qui teste un bit par cycle ( citation nécessaire ).

Une méthode de recherche de table pré-remplie peut être très rapide si votre CPU dispose d'un grand cache et / ou si vous exécutez beaucoup de ces instructions dans une boucle serrée. Cependant, il peut souffrir à cause du coût d'un «échec de cache», où le CPU doit récupérer une partie de la table de la mémoire principale. (Recherchez chaque octet séparément pour garder la table petite.)

Si vous savez que vos octets seront principalement des 0 ou des 1, il existe des algorithmes très efficaces pour ces scénarios.

Je crois qu'un très bon algorithme à usage général est le suivant, connu sous le nom d'algorithme SWAR «parallèle» ou «à précision variable». Je l'ai exprimé dans un pseudo-langage de type C, vous devrez peut-être l'ajuster pour qu'il fonctionne pour un langage particulier (par exemple en utilisant uint32_t pour C ++ et >>> en Java):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Pour JavaScript: contraindre à un entier avec |0pour des performances: changez la première ligne eni = (i|0) - ((i >> 1) & 0x55555555);

Cela a le meilleur comportement dans le pire des cas de tous les algorithmes discutés, donc traitera efficacement tout modèle d'utilisation ou les valeurs que vous lui lancerez.


Comment fonctionne ce bithack SWAR:

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

La première étape est une version optimisée du masquage pour isoler les bits pairs / impairs, les décaler pour les aligner et les ajouter. Cela fait effectivement 16 ajouts distincts dans des accumulateurs 2 bits ( SWAR = SIMD dans un registre ). Comme (i & 0x55555555) + ((i>>1) & 0x55555555).

L'étape suivante prend les huit paires paires / impaires de ces 16x accumulateurs 2 bits et les ajoute à nouveau, produisant des sommes 8x 4 bits. L' i - ...optimisation n'est pas possible cette fois-ci, elle masque donc juste avant / après le décalage. L'utilisation de la même 0x33...constante les deux fois plutôt 0xccc...qu'avant le décalage est une bonne chose lors de la compilation pour les ISA qui doivent construire des constantes 32 bits dans des registres séparément.

La dernière étape de changement et d'ajout de (i + (i >> 4)) & 0x0F0F0F0Fs'élargit à 4 accumulateurs 8 bits. Il masque après l' ajout au lieu d'avant, car la valeur maximale dans tout accumulateur à 4 bits est 4, si les 4 bits des bits d'entrée correspondants ont été définis. 4 + 4 = 8 qui tient toujours sur 4 bits, donc le transfert entre les éléments de quartet est impossible dans i + (i >> 4).

Jusqu'à présent, il s'agit simplement d'une carte SIMD assez normale utilisant des techniques SWAR avec quelques optimisations intelligentes. Continuer avec le même modèle pour 2 étapes supplémentaires peut s'étendre à 2 x 16 bits puis 1 x 32 bits. Mais il existe un moyen plus efficace sur les machines à multiplication matérielle rapide:

Une fois que nous avons assez "d'éléments", une multiplication avec une constante magique peut additionner tous les éléments dans l'élément supérieur . Dans ce cas, les éléments d'octet. La multiplication se fait par décalage vers la gauche et addition, donc une multiplication des x * 0x01010101résultats x + (x<<8) + (x<<16) + (x<<24). Nos éléments 8 bits sont suffisamment larges (et contiennent des nombres suffisamment petits) pour que cela ne produise pas de report dans les 8 bits supérieurs.

Une version 64 bits de ceci peut faire 8x éléments 8 bits dans un entier 64 bits avec un multiplicateur 0x010101010101010101 et extraire l'octet haut avec >>56. Il ne prend donc pas d'étapes supplémentaires, juste des constantes plus larges. C'est ce que GCC utilise __builtin_popcountllsur les systèmes x86 lorsque l' popcntinstruction matérielle n'est pas activée. Si vous pouvez utiliser des fonctions intégrées ou intrinsèques à cette fin, faites-le pour donner au compilateur la possibilité d'effectuer des optimisations spécifiques à la cible.


Avec SIMD complet pour des vecteurs plus larges (par exemple, compter un tableau entier)

Cet algorithme bit à bit-SWAR pourrait se paralléliser pour être fait dans plusieurs éléments vectoriels à la fois, plutôt que dans un seul registre entier, pour une accélération sur les CPU avec SIMD mais sans instruction de popcount utilisable. (par exemple, le code x86-64 qui doit s'exécuter sur n'importe quel processeur, pas seulement Nehalem ou version ultérieure.)

Cependant, la meilleure façon d'utiliser les instructions vectorielles pour popcount est généralement d'utiliser un shuffle variable pour effectuer une recherche de table sur 4 bits à la fois de chaque octet en parallèle. (Les 4 bits indexent une table à 16 entrées contenue dans un registre vectoriel).

Sur les processeurs Intel, l'instruction popcnt matérielle 64 bits peut surpasser une implémentation parallèle-bit SSSE3PSHUFB d'environ un facteur 2, mais uniquement si votre compilateur l'obtient parfaitement . Sinon, l'ESS peut sortir nettement en tête. Les versions de compilateur plus récentes sont conscientes du problème de fausse dépendance popcnt sur Intel .

Références:

Matt Howells
la source
87
Ha! J'adore la fonction NumberOfSetBits (), mais bonne chance pour obtenir cela grâce à une révision du code. :-)
Jason S
37
Peut-être que cela devrait être utilisé unsigned intpour montrer facilement qu'il est exempt de toute complication de bit de signe. Serait uint32_tégalement plus sûr, comme dans, vous obtenez ce que vous attendez sur toutes les plateformes?
Craig McQueen
35
@nonnb: En fait, tel qu'écrit, le code est bogué et a besoin de maintenance. >>est défini par l'implémentation pour les valeurs négatives. L'argument doit être modifié (ou converti) en unsigned, et puisque le code est spécifique à 32 bits, il devrait probablement être utilisé uint32_t.
R .. GitHub STOP HELPING ICE
6
Ce n'est pas vraiment magique. Il ajoute des ensembles de bits mais le fait avec quelques optimisations intelligentes. Le lien wikipedia donné dans la réponse explique bien ce qui se passe mais je vais aller ligne par ligne. 1) Comptez le nombre de bits dans chaque paire de bits, en mettant ce nombre dans cette paire de bits (vous aurez 00, 01 ou 10); le bit "intelligent" ici est la soustraction qui évite un masque. 2) Ajoutez des paires de ces sommes de paires de bits dans leurs quartets correspondants; rien d'intelligent ici mais chaque quartet aura désormais une valeur 0-4. (suite)
dash-tom-bang
8
Une autre note, cela s'étend aux registres 64 et 128 bits en étendant simplement les constantes de manière appropriée. Fait intéressant (pour moi), ces constantes sont également ~ 0/3, 5, 17 et 255; les trois premiers étant 2 ^ n + 1. Tout cela a plus de sens plus vous le regardez et y pensez sous la douche. :)
dash-tom-bang
214

Tenez également compte des 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 émettra une instruction cpu pour effectuer le même travail plus rapidement.

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


Sur x86, vous pouvez indiquer au compilateur qu'il peut assumer la prise en popcntcharge des instructions avec -mpopcntou -msse4.2pour activer également les instructions vectorielles ajoutées dans la même génération. Voir les options de GCC x86 . -march=nehalem(ou -march=quel que soit le processeur que vous voulez que votre code assume et ajuste) pourrait être un bon choix. L'exécution du binaire résultant sur un processeur plus ancien entraînera une erreur d'instruction illégale.

Pour rendre les 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 l' popcntinstruction x86 , mais contrairement à gcc, c'est vraiment un intrinsèque pour l'instruction matérielle et nécessite un support matériel.


Utilisation std::bitset<>::count()au lieu d'un intégré

En théorie, tout compilateur qui sait comment effectuer un décompte efficace pour le processeur cible doit exposer cette fonctionnalité via ISO C ++ std::bitset<>. En pratique, vous pourriez être mieux avec le bit-hack ET / shift / ADD dans certains cas pour certains CPU cibles.

Pour les architectures cibles où le popcount matériel est une extension facultative (comme x86), tous les compilateurs n'en ont pas qui en tirent std::bitsetparti lorsqu'ils sont disponibles. Par exemple, MSVC n'a aucun moyen d'activer la popcntprise en charge 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 fonctionnalité distinct pour popcnt.)

Mais au moins, vous obtenez quelque chose de portable qui fonctionne partout, et avec gcc / clang avec les bonnes options cibles, vous obtenez un popcount matériel pour les architectures qui le prennent en charge.

#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, icc et MSVC sur l'explorateur du compilateur Godbolt.

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 la intversion arg):

    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 se compile bien uniquement pour x86 avec gcc / clang / icc.

Notez également que le remplacement de gcc pour les architectures sans popcount à instruction unique est une recherche de table octet par octet. Ce n'est pas merveilleux pour ARM, par exemple .

Peter Cordes
la source
5
Je suis d'accord que c'est une bonne pratique en général, mais sur XCode / OSX / Intel, je l'ai trouvé pour générer du code plus lent que la plupart des suggestions publiées ici. Voir ma réponse pour plus de détails.
5
L'Intel i5 / i7 possède l'instruction SSE4 POPCNT qui le fait, en utilisant des registres à usage général. GCC sur mon système n'émet pas cette instruction en utilisant cette intrinsèque, je suppose à cause de l'option no -march = nehalem pour le moment.
matja
3
@matja, mon GCC 4.4.1 émet l'instruction popcnt si je compile avec -msse4.2
Nils Pipenbrinck
74
utilisez les c ++ std::bitset::count. après avoir inséré cela compile en un seul __builtin_popcountappel.
deft_code
1
@nlucaroni Eh bien, oui. Les temps changent. J'ai écrit cette réponse en 2008. Aujourd'hui, nous avons un popcount natif et l'intrinsèque se compilera en une seule déclaration d'assembleur si la plate-forme le permet.
Nils Pipenbrinck
184

À mon avis, la "meilleure" solution est celle qui peut être lue par un autre programmeur (ou le programmeur d'origine deux ans plus tard) sans commentaires abondants. Vous voudrez peut-être la solution la plus rapide ou la plus intelligente que certains aient déjà fournie, mais je préfère la lisibilité à 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 documentiez 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 types de données spécifiques, ils ne sont donc pas portables. Mais, comme de nombreuses optimisations de performances ne sont pas portables de toute façon, cela peut ne pas être un problème. Si vous voulez la portabilité, je m'en tiendrai à la solution lisible.

paxdiablo
la source
21
Au lieu de diviser par 2 et de le commenter comme "bits de décalage ...", vous devez simplement utiliser l'opérateur de décalage (>>) et laisser de côté le commentaire.
indiv
9
ne serait-il pas plus judicieux de remplacer if ((value & 1) == 1) { count++; }par count += value & 1?
Ponkadoodle
21
Non, la meilleure solution n'est pas la plus lisible dans ce cas. Ici, le meilleur algorithme est le plus rapide.
NikiC
21
C'est entièrement votre opinion, @nikic, même si vous êtes libre de me dévaloriser, évidemment. Il n'y avait aucune mention dans la question quant à la façon de quantifier le "meilleur", les mots "performance" ou "rapide" ne peuvent être vus nulle part. C'est pourquoi j'ai opté pour le lisible.
paxdiablo
3
Je lis cette réponse 3 ans plus tard, et je la trouve comme la meilleure réponse car elle est lisible et contient plus de commentaires. période.
waka-waka-waka
98

Extrait de Hacker's Delight, 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 instructions de ~ 20-ish (dépend de l'arc), pas de branchement.

Hacker's Delight est délicieux! Hautement recommandé.

Kevin Little
la source
8
La méthode Java Integer.bitCount(int)utilise cette même implémentation exacte.
Marco Bolis
Ayant un peu de mal à suivre cela - comment cela changerait-il si nous ne nous soucions que des valeurs 16 bits, au lieu de 32 bits?
Jeremy Blum
Peut-être que les pirates sont ravis, mais je donnerais un bon coup de pied à quiconque appelle cela popau lieu de population_count(ou pop_cntsi vous devez avoir une abréviation). @MarcoBolis Je suppose que cela sera vrai pour toutes les versions de Java, mais officiellement cela dépendra de l'implémentation :)
Maarten Bodewes
Et cela ne nécessite aucune multiplication, comme le code dans la réponse acceptée.
Alex
Notez que lors de la généralisation à 64 bits, il y a un problème. Le résultat ne peut pas être 64, à cause du masque.
Albert van der Horst
76

Je pense que le moyen le plus rapide - sans utiliser de tables de recherche et de popcount - est le suivant. Il compte les bits définis 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 définis en divisant en deux moitiés, en comptant le nombre de bits définis dans les deux moitiés, puis en les additionnant. Aussi connu sous le nom de Divide and Conquerparadigme. Entrons dans les détails ..

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

Le nombre de bits sur deux bits peut être 0b00, 0b01ou 0b10. Essayons de travailler cela 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 indique le nombre de bits définis dans chaque paire de deux bits. Si le nombre à deux bits est >= 2 (0b10)alors andproduit 0b01, sinon il produit 0b00.

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

Cette déclaration doit être facile à comprendre. Après la première opération, nous avons 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 résumons ensuite le résultat ci-dessus, en nous donnant le nombre total de bits définis sur 4 bits. La dernière affirmation est la plus délicate.

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

Décomposons-le plus loin ...

v + (v >> 4)

C'est similaire à la deuxième déclaration; nous comptons plutôt les bits définis par groupes de 4. Nous savons - en raison de nos opérations précédentes - que chaque quartet contient le nombre de bits définis. Regardons un exemple. Supposons que nous ayons l'octet 0b01000010. Cela signifie que le premier quartet a son jeu de 4 bits et le second a son jeu de 2 bits. Maintenant, nous ajoutons ces grignotages ensemble.

0b01000010 + 0b01000000

Il nous donne le nombre de bits définis dans un octet, dans le premier quartet 0b01100010et donc nous masquons les quatre derniers octets de tous les octets du nombre (en les éliminant).

0b01100010 & 0xF0 = 0b01100000

Désormais, chaque octet contient le nombre de bits définis. Nous devons les additionner tous ensemble. L'astuce consiste à multiplier le résultat par 0b10101010lequel a une propriété intéressante. Si notre numéro a quatre octets, A B C Dil en résultera un nouveau numéro 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 peuvent être représentés comme 0b00100000.

Tout ce dont nous avons besoin maintenant est le premier octet qui a la somme de tous les bits définis dans tous les octets, et nous l'obtenons >> 24. Cet algorithme a été conçu pour les 32 bitmots mais peut être facilement modifié pour les 64 bitmots.

vidit
la source
De quoi s'agit- c = il? On dirait qu'il devrait être éliminé. De plus, suggérez un jeu de paren supplémentaire A "((((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24" pour éviter certains avertissements classiques.
chux
4
Une caractéristique importante est que cette routine 32 bits fonctionne à la fois pour popcount(int v)et popcount(unsigned v). Pour la portabilité, considérez popcount(uint32_t v), etc. Vraiment comme la partie * 0x1010101.
chux
sauce ? (livre, lien, noms des envahisseurs, etc.) serait TRÈS bien accueilli. Parce qu'alors nous pouvons coller cela dans nos bases de code avec un commentaire d'où il vient.
v.oddou
1
Je pense que pour plus de clarté, la dernière ligne doit être écrite comme suit: return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;nous n'avons donc pas besoin de compter les lettres pour voir ce que vous faites réellement (puisque vous avez supprimé la première 0, j'ai accidentellement pensé que vous aviez utilisé le mauvais motif de bits (inversé) comme masque - c'est jusqu'à ce que je note qu'il n'y a que 7 lettres et non 8).
emem
Cette multiplication par 0x01010101 peut être lente, selon le processeur. Par exemple, dans mon ancien PowerBook G4, 1 multiplication était à peu près aussi lente que 4 ajouts (pas aussi mauvais que la division, où 1 division était à peu près aussi lente que 23 ajouts).
George Koehler
54

Je me suis ennuyé et j'ai chronométré un milliard d'itérations de trois approches. Le compilateur est gcc -O3. Le CPU est tout ce qu'ils mettent dans le Macbook Pro de 1ère génération.

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

La deuxième place revient au même code mais en recherchant 4 octets au lieu de 2 demi-mots. Cela a pris environ 5,5 secondes.

La troisième place revient à l'approche "d'addition latérale" qui a pris un peu de temps, qui a pris 8,6 secondes.

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

L'approche de comptage un bit à la fois a été plus lente, et je me suis ennuyé d'attendre qu'elle se termine.

Donc, si vous vous souciez de la performance avant tout, utilisez la première approche. Si vous vous en souciez, mais pas assez pour y dépenser 64 Ko de RAM, utilisez la deuxième approche. Sinon, utilisez l'approche un bit à la fois lisible (mais lente).

Il est difficile de penser à une situation dans laquelle vous voudriez utiliser l'approche du bit-twiddling.

Edit: Résultats similaires ici .

Mike F
la source
49
@Mike, L'approche basée sur la table est imbattable si la table est dans le cache. Cela se produit dans des micro-benchmarks (par exemple, faites des millions de tests en boucle serrée). Cependant, un échec de cache prend environ 200 cycles, et même le popcount le plus naïf sera plus rapide ici. Cela dépend toujours de l'application.
Nils Pipenbrinck
10
Si vous n'appelez pas cette routine plusieurs millions de fois dans une boucle serrée, vous n'avez aucune raison de vous soucier de ses performances et pourriez tout aussi bien utiliser l'approche naïve mais lisible car la perte de performances sera négligeable. Et FWIW, la LUT 8 bits est mise en cache dans les 10 à 20 appels.
6
Je ne pense pas qu'il soit si difficile d'imaginer une situation où il s'agit d'un appel de feuille effectué à partir de la méthode - en fait, le gros du travail - dans votre application. En fonction de ce qui se passe (et du filetage), la version plus petite pourrait gagner. Beaucoup d'algorithmes ont été écrits qui battent leurs pairs en raison d'une meilleure localité de référence. Pourquoi pas ça aussi?
Jason
Essayez cela avec clang, il est beaucoup plus intelligent d'implémenter des builtins.
Matt Joiner
3
GCC n'émettra pas d'instruction popcont sauf s'il est appelé avec -msse4.2, cas qui est plus rapide que 'addition latérale'.
lvella
54

S'il vous arrive d'utiliser Java, la méthode intégrée le Integer.bitCountfera.

Noether
la source
Lorsque Sun a fourni différentes API, il doit utiliser une logique en arrière-plan, non?
Vallabh Patade
2
En guise de remarque, l'implémentation de Java utilise le même algorithme que Kevin Little .
Marco Bolis
2
Mis à part l'implémentation, c'est probablement le message d'intention le plus clair pour les développeurs qui maintiennent votre code après vous (ou quand vous y revenez 6 mois plus tard)
divillysausages
31
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;
}

Permettez-moi d'expliquer cet algorithme.

Cet algorithme est basé sur l'algorithme Divide and Conquer. Supposons qu'il existe un entier 8 bits 213 (11010101 en binaire), l'algorithme fonctionne comme ceci (à chaque fois fusionnez 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)
+-------------------------------+
abcdabcd987
la source
7
Cet algorithme est la version publiée par Matt Howells, avant d'être optimisé au point de devenir illisible.
Lefteris E
29

C'est l'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ées avec -O3 en utilisant les lignes C ++ pour éliminer la surcharge des appels de fonction, un milliard d'itérations, en gardant la somme cumulée de tous les décomptes pour garantir que le compilateur ne supprime rien d'important, en utilisant rdtsc pour le timing ( cycle d'horloge précis).

inline int pop2 (non signé x, non signé 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);
    retourner (x + y) & 0x000000FF;
}

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

Cela a à voir avec les chaînes de dépendance des instructions, qui sont très mauvaises pour cet algorithme. Je pourrais presque doubler à nouveau la vitesse en utilisant une paire de registres 64 bits. En fait, si j'étais intelligent et ajoutais x + ya un peu plus tôt, je pourrais raser certains changements. La version 64 bits avec quelques petits ajustements serait à peu près égale, mais compterait à nouveau deux fois plus de bits.

Avec les registres SIMD 128 bits, encore un autre facteur de deux, et les jeux d'instructions SSE ont souvent aussi des raccourcis intelligents.

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. Le 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 la version 64 bits modifiée au banc. Pour cette taille unique (long non signé) == 8

inline int pop2 (unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) et 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x333333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x333333333333333333) + ((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); 
    retourner x & 0xFF;
}

Cela semble correct (je ne teste pas soigneusement, cependant). Maintenant, les timings sortent à 10,70 gigacycles / 14,1 gigacycles. Ce nombre ultérieur totalisait 128 milliards de bits et correspond à 5,9 secondes écoulées sur cette machine. La version non parallèle accélère un tout petit peu car je suis en mode 64 bits et elle aime les registres 64 bits légèrement mieux que les registres 32 bits.

Voyons voir s'il y a un peu plus de pipelines OOO à avoir ici. C'était un peu plus compliqué, donc j'ai testé un peu. Chaque terme totalise à lui seul 64, la somme combinée à 256.

inline int pop4 (unsigned long x, unsigned long y, 
                non signé long u, non signé long v)
{
  enum {m1 = 0x555555555555555555, 
         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);
    retourner x & 0x000001FF;
}

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

   hitime b4 = rdtsc (); 
   pour (non signé long i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
      somme + = pop4 (i, i ^ 1, ~ i, i | 1); 
   hitime e4 = rdtsc (); 

256 milliards de bits additionnés en 8,17 secondes se sont écoulés. Fonctionne à 1,02 s pour 32 millions de bits comme indiqué dans la recherche de table 16 bits. Je ne peux pas comparer directement, car l'autre banc ne donne pas de vitesse d'horloge, mais il semble que j'ai supprimé la morve de l'édition de table de 64 Ko, ce qui est une utilisation tragique du cache L1 en premier lieu.

Mise à jour: décidé de faire l'évidence et de créer pop6 () en ajoutant quatre autres lignes dupliquées. Entré à 22,8 gc, 384 milliards de bits additionnés en 9,5 secondes se sont écoulés. Il y a donc encore 20% à 800 ms pour 32 milliards de bits.

utilisateur183351
la source
2
La meilleure forme non assembleur comme celle-ci, j'ai vu 24 mots 32 bits déroulés à la fois. dalkescientific.com/writings/diary/popcnt.c , stackoverflow.com/questions/3693981/… , dalkescientific.com/writings/diary/archive/2008/07/05/…
Matt Joiner
28

Pourquoi ne pas diviser itérativement par 2?

count = 0
tandis que n> 0
  si (n% 2) == 1
    compter + = 1
  n / = 2  

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

daniel
la source
Cela fonctionnera et est facile à comprendre, mais il existe des méthodes plus rapides.
Matt Howells
2
À moins que vous ne le fassiez BEAUCOUP , l'impact sur les performances serait négligeable. Donc, toutes choses étant égales par ailleurs, je suis d'accord avec Daniel pour dire que «le meilleur» implique «ne se lit pas comme du charabia».
2
Je n'ai délibérément pas défini le «meilleur» pour obtenir une variété de méthodes. Regardons les choses en face si nous sommes descendus au niveau de ce genre de manipulation de bits, nous recherchons probablement quelque chose d'uber-fast qui ressemble à un chimpanzé.
Matt Howells, le
6
Mauvais code. Un compilateur pourrait en faire un bon, mais dans mes tests, GCC ne l'a pas fait. Remplacez (n% 2) par (n & 1); ET étant beaucoup plus rapide que MODULO. Remplacez (n / = 2) par (n >> = 1); décalage de bits beaucoup plus rapide que la division.
Mecki
6
@Mecki: Dans mes tests, gcc (4.0, -O3) a fait les optimisations évidentes.
26

Le bit-twiddling de Hacker's Delight devient tellement plus clair lorsque vous écrivez les motifs 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 chacun d'eux. Les autres étapes ajoutent des morceaux d'ordre élevé aux morceaux d'ordre inférieur, doublant la taille du morceau jusqu'à ce que le décompte final prenne l'intégralité de l'intégralité.

John Dimm
la source
3
Cette solution semble avoir un problème mineur, lié à la priorité des opérateurs. Pour chaque terme, il doit indiquer: x = (((x >> 1) & 0b0101010101010101010101010101010101) + (x & 0b01010101010101010101010101010101)); (c'est-à-dire des parens supplémentaires ajoutés).
Nopik
21

Pour un juste milieu entre une table de recherche 2 32 et une itération à 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;
}

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

PhirePhly
la source
Pas portable. Que faire si le CPU a 9 octets de bits? Oui, il y a de vrais processeurs comme ça là-bas ...
Robert S. Barnes
15
@Robert S. Barnes, cette fonction fonctionnera toujours. Il ne fait aucune hypothèse sur la taille des mots natifs et ne fait aucune référence aux "octets".
finnw
19

Cela peut être fait dans O(k), où kest le nombre de bits défini.

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

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

    return count;
}
herohuyongtao
la source
Il s'agit essentiellement de l' algorithme de Brian Kernighan (vous vous souvenez de lui?), Avec le changement mineur qu'il a utilisé la n &= (n-1)forme la plus succincte .
Adrian Mole
17

Ce n'est pas la solution la plus rapide ou la meilleure, mais j'ai trouvé la même question à ma manière, et j'ai commencé à réfléchir et à réfléchir. enfin j'ai réalisé que cela peut être fait comme ça 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 partie périodique, puis vous réalisez la différence entre les périodes ... donc Voici:

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);
    }
}
Peter
la source
4
oh j'aime ça. que diriez-vous de la version python:def f(i, d={0:lambda:0, 1:lambda:1, 2:lambda:1, 3:lambda:2}): return d.get(i, lambda: f(i//4) + f(i%4))()
underrun
10

La fonction que vous recherchez est souvent appelée «somme latérale» ou «nombre de population» d'un nombre binaire. Knuth en parle dans le pré-fascicule 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 l'article de Peter Wegner "A Technique for Counting Ones in a Binary Computer", tiré des Communications de l'ACM , Volume 3 (1960) Numéro 5, page 322 . Il y donne deux algorithmes différents, l'un optimisé pour les nombres censés être "clairsemés" (c'est-à-dire qu'ils en ont un petit nombre) et l'autre pour le cas contraire.

Michael Dorfman
la source
10
  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;
    }
stacktay
la source
9

Quelques questions ouvertes: -

  1. Si le nombre est négatif, alors?
  2. Si le nombre est 1024, la méthode de "division itérative par 2" va itérer 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 une référence complète, voir:

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

Baban
la source
9

Je pense que la méthode de Brian Kernighan sera également utile ... Elle passe par autant d'itérations qu'il y a de bits définis. Donc, si nous avons un mot de 32 bits avec uniquement le bit le plus élevé, il ne passera qu'une seule 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 C Programming Language 2nd 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écouverte indépendamment par Derrick Lehmer et publiée en 1964 dans un livre édité par Beckenbach.)"

Erorr
la source
8

J'utilise le code ci-dessous qui est plus intuitif.

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

Logique: n & (n-1) réinitialise le dernier bit défini de n.

PS: Je sais que ce n'est pas une solution O (1), quoique intéressante.

Manish Mulani
la source
c'est bon pour les nombres "clairsemés" avec un petit nombre de bits, comme c'est le cas O(ONE-BITS). Il s'agit bien de O (1) car il y a au plus 32 bits à un.
ealfonso
7

Que voulez-vous dire par "meilleur algorithme"? Le code court ou le code jeûné? 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 majeur et non la taille du code, je pense que la suite 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.

Horcrux7
la source
Mon code a 10 opérations. Votre code a 12 opérations. Votre lien fonctionne avec des tableaux plus petits (5). J'utilise 256 éléments. Avec la mise en cache peut être un problème. Mais si vous l'utilisez très fréquemment, ce n'est pas un problème.
Horcrux7
Cette approche est sensiblement plus rapide que l'approche de twiddling de bits, comme il se trouve. Quant à l'utilisation de plus de mémoire, elle compile en moins de code et ce gain est répété chaque fois que vous insérez la fonction. Il pourrait donc facilement s’avérer une victoire nette.
7

J'ai écrit une macro de comptage de bits rapide pour les machines RISC vers 1990. Elle n'utilise pas d'arithmétique avancée (multiplication, division,%), de récupération de mémoire (beaucoup trop lente), de branches (trop lente), mais elle suppose que le CPU a un Décalage en barillet 32 ​​bits (en d'autres termes, >> 1 et >> 32 prennent le même nombre 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 les temporaires et réutilisé 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, car il semble prendre au moins 3 instructions (masque, décalage, opérateur) pour réduire de moitié le nombre d'addends, donc log_2 (32) = 5, 5 x 3 = 15 instructions est une limite quasi-inférieure.

#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 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 1ère colonne (A) ci-dessus, la décale de 1 bit vers la droite et la soustrais de AB, j'obtiens la sortie (CD). L'extension à 3 bits est similaire; vous pouvez le vérifier avec une table booléenne à 8 rangées comme la mienne ci-dessus si vous le souhaitez.

  • Don Gillies
systemBuilder
la source
7

si vous utilisez C ++, une autre option consiste à utiliser la métaprogrammation de modèle:

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

l'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 davantage ce modèle pour utiliser différents types (même la taille de bits à détection automatique) mais je l'ai gardé simple pour plus de clarté.

edit: oublié de mentionner que c'est bon car cela devrait fonctionner dans n'importe quel compilateur C ++ et il déroule simplement votre boucle pour vous si une valeur constante est utilisée pour le nombre de bits (en d'autres termes, je suis presque sûr que c'est la méthode générale la plus rapide tu trouveras)

Pentaphobe
la source
Malheureusement, le comptage des bits ne se fait pas en parallèle, il est donc probablement plus lent. Pourrait faire un bien constexprcependant.
imallett
D'accord - c'était un exercice amusant de récursivité de modèle C ++, mais certainement une solution assez naïve.
pentaphobe
6

J'aime particulièrement cet exemple du fichier de 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 que c'est si joli!

Ross
la source
1
Comment fonctionne-t-il par rapport aux autres suggestions?
asdf
6

Java JDK1.5

Integer.bitCount (n);

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

vérifiez 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);
         }
Rahul
la source
Pas vraiment un algorithme, c'est juste un appel de bibliothèque. Utile pour Java, pas tant pour tout le monde.
benzado
2
@benzado a raison mais +1 quand même, car certains développeurs Java pourraient ne pas être au courant de la méthode
finnw
@finnw, je suis l'un de ces développeurs. :)
neevek
6

J'ai trouvé une implémentation du comptage de bits dans un tableau avec l'utilisation de l'instruction SIMD (SSSE3 et AVX2). Ses performances sont 2 à 2,5 fois supérieures à celles de 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];
}

Version AVX2:

#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];
}
ErmIg
la source
6

J'utilise toujours cela 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();
}
diugalde
la source
5

Il existe de nombreux algorithmes pour compter les bits définis; mais je pense que le meilleur est le plus rapide! Vous pouvez voir le détail sur cette page:

Bit Twiddling Hacks

Je suggère celui-ci:

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

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 processeur 64 bits avec une division de module rapide pour être efficace. La première option ne prend que 3 opérations; la deuxième option prend 10; et la troisième option prend 15.

Mostafa
la source
5

Solution C # rapide utilisant un tableau pré-calculé de décomptes d'octets avec branchement sur la taille d'entrée.

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
    };
}
papa
la source
Ironiquement, ce tableau aurait pu être créé par l'un des algorithmes publiés dans ce fil! Néanmoins, l'utilisation de tables comme celle-ci signifie des performances à temps constant. Aller plus loin et créer une table de traduction de 64 Ko réduirait donc de moitié les opérations AND, SHIFT et ADD nécessaires. Un sujet intéressant pour les manipulateurs de bits!
user924272
Les tables plus volumineuses peuvent être plus lentes (et non à temps constant) en raison de problèmes de cache. Vous pouvez «rechercher» 3 bits à la fois avec (0xe994 >>(k*2))&3, sans accès à la mémoire ...
greggo
5

Voici un module portable (ANSI-C) qui peut comparer chacun de vos algorithmes sur n'importe quelle architecture.

Votre CPU a 9 octets de bits? Pas de problème :-) Pour le moment, il implémente 2 algorithmes, l'algorithme K&R et une table de recherche par octets. 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 portable l'algorithme "Hacker's Delight", 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
Robert S. Barnes
la source
1
J'aime beaucoup votre plug-in, votre approche polymorphe, ainsi que le commutateur pour construire en tant que bibliothèque réutilisable ou exécutable de test autonome. Très bien pensé =)
5

ce que tu peux faire c'est

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

la logique derrière cela est que les bits de n-1 sont inversés par rapport au bit le plus à droite de n. si n = 6, c'est-à-dire 110, alors 5 est 101, les bits sont inversés par rapport au bit le plus à droite de n. Donc, si nous et ces deux, nous ferons le bit le plus à droite 0 à chaque itération et irons toujours au bit défini le plus à droite suivant, d'où le comptage du bit défini.

Varun Gusain
la source