Wie viele 1s in einem n-Bit-Integer?

Question

Ein interessantes Problem, das ich in heute lief: Was ist der schnellste Weg, um die Anzahl von 1s in einem n-Bit-Integer zu zählen? Ist es möglich, O (n) zu schlagen?

Zum Beispiel:

42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one

Natürlich ist der naive Algorithmus einfach zu zählen. Aber gibt es irgendwelche Tricks es zu beschleunigen?

(Dies ist nur eine akademische Frage,. Es gibt keinen erwarteten Leistungsgewinn durch eine solche Umsetzung einer Strategie)

Answer 1

Sehen Sie die fabelhafte Bit Twiddling Hacks Artikel .

Answer 2

Wahrscheinlich der schnellste Weg, auf x86-Prozessoren wäre die POPCNT Klasse von Anweisungen.

Answer 3

Der schnellste Weg (ohne spezielle Prozessorfunktionen benutzen oder verwahren vorausberechneten Antworten) zu und Ihr Wert mit Wert -. 1 in einer Schleife, bis es 0. Die Anzahl der Iterationen die Anzahl von 1en ist

Answer 4

Wenn Sie eine endliche Anzahl von Bits (zB 32 Bits) haben, können Sie es precalcualte und dann schauen nur den Wert in einem Array.

Eine etwas praktischere Möglichkeit, dies ist für jedes Byte oder Wort zu tun (dauert nur 256 / 64k Byte) und dann die Ergebnisse für jedes Byte / Wort in dem Wert hinzufügen

Answer 5

O (log n) , wenn Sie nicht gehen jenseits Maschinenwörter und ignorieren die Tatsache, dass jede Maschine Betrieb auf n Bits arbeitet.

In der Praxis sollten Sie Bibliotheksfunktionen verwenden, anstatt die Bits sich von twiddling, zum Beispiel Integer.bitCount () in Java.