Number of 1 Bits

+10

On vous donne un entier non négatif n. Écrivez n en binaire et renvoyez le nombre de ses chiffres qui sont des 1. Ce compte est également appelé le nombre de bits à 1, le nombre de bits à 1 ou le poids de Hamming. Par exemple, 6 s’écrit 110 en binaire, il a donc deux bits à 1.

Fonction

hammingWeight(n: integer) → integer

ninteger: un entier non négatif qui tient dans un int signé sur 32 bits
Renvoieinteger: le nombre de chiffres 1 dans la représentation binaire de n

Contraintes

0 ≤ n ≤ 2³¹-1

Exemples

Entrée: n = 11
Sortie: 3
Explication: 11 s’écrit 1011 en binaire, ce qui correspond à 8 + 2 + 1. Trois de ses quatre chiffres binaires sont des 1, donc la réponse est 3.

Entrée: n = 128
Sortie: 1
Explication: 128 est 2^7, écrit 10000000 : un seul 1 suivi de zéros, donc la réponse est 1.

Pour aller plus loin

Si cette fonction était exécutée des millions de fois, comment pourriez-vous compter les bits d’un nombre de 32 bits avec quatre recherches dans une table de 256 comptes précalculés ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Parcourez les chiffres binaires de n sans construire de chaîne. Lire le dernier bit et le décaler prend une étape par chiffre binaire, jusqu’à 31. Effacer le bit 1 le plus bas avec n & (n-1) prend une étape par bit 1, exactement autant que la réponse.

Vérifiez le dernier bit et décalez vers la droite

Intuition

n & 1 est le dernier chiffre binaire de n : 1 lorsque n est impair, 0 lorsqu’il est pair. Ajoutez-le au décompte. Ensuite, n >> 1 supprime ce chiffre et place le suivant à la dernière position ; pour un nombre non négatif, cela revient à le diviser par 2 en arrondissant à l’inférieur. Pour 11, 1011, les derniers bits lus sont 1, 1, 0 et 1 tandis que n diminue jusqu’à 0 : trois bits à 1.

La boucle s’arrête lorsque n vaut 0 ; elle ne parcourt donc jamais les zéros non significatifs : environ log2(n) étapes, 8 pour 128 et au maximum 31. Elle ne stocke que n et le décompte.

Algorithme

Commencez un compteur à 0.
Tant que n est supérieur à 0, ajoutez n & 1 au compteur.
Décalez n vers la droite d'un bit.
Lorsque n atteint 0, renvoyez le compteur.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

Effacer le bit à 1 de poids faible avec n & (n-1)

Intuition

Soustraire 1 transforme le bit 1 de poids le plus faible en 0 et chaque 0 situé en dessous en 1, tout en laissant les bits du dessus inchangés. Ainsi, n & (n-1) conserve les bits de poids supérieur et efface le bit 1 de poids le plus faible : 12 est 1100, 11 est 1011, et 1100 & 1011 donne 1000.

Chaque étape supprime exactement un bit 1 ; le nombre d’étapes nécessaires pour que n atteigne 0 est donc la réponse. 128 nécessite 1 étape au lieu de 8, même si 2^31-1 en nécessite toujours 31. Lua 5.1 ne possède pas d’opérateurs binaires ; sa version trouve donc le bit 1 de poids le plus faible en divisant par deux, puis le soustrait ; la boucle s’exécute toujours une fois par bit 1.

Algorithme

Initialisez un compteur à 0.
Tant que n n’est pas égal à 0, remplacez n par n & (n-1).
Ajoutez 1 au compteur après chaque remplacement.
Retournez le compteur.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Pièges et cas limites

Boucler tant que n > 1. La boucle s’arrête avant le dernier bit 1 et renvoie 0 pour n = 1.
Diviser avec un nombre à virgule flottante. En JavaScript, Lua et R, 11 / 2 vaut 5.5 et les restes qui suivent sont des fractions. Arrondissez à l’entier inférieur avec Math.floor, math.floor ou %/%, ou effectuez plutôt un décalage.
Écrire n & 1 en Lua 5.1. Ce langage n’a pas d’opérateurs binaires, donc le code ne compile pas ; utilisez n % 2 et math.floor(n / 2).

Questions fréquentes3

Quelle est la complexité temporelle du nombre de bits à 1 ?

La boucle de décalage s’exécute une fois par chiffre binaire : O(log n), au plus 31 étapes ici. La boucle n & (n-1) s’exécute une fois par bit à 1 : O(k), où k est la réponse. Les deux utilisent un espace supplémentaire de O(1).

Existe-t-il une fonction intégrée qui compte les bits à 1 ?

La plupart des langages en possèdent une, souvent prise en charge par une seule instruction du processeur : Integer.bitCount en Java, __builtin_popcount dans GCC, bits.OnesCount en Go, count_ones en Rust et int.bit_count dans Python 3.10 et les versions ultérieures. Lors d’un entretien, écrivez la boucle et mentionnez la fonction intégrée.

Quelle est la différence entre le poids de Hamming et la distance de Hamming ?

Le poids de Hamming d’un nombre correspond au nombre de ses chiffres binaires égaux à 1, et c’est ce que renvoie ce problème. La distance de Hamming entre deux nombres correspond au nombre de positions de bits où ils diffèrent : compte les bits à 1 de a ^ b, car XOR met à 1 exactement les positions où ils diffèrent.

def hammingWeight(n):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

n = 11

Résultat attendu