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




15 Answers

C'est ce qu'on appelle le « poids Hamming », «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 le popcnt de x86, sur les processeurs où il est supporté) 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 peu par cycle ( citation nécessaire ).

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 un langage particulier (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 être parallélisé pour être effectué dans plusieurs éléments vectoriels à la fois, plutôt que 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 fonctionner sur n'importe quel CPU, 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 une PSHUFB bit-parallèle SSSE3 PSHUFB d'environ un facteur 2, mais seulement si votre compilateur l'obtient correctement . Sinon SSE peut sortir significativement en avance. Les versions plus récentes du compilateur sont conscientes du problème de popcnt false dependency 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)

hamming weight

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?




À 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.




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. Connaissez aussi le paradigme Divide and Conquer . 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 nombre de 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 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 0b01100010 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, ABCD , il en résulte un nouveau nombre avec ces octets A+B+C+D B+C+D C+DD . Un nombre de 4 octets peut avoir un maximum de 32 bits, ce 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 définis dans tous les octets, et nous l'obtenons par >> 24 . Cet algorithme a été conçu pour 32 bit mots de 32 bit mais peut être facilement modifié pour 64 bit mots de 64 bit .




Si vous utilisez Java, la méthode Integer.bitCount 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 Divide and Conquer. Supposons qu'il existe un entier de 8 bits 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)
+-------------------------------+



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

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




Ce n'est pas la solution la plus rapide ou la meilleure, mais j'ai trouvé la même question sur mon chemin, et j'ai commencé à réfléchir et à réfléchir. finalement, 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, et ensuite vous réalisez la différence entre les périodes ... here you go:

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



The function you are looking for is often called the "sideways sum" or "population count" of a binary number. Knuth discusses it in pre-Fascicle 1A, pp11-12 (although there was a brief reference in Volume 2, 4.6.3-(7).)

The locus classicus is Peter Wegner's article "A Technique for Counting Ones in a Binary Computer", from the Communications of the ACM , Volume 3 (1960) Number 5, page 322 . He gives two different algorithms there, one optimized for numbers expected to be "sparse" (ie, have a small number of ones) and one for the opposite case.




What do you means with "Best algorithm"? The shorted code or the fasted code? Your code look very elegant and it has a constant execution time. The code is also very short.

But if the speed is the major factor and not the code size then I think the follow can be faster:

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

I think that this will not more faster for a 64 bit value but a 32 bit value can be faster.




if you're using C++ another option is to use 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;
}

usage would be:

// 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 )

you could of course further expand this template to use different types (even auto-detecting bit size) but I've kept it simple for clarity.

edit: forgot to mention this is good because it should work in any C++ compiler and it basically just unrolls your loop for you if a constant value is used for the bit count (in other words, I'm pretty sure it's the fastest general method you'll find)




I use the below code which is more intuitive.

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

Logic : n & (n-1) resets the last set bit of n.

PS : I know this is not O(1) solution, albeit an interesting solution.




Java JDK1.5

Integer.bitCount(n);

where n is the number whose 1's are to be counted.

check also,

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



There are many algorithm to count the set bits; but i think the best one is the faster one! You can see the detailed on this page:

Bit Twiddling Hacks

I suggest this one:

Counting bits set in 14, 24, or 32-bit words using 64-bit 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;

This method requires a 64-bit CPU with fast modulus division to be efficient. The first option takes only 3 operations; the second option takes 10; and the third option takes 15.




I always use this in Competitive Programming and it's easy to write and efficient:

#include <bits/stdc++.h>

using namespace std;

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



32-bit or not ? I just came with this method in Java after reading " cracking the coding interview " 4th edition exercice 5.5 ( chap 5: Bit Manipulation). If the least significant bit is 1 increment count , then right-shift the integer.

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

I think this one is more intuitive than the solutions with constant 0x33333333 no matter how fast they are. It depends on your definition of "best algorithm" .




Related

algorithm binary bit-manipulation hammingweight iec10967