Wie kann ich die Anzahl von "1" s in der Binärdarstellung einer Zahl ohne tatsächlich konvertieren und zählen?Wie kann ich Hamming Weight überprüfen, ohne in binär zu konvertieren?
z.B.
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
IMO, wäre ein guter Ansatz, eine Nachschlagetabelle zu verwenden - ein Wörterbuch zu erstellen, das Bytes in eine Zahl von 1 umwandelt (Sie können den Code verwenden, den Sie zum Generieren angaben, es müsste nur einmal ausgeführt werden), und dann etwas wie folgt verwenden:
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.
Ich bin kein Python-Programmierer, aber hoffentlich wird es genug für Sie zu folgen.
Während ein wenig obskur, ist der Hauptvorteil Geschwindigkeit und Einfachheit. Die while-Schleife wird nur einmal für jedes Bit durchlaufen, das in n auf 1 gesetzt ist.
Wenn Sie tatsächlich über Geschwindigkeit besorgt sind, codieren Sie es in C (siehe this question für wie) und Schnittstelle mit der C-Implementierung mit etwas wie ctypes.
Ich beschäftige mich mit Rechenkomplexität nicht mit der tatsächlichen Geschwindigkeit oder Sprache. –
Wenn Sie es in einer einzigen Zeile tun möchten, können Sie verwenden:
sum([x&(1<<i)>0 for i in range(32)])
Sie nicht diese rechnerisch weniger komplex machen. Es ist O (n) die Anzahl der Bits, oder, wie die Antwort mit dem & Trick zeigte, O (n) die Anzahl der Bits, die auf 1 gesetzt sind; aber wenn nicht alle Zahlen, die Sie verwenden, ein Sonderfall sind, sollte der letztere im Durchschnitt n/2 sein, also sind beide dieser O (n) Zahlen gleich.
Und der Lookup-Table-Trick tut natürlich nichts für die Rechenkomplexität; es zahlt nur für die Zeit mit Platz, aber ohne die zugrundeliegenden Ökonomien zu ändern, die sind, dass Sie jedes Bit einmal untersuchen müssen irgendwie und es gibt keinen Weg darum herum. Sie können logischerweise keine Frage zu den Bits in der Zahl beantworten, ohne sie zu prüfen.
Nun, ich bin ein bisschen schlampig, da viele dieser Beispiele eigentlich O (n^2) sind, da man in Python die ganze Zahl auf einmal untersuchen muss, also mit einer langen Python-Zahl von, sagen wir, 100 Bytes, a + oder & oder a/Operation wird jedes Byte mindestens einmal betrachten, und das wird immer wieder vorkommen, bis die Zahl auf Null reduziert wird (in den oben beschriebenen Schemata), also diese wiederum sind wirklich O (n^2) Operationen. Ich bin mir nicht sicher, ob Python hier eine echte O (n) -Lösung erlaubt.
Wie auch immer: wenn Sie wirklich Fragen über computational Komplexität, die speziell Big-O-Analyse bedeutet, das ist Ihre Antwort. :-)
p = lambda n: n + 1 und p (n & (n-1))
Dieses verwendet einen Kurzschluss und Rekursion, wenn n größer als 0 ist, schaltet es 1 zu berechnen + p (n & (n-1)) wobei p (n & (n-1)) aufgerufen wird und so weiter, wenn n 0 ist, gibt es 0 zurück. Die Komplexität ist O (n), da es die Anzahl der Male ausführt Anzahl der Einsen existiert in der Binärdatei.
Beispiel: p (9) = 1 + p (8) = 1 + 1 + p (0) = 1 + 1 + 0 = 2
Wenn dies eine gültige Antwort ist, wäre es mit einigen Erklärungen wertvoller. –
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 sein ... implementated ursprünglich in C (Algo hat einen Namen ich mich nicht erinnern kann). Es funktioniert gut für mich, ich hoffe, dass es für jede andere Person tut
Ist dies ein Duplikat von http://stackoverflow.com/questions/843737/count-bits-in-the-number-closed – ChrisW
@ ChrisW- Python und c sind zwei verschiedene lanaguages – TStamper
Es ist kein genaues Duplikat. Bitweise Operationen in Python sind viel teurer, als dass c. –