comptage de bits

Le
zombie
Bonjour,

Question d'algorithmique basique. Quelle est la fonction la plus
efficace que vous connaissez en C pour compter le nombres de bits à 1
dans un "unsigned int" (entier non signé codé sur 4 octets, en
général) ?

Exemple pour 1, 2, 4, 8, 16 retour 1
pour 3, 5, 9, 17 retour 2
pour 15 (1111) retour 4
etc

unsigned int countBits (unsigned int iValue)
{

}
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Eric Levenez
Le #12841871
Le 08/07/08 10:05, dans
« zombie »
Question d'algorithmique basique. Quelle est la fonction la plus
efficace que vous connaissez en C pour compter le nombres de bits à 1
dans un "unsigned int" (entier non signé codé sur 4 octets, en
général) ?

Exemple pour 1, 2, 4, 8, 16... retour 1
pour 3, 5, 9, 17... retour 2
pour 15 (1111) retour 4
etc...

unsigned int countBits (unsigned int iValue)
{
...
}



Il y a différentes réponses ici :



--
Éric Lévénez -- Unix is not only an OS, it's a way of life.
Paris Hilton
Le #12859511
de mémoire ya le truc :

unsigned int countbits(unsigned int i) {
unsigned int setbits = 0
while (i != 0)
{
if (i % 2 == 1)
setbits++;
i /= 2;
}
return setbits;
}

Eric Levenez a écrit :
Le 08/07/08 10:05, dans
« zombie »
Question d'algorithmique basique. Quelle est la fonction la plus
efficace que vous connaissez en C pour compter le nombres de bits à 1
dans un "unsigned int" (entier non signé codé sur 4 octets, en
général) ?

Exemple pour 1, 2, 4, 8, 16... retour 1
pour 3, 5, 9, 17... retour 2
pour 15 (1111) retour 4
etc...

unsigned int countBits (unsigned int iValue)
{
...
}



Il y a différentes réponses ici :





Erwan David
Le #12859501
Paris Hilton
de mémoire ya le truc :

unsigned int countbits(unsigned int i) {
unsigned int setbits = 0
while (i != 0)
{
if (i % 2 == 1)
setbits++;
i /= 2;
}
return setbits;
}



Il va falloir que je fouille, mais il il y a une formule qui mets à 0 le
bit de poids le plus faible...


--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé
Erwan David
Le #12880931
Olivier Miakinen
Le 08/07/2008 21:08, Erwan David répondait à Paris Hilton :

de mémoire ya le truc :
[ méthode pire que la plus naïve des liens déjà donnés :
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive ]





:-D

Il va falloir que je fouille, mais il il y a une formule qui mets à 0 le
bit de poids le plus faible...



http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan



Oui c'est ça. je l'ai utilisé dans un algo de crypto qui faisait un
certain nombre de rounds de DES, avec un compteur dans un coin dont on
devait sauter les valeurs à plus de 10 bits à 1...

--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé
pasde.hcyrano.spam
Le #12881831
Erwan David
Olivier Miakinen
> Le 08/07/2008 21:08, Erwan David répondait à Paris Hilton :
>>
>>> de mémoire ya le truc :
>>> [ méthode pire que la plus naïve des liens déjà donnés :
>>> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive ]
>
> :-D
>
>> Il va falloir que je fouille, mais il il y a une formule qui mets à 0 le
>> bit de poids le plus faible...
>
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Oui c'est ça. je l'ai utilisé dans un algo de crypto qui faisait un
certain nombre de rounds de DES, avec un compteur dans un coin dont on
devait sauter les valeurs à plus de 10 bits à 1...



pour info sur le penryn tu as popcnt

sinon sur le net c'est assez simple de trouver des algo (meme wikipedia)
--
Bruno Causse
http://perso.wanadoo.fr/othello
Vincent Lefevre
Le #12882801
In fr.comp.lang.c, article Eric Levenez
Il y a différentes réponses ici :






Quelle horreur! Il y a plein de trucs non portables, sans parfois que
ce soit dit, et qui ont des chances de ne pas fonctionner en pratique
(crash, résultat incorrect...).

Par exemple, dans le minimum de deux entiers:

r = y + ((x - y) & -(x < y)); // min(x, y)

x - y peut provoquer un overflow, d'où comportement indéfini. Avec
gcc -ftrapv, ça va planter.

D'autre part, certaines optimisations pourraient mener à du code qui
ne ferait pas ce qu'on veut.

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Hugo
Le #14499341
Vincent Lefevre a écrit :




Quelle horreur! Il y a plein de trucs non portables, sans parfois que
ce soit dit, et qui ont des chances de ne pas fonctionner en pratique
(crash, résultat incorrect...).

Par exemple, dans le minimum de deux entiers:

r = y + ((x - y) & -(x < y)); // min(x, y)

x - y peut provoquer un overflow, d'où comportement indéfini. Avec
gcc -ftrapv, ça va planter.



N'hésite pas à lui faire part de tes remarques, d'autant plus que ce
site a une certaine autorité dans le domaine (cette exemple est même
celui choisi par wikipedia pour illustrer les manipulations de bits). Ça
fera avancer les choses.

Ca te donnera le droit à une bière gratuite en plus ^_^ :

To the first person to inform me of a legitimate bug in the code, I'll
pay a bounty of US$10 (by check or Paypal)



(suivi positionné)

--
Hugo
Vincent Lefevre
Le #14499331
In fr.comp.lang.c, article Hugo
N'hésite pas à lui faire part de tes remarques,



Je lui ai envoyé quelques commentaires tout à l'heure. Maintenant,
c'est vrai que cette page est bien mieux faite que ce qu'on peut
voir ailleurs, et qu'il y a des choses intéressantes.

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
zombie
Le #14499321
> Par exemple, dans le minimum de deux entiers:

r = y + ((x - y) & -(x < y)); // min(x, y)

x - y peut provoquer un overflow, d'où comportement indéfini. Avec
gcc -ftrapv, ça va planter.



Mais l'overflow n'existe que pour les flottants, non ? Si x et y sont
des unsigned int, le calcul se fait modulo 2^32, ce qui fait que la
formule reste correcte (je dirais même qu'elle exploite cette
propriété).

Merci à tous pour vos réponses, au passage.
Vincent Lefevre
Le #14552021
In fr.comp.lang.c, article zombie
> Par exemple, dans le minimum de deux entiers:
>
> r = y + ((x - y) & -(x < y)); // min(x, y)
>
> x - y peut provoquer un overflow, d'où comportement indéfini. Avec
> gcc -ftrapv, ça va planter.



Mais l'overflow n'existe que pour les flottants, non ?



Non, il peut y avoir aussi un overflow sur les entiers signés, auquel
cas, c'est du comportement indéfini (tout comme les flottants, mais en
général, pour les flottants, la norme IEEE754-1985 est supportée, plus
ou moins bien).

Si x et y sont des unsigned int, le calcul se fait modulo 2^32, ce
qui fait que la formule reste correcte (je dirais même qu'elle
exploite cette propriété).



J'ai oublié de dire que les entiers en question étaient des int
(en général, quand on parle d'entiers sans préciser, ce sont des
entiers signés).

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Publicité
Poster une réponse
Anonyme