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


8 bits représentant le numéro 7 ressemblent à ceci:

00000111

Trois bits sont définis.

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


751


origine


Réponses:


Ceci est connu comme le 'Hamming Poids',' popcount 'ou' ajout latéral '.

Le «meilleur» algorithme dépend vraiment du processeur sur lequel vous êtes 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 binaires. Les instructions parallèles (comme x86 popcnt, sur les processeurs où il est supporté) sera presque certainement le plus rapide. Certaines autres architectures peuvent avoir une instruction lente implémentée avec une boucle microcodée qui teste un peu par cycle (citation requise).

Une méthode de recherche de table pré-remplie peut être très rapide si votre CPU a un cache important et / ou si vous faites beaucoup de ces instructions dans une boucle serrée. Cependant, il peut souffrir à cause du coût d'un "cache manqué", où le CPU doit récupérer une partie de la table depuis la mémoire principale.

Si vous savez que vos octets seront principalement des 0 ou des 1, il y a 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'. J'ai exprimé cela dans un pseudo-langage de type C, vous devrez peut-être l'ajuster pour travailler pour une langue particulière (par exemple en utilisant uint32_t pour C ++ et >>> en Java):

int numberOfSetBits(int i)
{
     // Java: 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;
}

Cela a le meilleur comportement de l'un des algorithmes discuté, donc traitera efficacement tout modèle d'utilisation ou les valeurs que vous lui lancez.


Cet algorithme SWAR bit à bit pourrait paralléliser pour être effectué dans plusieurs éléments vectoriels à la fois, au lieu de dans un seul registre entier, pour une accélération sur les processeurs avec SIMD mais pas d'instruction popcount utilisable. (Par exemple, le code x86-64 qui doit s'exécuter sur n'importe quel processeur, pas seulement Nehalem ou plus tard.)

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

Sur les processeurs Intel, l'instruction popcnt 64 bits matérielle peut surpasser SSSE3 PSHUFB implémentation bit-parallèle d'environ un facteur de 2, mais seulement si votre compilateur obtient juste. Sinon SSE peut sortir significativement en avance. Les nouvelles versions du compilateur sont conscientes popcnt fausse dépendance  problème sur Intel.

Les références:

https://graphics.stanford.edu/~seander/bithacks.html

https://en.wikipedia.org/wiki/Hamming_weight

http://gurmeet.net/puzzles/fast-bit-counting-routines/

http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)


764



Considérez é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 va générer un appel à une fonction. Dans le meilleur des cas, le compilateur émet une instruction cpu pour effectuer le même travail plus rapidement.

Les intrinsèques de GCC fonctionnent même sur plusieurs plates-formes. Popcount deviendra grand public 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 dire au compilateur qu'il peut prendre en charge popcnt instruction avec -mpopcnt ou -msse4.2 pour activer également les instructions vectorielles qui ont été ajoutées dans la même génération. Voir Options GCC x86. -march=nehalem (ou -march= quel que soit le CPU que vous voulez que votre code assume et pour syntoniser) pourrait être un bon choix. L'exécution du binaire résultant sur un ancien processeur entraînera une erreur d'instruction illégale.

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


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

En théorie, tout compilateur qui sait calculer efficacement le processeur cible devrait exposer cette fonctionnalité via ISO C ++ std::bitset<>. En pratique, vous pourriez être mieux avec le bit-hack AND / shift / ADD dans certains cas pour certains processeurs cibles.

Pour les architectures cibles où le popcount matériel est une extension optionnelle (comme x86), tous les compilateurs n'ont pas std::bitset qui en profite quand il est disponible. Par exemple, MSVC n'a aucun moyen de permettre popcnt support à la compilation, et utilise toujours une recherche de table, même avec /Ox /arch:AVX (ce qui implique SSE4.2, bien qu'il y ait techniquement 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 du 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, 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 le int version 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 au x86 ni spécifique au GNU, mais ne se compile bien que pour x86 avec gcc / clang / icc.

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


185



À 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 copieux. Vous pouvez bien vouloir la solution la plus rapide ou la plus intelligente que certains ont 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 reposent sur des tailles de type de données spécifiques, ils ne sont donc pas portables. Mais, étant donné que de nombreuses optimisations de performances ne sont pas portables, ce n'est peut-être pas un problème. Si vous voulez la portabilité, je m'en tiendrai à la solution lisible.


168



D'après 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 dans les instructions ~ 20-ish (dépend de l'arche), pas de branchement.

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


94



Je pense que le moyen le plus rapide - sans utiliser les tables de recherche et popcount-est le suivant. Il compte les bits réglés 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 comme Divide and Conquer paradigme. Entrons dans les détails ..

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

Le nombre de bits dans deux bits peut être 0b00, 0b01 ou 0b10. Essayons de travailler 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 définis dans chaque paire de deux bits. Si le numéro à deux bits est >= 2 (0b10) puis and produit 0b01sinon 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 nombre de bits mis 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 en 4 bits. La dernière déclaration est la plus difficile.

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

Allons le décomposer plus loin ...

v + (v >> 4)

C'est semblable à la deuxième déclaration; nous comptons à la place les bits définis en groupes de 4. Nous savons - à cause de nos opérations précédentes - que chaque grignotage 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 son jeu de 2 bits. Maintenant, nous ajoutons ces grignotages ensemble.

0b01000010 + 0b01000000

Il nous donne le nombre de bits mis dans un octet, dans le premier quartet 0b01100010 et donc nous masquons les quatre derniers octets de tous les octets dans le nombre (en les rejetant).

0b01100010 & 0xF0 = 0b01100000

Maintenant, chaque octet a le nombre de bits définis. Nous devons les additionner tous ensemble. L'astuce consiste à multiplier le résultat par 0b10101010 qui a une propriété intéressante. Si notre numéro 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, ce qui peut être représenté 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 par >> 24. Cet algorithme a été conçu pour 32 bit mots, mais peut être facilement modifié pour 64 bit mots.


69



Je m'ennuyais, et chronométré un milliard d'itérations de trois approches. Le compilateur est gcc -O3. CPU est tout ce qu'ils mettent dans le 1er gen 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] );
}

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

La troisième place revient à l'approche «ajout latéral», qui a pris 8,6 secondes.

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

Le comptage d'un bit à la fois était plus lent, et je m'ennuyais d'attendre que cela se termine.

Donc, si vous vous souciez de la performance par-dessus tout, utilisez la première approche. Si cela vous intéresse, mais pas assez pour 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 où vous voudriez utiliser l'approche du twittling.

Edit: Des résultats similaires ici.


53



Si vous utilisez Java, la méthode intégrée Integer.bitCount Fera cela.


52