LeGreg | nraynaud a écrit :
Justement, ça m'a l'air plus facile de trouver des nombres parfait qu'une utilisation.
|
Je suis d'accord que le programme sur les nombres
parfaits est un exemple un peu pourri.
(meme si trouver une methode algorithmique
qui permette de battre le record du plus
grand nombre parfait peut avoir un interet theorique
mais ca depassera le cadre de ce forum).
Recemment en entretien d'embauche quelqu'un m'a
demandé: quelle est la methode la plus rapide pour
avoir le nombre de bits à un d'un int.
Il y a principalement deux méthodes et laquelle est
la plus rapide dépendra principalement du nombre
de bits mis et de considérations externes à l'algorithmique
du programme (cache miss).
Première méthode:
Code :
- int c = 0;
- while (i!=0)
- {
- i = (i-1)~i;
- c++;
- }
|
deuxieme méthode:
Code :
- static const char lut[]= {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,/*..*/,8};
- int c = lut[i&0xFF];
- c += lut[(i&0xFF00)>>8];
- c += lut[(i&0xFF0000)>>16];
- c += lut[(i&0xFF000000)>>24];
|
Cette derniere methode est valide
car le but de ces fonctions n'est pas de
determiner le nombre de bits mis
des nombres entiers (qui est deja connu)
mais simplement d'en obtenir rapidement
une valeur numérique utilisable dans un
programme.
LeGreg |
