Question d'algorithmique basique. Quelle est la fonction la plus
efficace que vous connaissez en C pour compter le nombres de bits =E0 1
dans un "unsigned int" (entier non sign=E9 cod=E9 sur 4 octets, en
g=E9n=E9ral) ?
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)
{
...
}
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) { ... }
-- Éric Lévénez -- <http://www.levenez.com/> Unix is not only an OS, it's a way of life.
Le 08/07/08 10:05, dans
<4ecf4ad5-b733-4512-b94a-12a32d430bd1@d77g2000hsb.googlegroups.com>,
« zombie » <klx@tele2.fr> a écrit :
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)
{
...
}
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) { ... }
-- Éric Lévénez -- <http://www.levenez.com/> Unix is not only an OS, it's a way of life.
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; }
Eric Levenez a écrit :
Le 08/07/08 10:05, dans , « zombie » a écrit :
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) { ... }
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
<4ecf4ad5-b733-4512-b94a-12a32d430bd1@d77g2000hsb.googlegroups.com>,
« zombie » <klx@tele2.fr> a écrit :
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)
{
...
}
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 » a écrit :
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) { ... }
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
Olivier Miakinen <om+ écrivait :
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...
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é
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...
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é
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...
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
Erwan David wrote:
Olivier Miakinen <om+ écrivait :
> 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
> 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
> 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
In fr.comp.lang.c, article <C498F82E.D1EC6%, Eric Levenez wrote:
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.
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.
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.
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)
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)
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
In fr.comp.lang.c, article <4874cb94$0$837$, Hugo wrote:
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.
In fr.comp.lang.c, article <4874cb94$0$837$426a74cc@news.free.fr>,
Hugo <hugo@nospam.invalid> wrote:
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.
In fr.comp.lang.c, article <4874cb94$0$837$, Hugo wrote:
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.
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.
> 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é).
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
In fr.comp.lang.c, article , zombie wrote:
> 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).
In fr.comp.lang.c, article <0175d2e0-413f-4c15-a41d-f4e385b5f7df@e53g2000hsa.googlegroups.com>,
zombie <klx@tele2.fr> wrote:
> 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).
> 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).
