Discussion :

[hack-77]

salut à tous

l'exercice
quelle est la meilleure méthode pour calculer les unités dans un numéro composé de 32bits sans utiliser une boucle
par exemple
10 contient 2 unites parce qu'il s'écrit comme ça 1010...
******
solution
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
est-ce que quelqu'un peut m'expliquer ça!!!!!????

[khayyam90]

Bien le bonjour,

je ne comprends pas bien ce que tu veux faire.

à partir d'un nombre codé sur 32 bits tu veux séparer tous les digits (en base 10) ?

[titoine1978]

Ca ne serait pas plutot compter le nombre de 1 qu'il y a dans la representation binaire d'un entier 32 bit ?

[Matthieu Brucher]

Merci de mettre un titre plus clair à l'avenir.

[Sivrît]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

On travaille sur des groupes de 2 bits. Pour chaque groupe on soustrait à sa valeur le bit de poid fort.
En gros (mieux vaut le faire pour constater que ça marche) :
10=>01
00=>00
01=>01
11=>10
Et le résultat est que chaque groupe contient en binaire le nombre de 1 qu'il y avait à l'origine sur ce groupe.

La suite ne consiste plus qu'à sommer les résultats 2 à 2.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));

Sur des groupes de 4 bits on additionne les deux bits de poids fort aux deux bits de poids faible, en masquant avec "0011" pour libérer les deux bits de poids fort.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
x += (x >> 4);
x &= 0x0f0f0f0f;

Pour chaque octet on somme les 4 bits de poids fort et les 4 bits de poids faible.
Et on masque pour nettoyer la partie haute des octets.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
x += (x >> 8);

Puis on somme les octets 2 à 2.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
x += (x >> 16);

On somme les deux groupes de deux octets.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
return(x & 0x0000003f);

Et on masque pour enlever les débris du calcul.


Ce code devrait illustrer le commandement "Ton code tu commentera" dans la bible du programmeur

[10_GOTO_10]

Tiens, ça doit être l'exercice préféré d'un prof sadique, parce qu'il y a quelques temps quelqu'un a posé exactement la même question:

http://www.developpez.net/forums/showthread.php?t=63710