Comment puis-je vérifier Hamming Weight sans convertir en binaire?

Question

Comment puis-je obtenir le nombre de & "1 &"; s dans la représentation binaire d'un nombre sans convertir ni compter réellement?

par exemple

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

IMO, une bonne approche consisterait à utiliser une table de correspondance - créez un dictionnaire qui convertit les octets en nombre de 1 (vous pouvez utiliser le code que vous avez posté pour le générer, il ne devrait être exécuté qu'une seule fois), et puis utilisez quelque chose comme ceci:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

Je pense que c'est un assez bon compromis entre espace et temps d'exécution.

Answer 2

Je ne suis pas un programmeur python, mais j'espère qu'il vous suffira de le suivre.

c = 0
while n:
    c += 1
    n &= n - 1

return c

Bien qu’un peu obscur, son principal avantage est la rapidité et la simplicité. La boucle while n’est itérée qu’une fois pour chaque bit défini sur 1 sur n.

Answer 3

Vous ne pouvez pas rendre cela moins complexe en calcul. Ce sera O (n) le nombre de bits, ou, comme réponse avec le & Amp; astuce a montré, O (n) le nombre de bits mis à 1; mais à moins que tous les nombres que vous utilisez ne constituent un cas spécial, ces derniers doivent en moyenne être n / 2, de sorte que les deux nombres O (n) sont identiques.

Et l’astuce de la table de correspondance, bien sûr, ne fait rien pour la complexité informatique; c'est juste payer pour le temps avec l'espace, mais sans changer les données économiques sous-jacentes, à savoir que vous devez examiner chaque bit une fois d'une manière ou d'une autre et il n'y a aucun moyen de contourner cela. Logiquement, vous ne pouvez pas répondre à une question sur les bits du nombre sans inspecter chacun d'entre eux.

Maintenant, je suppose que je suis un peu bâclé, car bon nombre de ces exemples sont en fait O (n ^ 2) car en Python, vous devez examiner le nombre entier en même temps, donc avec un entier long Python de, disons , 100 octets, un + ou un & Amp; ou a / opération examinera chaque octet au moins une fois, et cela se produira encore et encore jusqu'à ce que le nombre soit réduit à zéro (dans les schémas décrits ci-dessus), de sorte qu'il s'agit là encore d'opérations O (n ^ 2). Je ne suis pas sûr que Python autorisera une véritable solution O (n) ici.

Quoi qu'il en soit: si vous vous posiez vraiment des questions sur la complexité informatique , ce qui signifie spécifiquement l'analyse big-O, voici votre réponse. : -)

Answer 4

Si vous souhaitez le faire sur une seule ligne, vous pouvez utiliser:

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 5

Si la vitesse vous préoccupe, codez-la en C (voir cette question pour savoir comment) et interfacer avec l'implémentation C en utilisant quelque chose comme ctypes .

Answer 6

ici:

def bitCount (int_no):

c = 0
while(int_no):
    int_no &= (int_no - 1)
    c += 1
return c

C’est peut-être un moyen ancien et efficace de le faire ... initialement mis en œuvre en C (Algo a un nom dont je ne me souviens plus). Cela fonctionne bien pour moi, j'espère que ça le sera pour toute autre personne

Answer 7

p = lambda n: n et 1 + p (n & amp; (n-1))

Ceci utilise court-circuit et récursivité, lorsque n est supérieur à 0, il commute pour calculer 1 + p (n & amp; (n-1)) où p (n & amp; (n- 1)) est appelé, etc., lorsque n est égal à 0, il renvoie 0. La complexité étant O (n) car le nombre de fois qu'il en existe un dans le binaire, il est exécuté.

Exemple: p (9) = 1 + p (8) = 1 + 1 + p (0) = 1 + 1 + 0 = 2