Compter les bits à l’état haut dans un nombre est un problème que l’on rencontre parfois, comme quand on veut évaluer la consommation d’un afficheur (combien de segments éclairés à la fois).
Il y a plusieurs manières de mener ce calcul de la manière la plus naïve à la plus astucieuse. Je vous les propose ici.
La force brute (le côté obscure)
C’est la méthode la plus naïve qui consiste à tester la parité d’un nombre et de le diviser par deux, on va ainsi tester tous les bits du nombre (notez qu’avec cette méthode, je ne fais aucune hypothèse sur la représentation des nombres entiers) :
unsigned compter_les_bits(const unsigned long& nombre)
{
auto n = nombre;
unsigned compte = 0;
while ( n ) {
compte += (n % 2); // test de parité
n /= 2; // décalage à droite et suppression du bit de poids le plus faible
}
return compte;
}
Le côté clair de la force
Pour ceux qui aiment ça, on peut transformer la boucle itérative (while) par un appel récursif, mais à ce stade, je ne suis pas sûr que ça apporte de la lisibilité ou de la performance au code. Et comme je suis un peu taquin en période de confinement, je l’ai posée sur une seule ligne :
unsigned compter_les_bits(const unsigned long& nombre)
{
return ( nombre ? (nombre % 2) + compter_les_bits(nombre / 2) : 0 );
}
La version du Maître, dit « Algorithme de Brian Kernighan »
(j’aimerais trouver une source originelle de cet algo, mais sans succès jusque là)
L’algorithme est basé sur le constat que l’écriture binaire d’un nombre et de son entier naturel précédent (n – 1) sont complémentaires jusqu’au dernier bit à 1 en allant du bit de poids le plus faible et en remontant les poids, cela en raison de la propagation de la retenue dans une soustraction binaire. Un exemple sera bien plus clair :
10 = 1010b9 = 1001b8 = 1000b7 = 0111b- etc.
Donc si l’on applique un ET binaire entre un nombre et ce même nombre ôté de 1, on obtient un nombre auquel on peut appliquer la même méthode pour en compter les bits à 1, jusqu’à sa nullité.
L’intérêt de cet algorithme est qu’il limite le nombre d’itérations au nombre de bits à 1 et que le comptage est trivial puisqu’il s’effectue sans test.
unsigned compter_les_bits(const unsigned long& nombre)
{
auto n = nombre;
unsigned compte = 0;
while ( n ) {
n &= (n - 1);
++compte;
}
return compte;
}
Si vous aimez l’instruction for pour sa compacité, cela peut donner :
unsigned compter_les_bits(const unsigned long& nombre)
{
unsigned compte = 0;
for ( auto n = nombre ; n ; n &= (n - 1) ) {
++compte;
}
return compte;
}
Vous êtes arrivés jusque là, alors je vous propose une version récursive (compacte), toujours sans grand espoir de performance :
unsigned compter_les_bits(const unsigned long& nombre)
{
return ( nombre ? 1 + compter_les_bits(n & (n - 1)) : 0 );
}
Performance
J’ai fait quelques tests de performance sur ces 5 algorithmes et leur beauté n’est pas en relation avec leur vitesse d’exécution.
Le plus rapide est bien l’algorithme de Kernighan dans sa version boucle, avec un très léger avantage pour la boucle for mais qui se perd dans le bruit statistique de la mesure.
La version récursive est naturellement deux fois plus lente du fait des appels de fonction et de la gestion de la pile.
L’algorithme naïf est lui 1,5 fois plus lent que l’algorithme de Kernighan dans sa version boucle alors que la version récursive est elle, 3 fois plus lente que la référence.
Conclusion
On le savait déjà en informatique, il est contre-productif de réinventer la roue ; il faut utiliser des algorithmes scientifiquement éprouvés.
Conclusion personnelle
Les tests nombre > 0 et nombre != 0, voir (nombre) n’ont pas la même performance et l’optimiseur du compilateur n’est pas capable de remplacer l’un par l’autre.
Pour tester la non-nullité d’un nombre, il faut utiliser (nombre).