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)
{
...
}
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).
donc la réponse est "ça dépend". le nombre de bits à 1 ne sera pas forcément le même dans toutes les représentations des entiers signés.
(-1 sur 32 bits, 32 bits à 1 en complément à 2, 2 bits à 1 en signe+mantisse).
-- Le travail n'est pas une bonne chose. Si ça l'était, les riches l'auraient accaparé
Antoine Leca
En news:, zombie va escriure:
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.
Sans compter le cas où les entiers sont en signe+magnitude... :-)
Ce code est surtout intéressant parce qu'en assembleur i386, l'opération -(x < y) se résume à l'instruction SETL E?X et donc la formule donne un code extrêmement compact. Comme dit l'auteur, cette formule « peut » être avantageuse sur l'évidente utilisation de l'opérateur ?:, ce que l'on peut aussi comprendre comme quoi elle ne l'est pas toujours...
Mais l'overflow n'existe que pour les flottants, non ?
Non. En C, le débordement _peut_ exister pour les flottants, et _peut_ exister pour les opérations entières signées. Ni l'une ni l'autre des deux options sont obligatoires, et elles n'ont pas à être systématiques (peut le faire une fois sur deux, par exemple ; ou selon les types mis en ½uvre).
Si x et y sont des unsigned int, le calcul se fait modulo 2^32,
... modulo UINT_MAX+1 pour être précis.
Antoine
En news:0175d2e0-413f-4c15-a41d-f4e385b5f7df@e53g2000hsa.googlegroups.com,
zombie va escriure:
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.
Sans compter le cas où les entiers sont en signe+magnitude... :-)
Ce code est surtout intéressant parce qu'en assembleur i386,
l'opération -(x < y) se résume à l'instruction
SETL E?X
et donc la formule donne un code extrêmement compact.
Comme dit l'auteur, cette formule « peut » être avantageuse sur l'évidente
utilisation de l'opérateur ?:, ce que l'on peut aussi comprendre comme quoi
elle ne l'est pas toujours...
Mais l'overflow n'existe que pour les flottants, non ?
Non. En C, le débordement _peut_ exister pour les flottants, et _peut_
exister pour les opérations entières signées.
Ni l'une ni l'autre des deux options sont obligatoires, et elles n'ont pas à
être systématiques (peut le faire une fois sur deux, par exemple ; ou selon
les types mis en ½uvre).
Si x et y sont des unsigned int, le calcul se fait modulo 2^32,
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.
Sans compter le cas où les entiers sont en signe+magnitude... :-)
Ce code est surtout intéressant parce qu'en assembleur i386, l'opération -(x < y) se résume à l'instruction SETL E?X et donc la formule donne un code extrêmement compact. Comme dit l'auteur, cette formule « peut » être avantageuse sur l'évidente utilisation de l'opérateur ?:, ce que l'on peut aussi comprendre comme quoi elle ne l'est pas toujours...
Mais l'overflow n'existe que pour les flottants, non ?
Non. En C, le débordement _peut_ exister pour les flottants, et _peut_ exister pour les opérations entières signées. Ni l'une ni l'autre des deux options sont obligatoires, et elles n'ont pas à être systématiques (peut le faire une fois sur deux, par exemple ; ou selon les types mis en ½uvre).
Si x et y sont des unsigned int, le calcul se fait modulo 2^32,
... modulo UINT_MAX+1 pour être précis.
Antoine
Sleipnir
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
Qui dit mieux ?
"zombie" a écrit dans le message de news: 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) { ... }
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien"
décalage de bit vers la droite
etc et tant que le nombre n'est pas egal à 0...
Qui dit mieux ?
"zombie" <klx@tele2.fr> a écrit dans le message de
news:4ecf4ad5-b733-4512-b94a-12a32d430bd1@d77g2000hsb.googlegroups.com...
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)
{
...
}
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
Qui dit mieux ?
"zombie" a écrit dans le message de news: 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) { ... }
Jean-marc
Sleipnir wrote:
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n) { int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; } return count ; }
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut dans ce thread: http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul proportionnel au nombre de bits du nombre, alors que d'autres ont un temps de calcul proportionnel au nombre de 0 ou de 1, voire (beaucoup) moins pour les méthodes précalculées. On peut faire de 1 à 20 fois plus rapide en fonction des options de compil.
-- (jean_marc_n2)
Sleipnir wrote:
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien"
décalage de bit vers la droite
etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n)
{
int count=0;
while (n)
{
count += n & 0x1u ;
n >>= 1 ;
}
return count ;
}
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut
dans ce thread:
http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul
proportionnel au nombre de bits du nombre, alors que d'autres ont un
temps de calcul proportionnel au nombre de 0 ou de 1, voire
(beaucoup) moins pour les méthodes précalculées. On peut faire
de 1 à 20 fois plus rapide en fonction des options de compil.
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n) { int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; } return count ; }
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut dans ce thread: http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul proportionnel au nombre de bits du nombre, alors que d'autres ont un temps de calcul proportionnel au nombre de 0 ou de 1, voire (beaucoup) moins pour les méthodes précalculées. On peut faire de 1 à 20 fois plus rapide en fonction des options de compil.
-- (jean_marc_n2)
Sleipnir
bon ben... je prends lol =)
et oui, o(n)... c'est carrément pas le top lol
"Jean-marc" a écrit dans le message de news:48877595$0$2859$
Sleipnir wrote:
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n) { int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; } return count ; }
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut dans ce thread: http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul proportionnel au nombre de bits du nombre, alors que d'autres ont un temps de calcul proportionnel au nombre de 0 ou de 1, voire (beaucoup) moins pour les méthodes précalculées. On peut faire de 1 à 20 fois plus rapide en fonction des options de compil.
-- (jean_marc_n2)
bon ben... je prends lol =)
et oui, o(n)... c'est carrément pas le top lol
"Jean-marc" <jm@nowhere.invalid> a écrit dans le message de
news:48877595$0$2859$ba620e4c@news.skynet.be...
Sleipnir wrote:
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien"
décalage de bit vers la droite
etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n)
{
int count=0;
while (n)
{
count += n & 0x1u ;
n >>= 1 ;
}
return count ;
}
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut
dans ce thread:
http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul
proportionnel au nombre de bits du nombre, alors que d'autres ont un
temps de calcul proportionnel au nombre de 0 ou de 1, voire
(beaucoup) moins pour les méthodes précalculées. On peut faire
de 1 à 20 fois plus rapide en fonction des options de compil.
"Jean-marc" a écrit dans le message de news:48877595$0$2859$
Sleipnir wrote:
ben le plus simple que je vois c'est :
un test "le nombre est impair? si oui, +1 sinon alors rien" décalage de bit vers la droite etc et tant que le nombre n'est pas egal à 0...
C'est la méthode classique par itération:
int bitcount (unsigned int n) { int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; } return count ; }
Qui dit mieux ?
Des tas d'autres algorithmes décrits sur la page indiquée plus haut dans ce thread: http://infolab.stanford.edu/~manku/bitcount/bitcount.html
La méthode que tu proposes fonctionne bien mais à un temps de calcul proportionnel au nombre de bits du nombre, alors que d'autres ont un temps de calcul proportionnel au nombre de 0 ou de 1, voire (beaucoup) moins pour les méthodes précalculées. On peut faire de 1 à 20 fois plus rapide en fonction des options de compil.
