Comment compter le nombre de bits zéro dans un entier?

Question

Comment pourrais-je trouver le nombre de bits 'zéro' en C++. Supposons que j'ai un nombre entier;

int value = 276; 

Pour qui j'ai les bits 100010100, mais comment compter les zéros?

Answer 1

La façon la plus la plus naïve façon est de simplement itérer sur les bits et compter:

size_t num_zeroes = 0; 

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i) 
{ 
    if ((value & (1 << i)) == 0) 
    ++num_zeroes; 
} 

Il y a tout nombre de mieux (pour différentes valeurs de « meilleurs ») des moyens, mais cela est tout à fait clair, très laconique (code-sage), et ne nécessite pas un tas d'installation.

Un micro-optimisation qui pourrait être considéré comme une amélioration est de ne pas calculer le masque pour tester chaque bit, décalage au lieu de la valeur et toujours tester le bit le plus à droite:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1) 
{ 
    if ((value & 1) == 0) 
    ++num_zeroes; 
} 

Answer 2

loin la solution la plus évidente est une table de recherche.

/* Assuming CHAR_BITS == 8 */ 
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ }; 
int bitsInByte(unsigned char c) { return bits[c]; } 

Answer 3

Il y a un grand livre pour ce genre de choses: Hacker's Delight (oui, le nom est nul: il n'a rien à voir avec la sécurité, mais exclusivement bit bidouilles). Il fournit plusieurs algorithmes pour compter '1' bits, le meilleur peut également être trouvé here (bien que le livre a des explications que ce site ne fait pas). Une fois que vous connaissez le nombre de bits '1', soustrayez-le au nombre de bits de votre représentation de type.

Answer 4

Vous pouvez faire 32 moins the number of bits set.

Answer 5

Si vous utilisez GCC, vous pouvez essayer les fonctions intégrées:

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x) 
int __builtin_clz (unsigned int x) 

Voir GCC Documentation pour plus de détails.

Answer 6

Faites le compliment d'un, puis comptez les 1s.

count_zero_bits (x) = count_one_bits (~ x);

Implémentez le code pour compter les uns.

template< typename I > 
int count_one_bits(I i) 
{ 
    size_t numbits = 0; 
    for(; i != 0; i >>= 1) 
    { 
     numbits += i&1; 
    } 
} 

bien qu'il y ait un problème avec ma fonction si i est un nombre négatif, car >> mettra 1 bits dans le côté droit et vous obtiendrez une boucle sans terminaison. S'il existe un moyen structuré d'appliquer un type non signé qui serait idéal.

Une fois que vous avez ce alors:

template< typename I > int count_zero_bits(I i) 
{ 
    return count_one_bits(~i); 
} 

fonctionnera.

Answer 7

Kernighan way de bits de comptage mis

unsigned int v; // count the number of bits set in v 
unsigned int c; // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1; // clear the least significant bit set 
} 

peut être facilement adapté à la tâche donnée. Un certain nombre d'itérations est ici égal à un nombre de bits défini.

Je recommande également le lien ci-dessus pour diverses autres façons de résoudre ce problème et d'autres types de tâches liées aux bits. Il y a également un exemple de ligne unique d'obtention du nombre de bits implémenté dans les macros.

Answer 8

Si vous voulez l'efficacité puis il y a une bonne mise en œuvre dans le livre « Les pirates informatiques Delight »

22 branche d'instructions gratuite.

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

unsigned int count_0bits(unsigned int x) 
{ 
    return 32 - count_1bits(x); 
} 

Je vais essayer d'expliquer comment cela fonctionne. C'est un algorithme de division et de conquête.

(x >> 1) & 0x55555555 

Décale tous les bits de 1 pas vers la droite et prend le bit le moins significatif de chaque paire de bits.

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs) 

Donc, fondamentalement, vous aurez le tableau suivant de toutes les permutations de 2 bits.

1. (00 >> 1) & 01 = 00 
2. (01 >> 1) & 01 = 00 
3. (10 >> 1) & 01 = 01 
4. (11 >> 1) & 01 = 01 

x - ((x >> 1) & 0x55555555); 

Ensuite, vous soustrayez ceux-ci des paires non décalées.

1. 00 - 00 = 00 => 0 x 1 bits 
2. 01 - 00 = 01 => 1 x 1 bits 
3. 10 - 01 = 01 => 1 x 1 bits 
4. 11 - 01 = 10 => 2 x 1 bits 

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

Alors maintenant, nous avons changé chaque paire 2 bits de sorte que leur valeur est maintenant le nombre de bits de leurs 2 paires de bits d'origine correspondant ... et puis nous continuons dans la même manière avec 4 groupes de bits, 8 bits groupes, 16 groupes de bits et final 32 bits.

Si vous voulez une meilleure explication acheter le livre, il y a beaucoup de bonnes explications et discussions d'algorithmes alternatifs, etc ...

Answer 9

Selon moi, la façon la plus simple pour obtenir le nombre de bits zéro dans un esprit positif entier est le morceau de code suivant.

int get_zero_bit_count(int num) 
{ 
    int cnt = 0; 

    while(num > 0) 
     { 
      int and_num = num & 1; 

      if (and_num != num) cnt++; 

      num >>= 1; 
     } 

     return cnt; 
    } 

Ce morceau de code est facile à comprendre et est explicite. Cela fonctionne bien pour les entiers positifs.

Answer 10

Je suis surpris que personne n'a mentionné celui-ci:

int num_zero_bits = __builtin_popcount(~num); 

Cela donnera le nombre de bits à zéro dans num lorsqu'il est utilisé avec GCC.

Answer 11

L'expansion sur la réponse de ronag, que les autres utilisateurs ont mentionné conduit à des résultats erronés (son algorithme ne fonctionne que jusqu'à une valeur de x = 15), voici une version mise à jour de l'algorithme:

uint8_t count_1bits(uint32_t x) { 
    x = x - ((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 & 0x3F; 
} 

uint8_t count_0bits(uint32_t x) { 
    return 32 - count_1bits(x); 
} 

Le l'explication de la première ligne de ronag est correcte, cependant, les lignes restantes utilisent une approche différente. Dans la première ligne, à travers le décalage et la soustraction, chaque paire de 2 bits contiendra le nombre de bits qui ont été définis dans cette paire dans le nombre d'origine. Le reste des lignes regroupe récursivement ces nombres en ajoutant le lsb de chaque groupe de 2n bits au msb de cette paire décalée de n, de sorte que le groupe de 2n bits contient le nombre de bits qui a été défini dans ce groupe dans le groupe. nombre original:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number) 
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111 
= 0110 + 0111 
= 1101 

l'algorithme ci-dessus fonctionne pour 32 des nombres entiers binaires, mais peut facilement être adapté en changeant les constantes de la longueur de bit correct de sorte que le motif reste le même (par exemple 0x5555 ... = 0101. .., 0x0f0f ...= 00001111 ... etc.) et en ajoutant/supprimant les quarts de travail appropriés