calculer le nombre de bits mis en octets

Pour un octet de données, la façon optimale en considérant à la fois la vitesse et la consommation de mémoire:

uint8_t count_ones (uint8_t byte)
{
  static const uint8_t NIBBLE_LOOKUP [16] =
  {
    0, 1, 1, 2, 1, 2, 2, 3, 
    1, 2, 2, 3, 2, 3, 3, 4
  };


  return NIBBLE_LOOKUP[byte & 0x0F] + NIBBLE_LOOKUP[byte >> 4];
}

L'appel de cette fonction à partir d'une boucle for doit produire tout un programme efficace sur la plupart des systèmes. Et il est très générique.

Pour juste un seul octet de la valeur, de la façon la plus rapide est de stocker la réponse dans un 256 tableau d'octets que vous avez indice de la valeur. Par exemple, bits_set[] = {0, 1, 1, 2, ...

La réponse habituelle pour le "moyen le plus rapide pour faire bitcount" est "de rechercher les octets dans un tableau". Ce genre de travaux pour les octets, mais vous payez un réel accès à la mémoire.
Si vous ne le faire une fois de temps en temps, il est probablement le plus rapide, mais alors vous n'avez pas besoin de la manière la plus rapide si vous ne le faites qu'une fois de temps en temps.

Si vous le faites, vous êtes mieux de dosage jusqu'octets en mots ou doublewords, et de faire un rapide bitcount les opérations sur ces. Ceux-ci tendent à être de la pure arithmétique, puisque vous ne pouvez pas réaliste de recherche d'une valeur 32 bits dans un tableau pour obtenir son bitcount. Au lieu de cela vous combiner les valeurs de décalage et de masquage de manière astucieuse.

Une grande source de trucs astucieux pour le faire, c'est Peu Hacks.

Ici, c'est le régime qui y sont publiés pour le comptage de bits en 32 bits des mots dans C:

 unsigned int v; //count bits set in this (32-bit value)
 unsigned int c; //store the total here

 v = v - ((v >> 1) & 0x55555555);                    //reuse input as temporary
 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     //temp
 c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; //count

#include <iostream>
#include <climits> //for CHAR_BIT (most likely to be 8)
#include <cstring> //for memset
#include <new> 
static const int DUMMY = -1;
//first approch : activate the O(8) function in first get try... after that its O(1);
class bitsInByteflyLUT
{
typedef unsigned char byte;
public:
bitsInByteflyLUT();     //CTOR - throws std::bad_alloc
~bitsInByteflyLUT();    //DTOR
int Get_bitsInByte(byte _byte);     
private:
//CLASS DATA
int*    flyLUT;
//PRIVATE FUNCTIONS
int bitsInByte(byte _byte);
//O(8) for finding how many bits are ON in a byte.
//answer can be between 0 to CHAR_BIT.
bitsInByteflyLUT(const bitsInByteflyLUT & _class); //COPY CTOR - forbidden
const bitsInByteflyLUT & operator= (const bitsInByteflyLUT& _class);
//ASSIGN OPERATOR - forbidden
};
bitsInByteflyLUT::bitsInByteflyLUT()
{
size_t nIndexes = 1 << CHAR_BIT;
try
{
flyLUT =  new int[nIndexes];
}
catch (std::bad_alloc& ba)
{
throw;
}
memset(flyLUT, DUMMY, sizeof(int)*nIndexes);
}
bitsInByteflyLUT::~bitsInByteflyLUT()
{
delete[] flyLUT;
}
int bitsInByteflyLUT::Get_bitsInByte(byte _byte)
{
if (flyLUT[_byte] == DUMMY) //if its first time we try to get answer for this char.
{
flyLUT[_byte] = bitsInByte(_byte); //O(8)
}
return flyLUT[_byte]; //O(1) 
}
int bitsInByteflyLUT::bitsInByte(byte _byte)
{   
byte nBits = CHAR_BIT;
byte counter = 0;
byte mask = 1;
while(nBits--)
{
if(mask & _byte)
{
++counter;
}
mask <<= 1;
}
return counter;
}
int main ()
{
using std::cout;
using std::endl;
bitsInByteflyLUT flut;
for (unsigned int i = 0; i < (1 << CHAR_BIT); i += 1)
{   
cout << i << " " << flut.Get_bitsInByte(i) << endl;
}
return 0;
}