Wie kann ich Hamming Gewicht überprüfen, ohne auf binäre Umwandlung?

Question

Wie kann ich die Anzahl der „1“ in der binären Darstellung einer Zahl erhalten, ohne tatsächlich die Umwandlung und das Zählen?

z.

  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, ein guter Ansatz einer Look-up-Tabelle zu verwenden, wäre - ein Wörterbuch erstellen, die (den Code zu generieren Sie auf dem Laufenden es verwenden können Sie, wäre es nur einmal ausgeführt werden müssen) Bytes Anzahl von 1-umwandelt und verwenden so etwas wie dieses dann:

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

Ich glaube, das ist ein ziemlich guter Kompromiss zwischen Raum und Laufzeit.

Answer 2

Ich bin kein Python-Programmierer, aber hoffentlich wird es genug sein, für Sie zu folgen.

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

return c

Während ein wenig dunkel, es ist primärer Vorteil ist Schnelligkeit und Einfachheit. Die while-Schleife wird nur einmal iteriert für jedes Bit auf 1 in n eingestellt.

Answer 3

Sie können diese rechnerisch weniger komplex machen. Es wird O (n) die Anzahl der Bits, oder, wie die Antwort mit der & Trick zeigte, O (n) die Anzahl der Bits auf 1 gesetzt sein; aber es sei denn, alle Zahlen Sie verwenden ein Spezialfall sind im Durchschnitt sollte dieser n / 2 sein, also diese beiden O (n) Zahlen gleich sind.

Und der Lookup-Tabelle Trick, natürlich, ist eigentlich nichts zu tun, für die Rechenkomplexität; es ist nur mit Platz für die Zeit bezahlen, aber ohne die zugrunde liegende Wirtschaft zu ändern, die sind, dass Sie jedes Bit einmal prüfen müssen irgendwie und es gibt keinen Weg dran vorbei. Sie können nicht logisch, beantworten Sie eine Frage zu den Bits der Zahl ohne jede von ihnen Inspektion.

Nun, ich nehme an, ich meine es ein bisschen schlampig, da viele dieser Beispiele sind eigentlich O (n ^ 2), da in Python haben Sie die ganze Zahl auf einmal Zeit zu untersuchen, so mit einem Python lange ganze Zahl von, sagen 100 Bytes, a + oder & oder a / Operation wird bei jedem Byte zumindest einmal sehen, und das wird immer passieren, bis die Anzahl auf Null reduziert wird (in den vorstehend beschriebenen Programmen), so dass diese wiederum sind wirklich O (n ^ 2) Operationen. Ich bin nicht sicher, ob Python eine wahre O (n) Lösung hier ermöglichen.

Wie auch immer: Wenn Sie wirklich über fragen Computational Komplexität, die speziell Big-O-Analyse bedeutet, das ist die Antwort. : -)

Answer 4

Wenn Sie es in einer einzigen Zeile tun möchten, können Sie verwenden:

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

Answer 5

Wenn Sie wirklich besorgt sind über die Geschwindigkeit, Code in C (siehe diese Frage wie) und Schnittstelle bei der Umsetzung C mit so etwas wie ctypes .

Answer 6

Hier:

def Bitcount (int_no):

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

Dies könnte eine alte und effiziente Art und Weise, dies zu tun ... ursprünglich implementated in C (Algo hat einen Namen ich kann mich nicht erinnern). Es funktioniert gut für mich hoffen, dass es tut, für eine andere Person

Answer 7

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

Dieses verwendet einen Kurzschluss und Rekursion, wenn n größer als 0 ist, schaltet er 1 + p berechnen (n & amp; (n-1)), wobei p (n & amp; (n-1)) genannt wird, und so weiter, wenn n 0 ist das Ergebnis 0. Komplexität ist O (n), da es die Anzahl der Male, verläuft die Anzahl der Einsen in der binären existieren.

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