Comment compter le nombre de bits activés dans un nombre entier de 32 bits ?

Question

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

00000111

Trois bits sont activés.

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

Answer 1

C'est ce que l'on appelle le Poids de Hamming ", " popcount " ou " sideways addition ".

Certains processeurs ont une seule instruction intégrée pour le faire et d'autres ont des instructions parallèles qui agissent sur des vecteurs de bits. Des instructions comme celle du x86 popcnt (sur les CPU où il est supporté) sera presque certainement le plus rapide pour un seul entier. 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 - Le popcount matériel est normalement rapide s'il existe).

Le "meilleur" algorithme dépend vraiment de l'unité centrale que vous utilisez et de vos habitudes d'utilisation.

Votre compilateur peut savoir comment faire quelque chose qui est bon pour le CPU spécifique pour lequel vous compilez, par ex. C++20 std::popcount() ou C++ std::bitset<32>::count() comme un moyen portable d'accéder à des fonctions intégrées/ intrinsèques (cf. une autre réponse sur cette question). Mais le choix de votre compilateur comme solution de repli pour les processeurs cibles qui n'ont pas de popcnt matériel peut ne pas être optimal pour votre cas d'utilisation. Ou votre langage (par exemple le C) peut ne pas exposer de fonction portable qui pourrait utiliser un popcount spécifique au CPU quand il y en a un.

---

Algorithmes portables qui ne nécessitent pas (ou ne bénéficient pas) d'un support matériel.

La méthode de consultation d'une table préremplie peut être très rapide si votre CPU dispose d'un grand cache et que vous effectuez un grand nombre de ces opérations dans une boucle serrée. Cependant, elle peut être pénalisée par le coût d'un "manque de cache", lorsque le CPU doit aller chercher une partie de la table en mémoire principale. (Cherchez chaque octet séparément pour garder la table petite). Si vous voulez popcount pour une gamme contiguë de nombres, seul l'octet le plus bas change pour les groupes de 256 nombres, ce qui en fait une très bonne .

Si vous savez que vos octets seront principalement des 0 ou des 1, il existe des algorithmes efficaces pour ces scénarios, par exemple en effaçant l'ensemble le plus bas avec un bithack dans une boucle jusqu'à ce qu'il devienne zéro.

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

GCC10 et clang 10.0 peuvent reconnaître ce modèle / idiome et le compiler vers un popcnt matériel ou une instruction équivalente lorsqu'elle est disponible, vous donnant le meilleur des deux mondes. ( https://godbolt.org/z/qGdh1dvKK )

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

Pour JavaScript : contraindre à un nombre entier con |0 pour la performance : changez la première ligne en i = (i|0) - ((i >> 1) & 0x55555555);

Cet algorithme a le meilleur comportement dans le pire des cas de tous les algorithmes discutés, il traitera donc efficacement tous les modèles d'utilisation ou valeurs que vous lui proposerez. (Ses performances ne dépendent pas des données sur les processeurs normaux où toutes les opérations sur les entiers, y compris la multiplication, se font en temps constant. Il ne devient pas plus rapide avec des entrées "simples", mais il est encore assez décent).

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)

---

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 et impairs, du décalage pour les aligner et de l'addition. Cela permet de réaliser 16 additions séparées dans des accumulateurs de 2 bits ( SWAR = SIMD dans un registre ). Comme (i & 0x55555555) + ((i>>1) & 0x55555555) .

L'étape suivante prend les huit impairs/pairs de ces 16x accumulateurs de 2 bits et les additionne à nouveau, produisant 8x sommes de 4 bits. Le site i - ... L'optimisation n'est pas possible cette fois-ci, donc il ne fait que masquer le changement de vitesse avant/après. En utilisant le même 0x33... constante les deux fois au lieu de 0xccc... avant le décalage est une bonne chose lors de la compilation pour les ISA qui doivent construire séparément les constantes 32 bits dans les registres.

L'étape finale de décalage et d'ajout de (i + (i >> 4)) & 0x0F0F0F0F s'élargit à 4 accumulateurs de 8 bits. Il masque après en ajoutant au lieu d'avant, parce que la valeur maximale dans un accumulateur de 4-bit est 4 si les 4 bits d'entrée correspondants ont été activés. 4+4 = 8, ce qui correspond toujours à 4 bits, de sorte que la retenue entre les éléments du quartet est impossible dans le cas d'un système d'information. i + (i >> 4) .

Jusqu'à présent, il s'agit simplement d'un SIMD normal utilisant les techniques SWAR avec quelques optimisations intelligentes. En continuant avec le même schéma pour 2 étapes supplémentaires, on peut passer à 2x 16-bit puis 1x 32-bit. Mais il existe un moyen plus efficace sur les machines avec une multiplication matérielle rapide :

Une fois que nous avons assez peu d'"éléments", un multiplicateur avec une constante magique peut additionner tous les éléments dans l'élément supérieur . Dans ce cas, il s'agit d'éléments d'octets. La multiplication se fait par décalage à gauche et addition, donc *une multiplication de `x 0x01010101résulte enx + (x<<8) + (x<<16) + (x<<24)` .** Nos éléments 8 bits sont suffisamment larges (et contiennent des comptes suffisamment petits) pour que cela ne produise pas de report. en les 8 premiers bits.

Une version 64 bits de cette peut faire 8x éléments de 8 bits dans un entier de 64 bits avec un multiplicateur de 0x010101010101010101, et extraire l'octet de poids fort avec >>56 . Ainsi, il n'y a pas d'étapes supplémentaires, juste des constantes plus larges. C'est ce que GCC utilise pour __builtin_popcountll sur les systèmes x86 lorsque le matériel popcnt L'instruction n'est pas activée. Si vous pouvez utiliser des builtins ou des intrinsics pour cela, faites-le pour donner au compilateur une chance d'effectuer des optimisations spécifiques à la cible.

---

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

Cet algorithme bitwise-SWAR pourrait être parallélisé pour être fait dans plusieurs éléments vectoriels à la fois, au lieu d'un seul registre entier, pour une accélération sur les CPUs avec SIMD mais sans instruction popcount utilisable. (par exemple, du code x86-64 qui doit s'exécuter sur n'importe quel CPU, pas seulement Nehalem ou plus).

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

Sur les processeurs Intel, l'instruction popcnt 64 bits matérielle peut être plus performante qu'une instruction popcnt 64 bits matérielle. SSSE3 PSHUFB mise en œuvre bit-parallèle d'un facteur 2 environ, mais seulement si votre compilateur le fait bien . Sinon, SSE peut s'en sortir avec une avance considérable. Les versions plus récentes des compilateurs sont conscientes de la popcnt false dependency problème sur Intel .

• https://github.com/WojciechMula/sse-popcount popcount SIMD x86 de pointe pour SSSE3, AVX2, AVX512BW, AVX512VBMI ou AVX512 VPOPCNT. Utilisation de Harley-Seal à travers les vecteurs pour différer le popcount dans un élément. (Aussi ARM NEON)
• Comptage de 1 bit (comptage de population) sur de grandes données en utilisant AVX-512 ou AVX-2
• liés : https://github.com/mklarqvist/positional-popcount - comptes séparés pour chaque position de bit de multiples entiers de 8, 16, 32 ou 64 bits. (Encore une fois, les SIMD de x86, y compris AVX-512 qui est vraiment bon à cela, avec vpternlogd fabrication du Harley-Seal muy bon.)

Answer 2

Certains langages exposent de manière portative l'opération de manière à ce que peut utiliser un support matériel efficace s'il est disponible, sinon une bibliothèque de secours qui, on l'espère, sera décente.

Par exemple (d'après un tableau par langue ):

• Le C++ a std::bitset<>::count() ou C++20 std::popcount(T x)
• Java a java.lang.Integer.bitCount() (également pour Long ou BigInteger)
• C# a System.Numerics.BitOperations.PopCount()
• Python a int.bit_count() (depuis 3.10)

Cependant, tous les compilateurs et bibliothèques ne parviennent pas à utiliser le support HW lorsqu'il est disponible. (Notamment MSVC, même avec des options qui rendent std::popcount inline comme x86 popcnt, son std::bitset::count utilise toujours une table de consultation. Nous espérons que cela changera dans les prochaines versions).

Pensez également aux fonctions intégrées de votre compilateur lorsque le langage portable ne dispose pas de cette opération de base sur les bits. Dans le GNU C par exemple :

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

Dans le pire des cas (pas de support HW à une seule instruction), le compilateur génèrera un appel à une fonction (qui dans le GCC actuel utilise un shift/and bit-hack comme cette réponse (du moins pour x86). Dans le meilleur des cas, le compilateur émettra une instruction cpu pour faire le travail. (Tout comme une * o / opérateur - GCC utilisera une instruction matérielle de multiplication ou de division si elle est disponible, sinon il appellera une fonction d'aide libgcc). Ou encore mieux, si l'opérande est une constante du temps de compilation après inlining, il peut faire une propagation constante pour obtenir un résultat popcount constant du temps de compilation.

Les buildins GCC fonctionnent même sur plusieurs plateformes. Popcount est presque devenu courant dans l'architecture x86, il est donc logique de commencer à utiliser le buildin maintenant afin que vous puissiez recompiler pour le laisser mettre en ligne une instruction matérielle lorsque vous compilez avec -mpopcnt ou quelque chose qui l'inclut (par ex. https://godbolt.org/z/Ma5e5a ). D'autres architectures disposent du popcount depuis des années, mais dans le monde x86, il existe encore d'anciens Core 2 et d'autres processeurs AMD similaires en service.

---

Sur x86, vous pouvez indiquer au compilateur qu'il peut supposer le support de popcnt l'instruction avec -mpopcnt (également sous-entendu par -msse4.2 ). Voir Options GCC x86 . -march=nehalem -mtune=skylake (ou -march= quel que soit le processeur que vous voulez que votre code prenne en charge et pour lequel il doit être réglé) pourrait être un bon choix. L'exécution du binaire résultant sur un ancien processeur entraînera un défaut d'instruction illégale.

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

MSVC fournit un intrinsèque pour le x86 popcnt instruction mais, contrairement à gcc, il s'agit d'une instruction intrinsèque pour le matériel et elle nécessite un support matériel.

---

Utilisation de std::bitset<>::count() au lieu d'un

En théorie, tout compilateur qui sait comment compter les popcounts efficacement pour le CPU cible devrait exposer cette fonctionnalité à travers ISO C++. std::bitset<> . En pratique, il est préférable d'utiliser 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 ne disposent pas d'une fonction std::bitset qui en tire parti lorsqu'il est disponible. Par exemple, MSVC n'a aucun moyen d'activer la fonction popcnt au moment de la compilation, et c'est std::bitset<>::count utilise toujours une consultation de table même avec /Ox /arch:AVX (ce qui implique SSE4.2, qui à son tour implique la fonctionnalité popcnt) (Mise à jour : voir ci-dessous ; cette fait obtenir le C++20 de MSVC std::popcount pour utiliser x86 popcnt mais pas son bitset<>::count. MSVC pourrait corriger cela en mettant à jour les en-têtes de sa bibliothèque standard pour utiliser std::popcount lorsqu'il est disponible).

Mais au moins, vous obtenez quelque chose de portable qui fonctionne partout, et avec gcc/clang et 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, icc, et MSVC sur l'explorateur de 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        # unnecessary 64-bit operand size
    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 du tout spécifique à x86 ou à GNU, mais ne se compile bien qu'avec gcc/clang/icc, du moins lorsqu'elle vise x86 (y compris x86-64).

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

C++20 a std::popcount(T)

Les en-têtes actuels de libstdc++ le définissent malheureusement avec un cas spécial if(x==0) return 0; au début, ce que clang n'optimise pas lors de la compilation pour x86 :

#include <bit>
int bar(unsigned x) {
    return std::popcount(x);
}

clang 11.0.1 -O3 -std=gnu++20 -march=nehalem ( https://godbolt.org/z/arMe5a )

# clang 11
    bar(unsigned int):                                # @bar(unsigned int)
        popcnt  eax, edi
        cmove   eax, edi         # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
        ret

Mais GCC compile bien :

# gcc 10
        xor     eax, eax         # break false dependency on Intel SnB-family before Ice Lake.
        popcnt  eax, edi
        ret

Même MSVC s'en sort bien, tant que vous utilisez -arch:AVX ou plus (et activer C++20 avec -std:c++latest ). https://godbolt.org/z/7K4Gef

int bar(unsigned int) PROC                                 ; bar, COMDAT
        popcnt  eax, ecx
        ret     0
int bar(unsigned int) ENDP                                 ; bar

Answer 3

À 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 très bien vouloir la solution la plus rapide ou la plus intelligente, que certains ont déjà fournie, mais je préfère toujours la lisibilité à l'intelligence.

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 rapidité (et en supposant que vous le documentez bien pour aider vos successeurs), vous pouvez utiliser une table de consultation :

// 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 qu'elles reposent sur des tailles de type de données spécifiques, elles ne sont pas vraiment portables. Mais, comme de nombreuses optimisations de performances ne sont pas portables de toute façon, ce n'est pas forcément un problème. Si vous voulez la portabilité, je m'en tiendrais à la solution lisible.

Answer 4

La méthode de Brian Kernighan passe par autant d'itérations qu'il y a de bits activés. Ainsi, si nous avons un mot de 32 bits dont seul le bit de poids fort est activé, il ne passera qu'une seule fois dans la boucle.

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

long count_bits(long n) {     
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set
  return c;
}

Notez qu'il s'agit d'une question utilisée lors des entretiens. L'interviewer ajoutera la mise en garde suivante : vous avez une "mémoire infinie". Dans ce cas, vous créez essentiellement un tableau de taille 2 32 et remplissez les comptes de bits pour les nombres à chaque emplacement. Alors, cette fonction devient O(1).

Answer 5

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écution en ~20 et quelques instructions (dépendant de l'architecture), pas de branchement.

Le plaisir du hacker est délicieux ! Vivement recommandé.