Méthode rapide de comptage des bits non nuls dans les nombres entiers positifs

Question

J'ai besoin d'un moyen rapide pour compter le nombre de bits dans un entier en python. Ma solution actuelle est

bin(n).count("1")

Mais je me demande s'il existe un moyen plus rapide de procéder ?

Answer 1

Python 3.10 introduit int.bit_count() :

>>> n = 19
>>> bin(n)
'0b10011'
>>> n.bit_count()
3
>>> (-n).bit_count()
3

Cela équivaut fonctionnellement à bin(n).count("1") mais devrait l'être ~6 fois plus rapide . Voir aussi Numéro 29882 .

Answer 2

Pour les entiers de longueur arbitraire, bin(n).count("1") est le plus rapide que j'ai pu trouver en Python pur.

J'ai essayé d'adapter les solutions d'Óscar et d'Adam pour traiter l'entier en tranches de 64 bits et de 32 bits, respectivement. Les deux solutions étaient au moins dix fois plus lentes que bin(n).count("1") (la version 32 bits a pris environ la moitié du temps).

D'autre part, gmpy popcount() a pris environ 1/20e du temps de bin(n).count("1") . Si vous pouvez installer gmpy, utilisez-le.

Pour répondre à une question posée dans les commentaires, j'utiliserais un tableau de correspondance pour les octets. Vous pouvez la générer au moment de l'exécution :

counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

Ou simplement le définir littéralement :

counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

Ensuite, c'est counts[x] pour obtenir le nombre de bits 1 dans x où 0 ≤ x ≤ 255.

Answer 3

Vous pouvez adapter l'algorithme suivant :

def CountBits(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary.
  return n

Cette méthode fonctionne pour les nombres positifs sur 64 bits, mais elle est facilement extensible et le nombre d'opérations croît avec le logarithme de l'argument (c'est-à-dire linéairement avec la taille des bits de l'argument).

Pour comprendre comment cela fonctionne, imaginez que vous divisez l'ensemble de la chaîne de 64 bits en 64 buckets de 1 bit. La valeur de chaque godet est égale au nombre de bits définis dans le godet (0 si aucun bit n'est défini et 1 si un bit est défini). La première transformation aboutit à un état analogue, mais avec 32 godets de 2 bits chacun. Pour ce faire, il suffit de décaler les godets de manière appropriée et d'additionner leurs valeurs (une seule addition suffit pour tous les godets, puisqu'il ne peut y avoir de report entre les godets - un nombre de n bits est toujours suffisamment long pour coder le nombre n). D'autres transformations conduisent à des états avec un nombre exponentiellement décroissant de godets de taille exponentiellement croissante jusqu'à ce que nous arrivions à un seul godet de 64 bits de long. Cela donne le nombre de bits définis dans l'argument d'origine.

Answer 4

Voici une implémentation Python de l'algorithme de comptage de population, comme expliqué dans ce document poste :

def numberOfSetBits(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

Il fonctionnera pour 0 <= i < 0x100000000 .

Answer 5

J'aime beaucoup cette méthode. Elle est simple et assez rapide, mais elle n'est pas non plus limitée dans la longueur des bits puisque Python a des entiers infinis.

C'est en fait plus astucieux qu'il n'y paraît, car cela évite de perdre du temps à analyser les zéros. Par exemple, il faudra le même temps pour compter les bits définis dans 10000000000000000000010100000001 que dans 1111.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n