Combien de 1 dans un entier à n bits?

Question

Un problème intéressant que j’ai rencontré aujourd’hui: quel est le moyen le plus rapide de compter le nombre de 1 dans un entier à n bits? Est-il possible de battre O (n)?

Par exemple:

42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one

Clairement, l’algorithme naïf consiste simplement à compter. Mais y a-t-il des astuces pour l'accélérer?

(Il s’agit simplement d’une question théorique; la mise en œuvre d’une telle stratégie n’apporte aucun gain de performance.)

Answer 1

Voir le fabuleux article de Twiddling Hacks .

Answer 2

Sur les processeurs x86, le moyen le plus rapide serait probablement d'utiliser le POPCNT . classe d'instructions.

Answer 3

Le moyen le plus rapide (sans utiliser de fonctions de processeur spéciales ni stocker de réponses pré-calculées) consiste à ET votre valeur avec la valeur - 1 dans une boucle jusqu'à 0. Le nombre d'itérations est le nombre de 1.

Answer 4

Si vous avez un nombre fini de bits (par exemple 32 bits), vous pouvez le précalculer, puis simplement rechercher la valeur dans un tableau.

Une méthode légèrement plus pratique consiste à effectuer cette opération pour chaque octet ou mot (ne prend que 256 octets / 64 ko), puis d'ajouter les résultats de chaque octet / mot dans la valeur

Answer 5

O (journal n) , si vous n'allez pas au-delà des mots machine et ignore le fait que chaque opération de la machine fonctionne sur n bits.

En pratique, vous devriez utiliser les fonctions de la bibliothèque au lieu de twiddler vous-même les bits, par exemple Integer.bitCount () en Java.