Bit Twiddling in C – Compter les bits

Je veux compter les bits qui sont placés dans un vecteur de bits extrêmement grand (c.-à-d. 100 000 bits).

Ce que je fais actuellement est d’utiliser un pointeur sur char (c’est-à-dire char * cPtr) pour pointer au début du tableau de bits. J’ai alors:

1. look at each element of the array (ie cPtr[x]), 2. convert it to an integer (ie (int) cPtr[x]) 3. use a 256 element look-up table to see how many bits are set in the given byte (ie cPtr[x]). 

Il me semble que si j’utilise plutôt un pointeur int court (c’est-à-dire short int * sPtr), il ne me faudra plus que la moitié du nombre de recherches, mais avec une table de correspondance d’éléments 65534, qui aura son propre coût en utilisation de la mémoire.

Je me demande quel est le nombre optimal de bits à examiner à chaque fois. De plus, si ce nombre n’est pas de la taille d’un type prédéfini, comment puis-je consulter mon vecteur de bits et définir un pointeur sur N’IMPORTE QUEL nombre de bits arbitraires au-delà de l’emplacement de départ du tableau de bits.

Je sais qu’il existe d’autres moyens de compter les bits, mais je souhaite pour le moment être certain de pouvoir optimiser cette méthode avant de procéder à des comparaisons avec d’autres méthodes.

Je me demande quel est le nombre optimal de bits à examiner à chaque fois

La seule façon de le savoir est de tester. Voir cette question pour une discussion sur le moyen le plus rapide de compter 32 bits à la fois.

De plus, si ce nombre n’est pas de la taille d’un type prédéfini, comment puis-je consulter mon vecteur de bits et définir un pointeur sur N’IMPORTE QUEL nombre de bits arbitraires au-delà de l’emplacement de départ du tableau de bits.

Vous ne pouvez pas définir un pointeur sur un bit arbitraire. La plupart des machines ont un adressage par octet, certaines peuvent uniquement adresser des mots.

Vous pouvez construire un mot commençant par un bit arbitraire comme ceci:

 long wordAtBit(int32_t* array, size_t bit) { size_t idx = bit>>5; long word = array[idx] >> (bit&31); return word | (array[idx+1] << (32 - (bit&31)); } 

Vous pouvez le compter en utilisant l’opération bit à bit:

 char c = cPtr[x]; int num = ((c & 0x01) >> 0) + ((c & 0x02) >> 1) + ((c & 0x04) >> 2) + ((c & 0x08) >> 3) + ((c & 0x10) >> 4) + ((c & 0x20) >> 5) + ((c & 0x40) >> 6) + ((c & 0x80) >> 7); 

Cela peut sembler un peu long, mais cela ne nécessite pas beaucoup de temps en mémoire, donc après tout, cela semble assez bon marché pour moi.

Vous pouvez même le rendre moins cher en lisant un int à chaque fois, mais vous devrez probablement régler un problème d’alignement.

Cela devrait être assez rapide (tiré de Wikipedia ):

 static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 }; static int popcount(uint32 i) { return (wordbits[i&0xFFFF] + wordbits[i>>16]); } 

De cette façon, vous pouvez vérifier 32 bits par itération.

Je suis un peu en retard pour le parti, mais il existe des approches beaucoup plus rapides que celles suggérées jusqu’à présent. La raison en est que de nombreuses architectures modernes proposent des instructions matérielles pour compter le nombre de bits de différentes manières (zéros de début, de début, de fin ou de nombre, en comptant le nombre de bits défini à 1, etc.). Compter le nombre de bits défini sur 1 s’appelle le poids de Hamming, ou encore dénombrement de la population, ou simplement popcount.

En fait, les processeurs x86 ont une instruction POPCNT dans le jeu d’instructions SSE4.2. La toute dernière architecture de processeur d’Intel (surnommée Haswell) offre un support matériel supplémentaire pour la manipulation de bits avec les extensions BMI1 et BMI2 – peut-être y a-t-il autre chose à utiliser!