Comptage de bits en C similaire au bidouillage de bits

Je dois créer un compteur n’impliquant pas de boucles (uniquement des opérations sur bits) et n’utilisant pas de grandes constantes

int x = 0xFFFFFFFF; x += (~((x >> 1) & 0x55555555)+1); x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); x = (((x >> 4) + x) & 0x0F0F0F0F); x += (x >> 8); x += (x >> 16); return(x & 0x0000003F); 

Je l’ai trouvé sur des bidouilles, mais la plus grande constante que je puisse utiliser est 0xFF … Je ne sais pas comment faire cela autrement.

Merci les gars.

Vous pouvez par exemple utiliser un tableau constant COUNTS[16] qui correspond au nombre de bits définis dans la représentation binary de nombres compris entre 0 et 15. Ensuite:

 static inline int byte_count (int x) { static const int COUNTS[16] = { 0, 1, 1, 2, 1, /* fill in the rest manually */ }; return COUNTS[x & 15] + COUNTS[x >> 4]; } int count(int x) { return byte_count(x >> 24) + byte_count((x >> 16) & 255) + byte_count((x >> 8) & 255) + byte_count(x & 255); } 

Pas de boucles et pas de constantes supérieures à 255.

En utilisant votre algorithme:

 int x = 0xFF; x |= (x << 8); // x = 0xFFFF x |= (x << 16); // x = 0xFFFFFFFF 

et ensuite le rest du code - à condition que cela fonctionne.

Solution récursive:

 int foo ( int x ) { if ( x == 0 ) return 0; return (x & 1) + foo ( x/2 ); } 

votre question est déjà répondu ici

 int NumberOfSetBits(int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; }