"Erwan David" <erwan***rail.eu.org> a écrit dans le message de news:
863amh93ub.fsf***nez-casse.depot.rail.eu.org...
> Vincent Lefevre <vincent+news***vinc17.org> écrivait :
>
>>
>> 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).

C'est sans compter les eventuels bits de parité et de padding assez courants
sur les architectures obsoletes qui implementaient les entiers en complement
à un ou signe+magnitude. Heureusement, ces curiosités historiques sont
introuvables aujourd'hui. Le langage C gagnerait en simplicité à
reconnaitre cette évolution et ranger aux oubliettes le support dans la
norme de ces trucs sans intérêt.
Mais les experts velus qui fréquentent les forums du C, en particulier
comp.lang.c et comp.std.c, défendront bec et ongles ces armes secretes qui
leur permettent de ridiculiser à loisirs les developpeurs de passage.

Quant au comptage de bits, il y a différentes solutions intéressantes sur
les pages:

http://graphics.stanford.edu/~seander/bithacks.html (avec une modeste
contribution de votre serviteur) et
http://infolab.stanford.edu/~manku/b.../bitcount.html avec des stats
comparatives.

Pour moi, la plus elegante reste :

int bitcount(unsigned int n)
{
int count = 0;
while (n) {
count++;
n &= n - 1;
}
return count;
}

L'analyse de cet algorithme est une occasion idéale de comprendre la
representation binaire des nombres.

Les alternatives plus rapides sont moins portables (code different selon la
taille des int), plus encombrantes (tableaux précalculés), voire
completement ésotériques...

Si la vitesse est vraiment critique, il faudra de toute facon faire de
vraies mesures d'efficacité, avec des données réelles, pour selectionner le
meilleur algorithme, et recommencer si les caractéristiques des données
changent ou l'architecture cible varie.

Dans ce cas, il est vraisemblable qu'une version en assembleur inline qui
utilise la bonne instruction du CPU s'il en dispose soit encore nettement
plus efficace que toutes celles qu'on a vu dans les pages de Stanford.

A moins qu'un compilateur suffisamment sioux n'ait analysé le code et
remplacé de lui-même tous ces efforts d'optimisation du source par une
implementation optimale pour l'architecture cible... je n'en ai pas encore
rencontré, mais je n'ai pas cherché activement et cela ne me semble pas bien
difficile (*).

--
Chqrlie.

(*) Oui, Jacob, c'est bien une incitation subliminale ;-)

"Pierre Maurette" <maurettepierre***wanadoo.fr> a écrit dans le message de
news: mn.253e7d885fe3dd63.79899***wanadoo.fr...
> Charlie Gordon, le 04/08/2008 a écrit :
>
> [...]
>
>> C'est sans compter les eventuels bits de parité et de padding assez
>> courants sur les architectures obsoletes qui implementaient les entiers
>> en complement à un ou signe+magnitude.
>
> Il me semble que dans ce fil, à partir du moment où on est sorti du
> problème initial de l'entier positif, on est dans une certaine ambiguïté.
> Il faut savoir, que ce soit pour afficher la représentation ou pour
> compter les bits allumés, quelle est la question:
>
> - Quelle est la représentation (ou nombre de bits allumés) pour une valeur
> numérique donnée, dans une représentation donnée et sur un nombre de bits
> donné. Ce problème se traite dans tous les langages, même ceux pour
> lesquels la représentation d'un entier en mémoire n'a pas ou peu de sens.

Tout à fait. La question initiale concernait bien le cas d'un "unsigned
int", donc d'un entier positif ou nul. Le nombre de bits a 1 de la
representation binaire d'un tel entier ne depend pas de la methode de
stockage, ni d'ailleurs ne necessite de stockage. Toutes les methodes
proposees ne s'interessent qu'à cette question. Elles varient uniquement
quant à l'algorithme choisi et la taille maximale de l'entier choisi.

> - Quelle est la représentation (ou nombre de bits allumés) réelle en
> mémoire pour telle ou telle donnée ou zone. Si la donnée est de type
> donné, par exemple un int, c'est à priori sans ambiguïté. Et encore. Si on
> veut généraliser, il faut impérativement dealer avec le boutisme. Pas pour
> compter les bits allumés, mais pour la représentation. Pour une donnée ou
> zone donnée par un pointeur et une taille, il faudra caster ce pointeur en
> unsigned char pour la représentation brute, mais peut-être en autre chose.
> Bref, il faudra là encore préciser la question. Ce genre de truc est
> accessible exclusivement j'imagine aux langages "à pointeurs".

Cette question est effectivement hors champs, et la remarque de Erwan David
suite à la digression de Vincent Lefevre nous a conduit dans le terrain
glissant des representations des nombres signés et autres curiosités
historiques supportées par le langage C. Compter les bits dans ce contexte
peut donner des résultats différents selon que l'on manipule la valeur des
nombres ou que l'on inspecte avec un pointeur adéquat (unsigned char*) leur
représentation en mémoire. Je ne pense pas que le boutisme ait d'importance
dans ce cas précis, mais déterminer exactement ce que la norme garantit,
compte tenu des différentes contraintes exprimées sur les représentations
admises est un travail d'expert non trivial. J'ai bien étudié cette
question et je suis encore perplexe. Ma conclusion est qu'il est grand
temps de supprimer ces scories de la prochaine version de la norme C.

> Les séries de truc trouvés sur internet ne répondent pas à la même
> question, sauf si on affirme une représentation des données en mémoire sur
> la plateforme cible.

Comme dit ci-dessus, les codes en question répondent à la premiere question,
avec souvent des contraintes fortes sur la taille du type unsigned int.

--
Chqrlie.