8 Bits, die die Zahl 7 darstellen, sehen folgendermaßen aus:
00000111
Es werden drei Bits gesetzt.
Was sind Algorithmen, um die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl zu bestimmen?
algorithm
binary
bit-manipulation
hammingweight
iec10967
Matt Howells
quelle
quelle
Antworten:
Dies ist als " Hamming Weight ", "Popcount" oder "Sideways Addition" bekannt.
Der "beste" Algorithmus hängt wirklich davon ab, auf welcher CPU Sie sich befinden und wie Ihr Nutzungsmuster ist.
Einige CPUs haben einen einzigen eingebauten Befehl, um dies zu tun, und andere haben parallele Befehle, die auf Bitvektoren wirken. Die parallelen Anweisungen (wie x86
popcnt
auf CPUs, auf denen sie unterstützt werden) sind mit ziemlicher Sicherheit am schnellsten. Bei einigen anderen Architekturen ist möglicherweise ein langsamer Befehl implementiert, der mit einer mikrocodierten Schleife implementiert ist, die ein Bit pro Zyklus testet ( Zitieren erforderlich ).Eine vorab ausgefüllte Tabellensuchmethode kann sehr schnell sein, wenn Ihre CPU über einen großen Cache verfügt und / oder Sie viele dieser Anweisungen in einer engen Schleife ausführen. Es kann jedoch unter den Kosten eines "Cache-Fehlers" leiden, bei dem die CPU einen Teil der Tabelle aus dem Hauptspeicher abrufen muss. (Suchen Sie jedes Byte einzeln nach, um die Tabelle klein zu halten.)
Wenn Sie wissen, dass Ihre Bytes meistens Nullen oder meistens Einsen sind, gibt es für diese Szenarien sehr effiziente Algorithmen.
Ich glaube, ein sehr guter Allzweckalgorithmus ist der folgende, der als "paralleler" oder "SWAR-Algorithmus mit variabler Genauigkeit" bekannt ist. Ich habe dies in einer C-ähnlichen Pseudosprache ausgedrückt. Möglicherweise müssen Sie es anpassen, um für eine bestimmte Sprache zu funktionieren (z. B. mit uint32_t für C ++ und >>> in Java):
Für JavaScript: coerce zu integer mit
|0
für die Leistung: ändern Sie die erste Zeilei = (i|0) - ((i >> 1) & 0x55555555);
Dies hat das beste Worst-Case-Verhalten aller diskutierten Algorithmen und kann daher effizient mit allen Verwendungsmustern oder Werten umgehen, die Sie darauf werfen.
Wie dieser SWAR-Bithack funktioniert:
Der erste Schritt ist eine optimierte Version der Maskierung, um die ungeraden / geraden Bits zu isolieren, zu verschieben, um sie auszurichten, und um sie hinzuzufügen. Dies führt effektiv 16 separate Additionen in 2-Bit-Akkumulatoren durch ( SWAR = SIMD Within A Register ). Wie
(i & 0x55555555) + ((i>>1) & 0x55555555)
.Der nächste Schritt nimmt die ungeraden / geraden acht dieser 16x 2-Bit-Akkumulatoren und addiert sie erneut, wodurch 8x 4-Bit-Summen erzeugt werden. Die
i - ...
Optimierung ist diesmal nicht möglich, daher wird nur vor / nach dem Schalten maskiert. Die Verwendung derselben0x33...
Konstante beide Male anstelle0xccc...
vor dem Verschieben ist eine gute Sache, wenn Sie für ISAs kompilieren, die 32-Bit-Konstanten in Registern separat erstellen müssen.Der letzte Schritt
(i + (i >> 4)) & 0x0F0F0F0F
zum Verschieben und Hinzufügen wird auf 4x 8-Bit-Akkumulatoren erweitert. Es maskiert nach dem Hinzufügen statt vorher, da der Maximalwert in einem 4-Bit-Akkumulator ist4
, wenn alle 4 Bits der entsprechenden Eingangsbits gesetzt wurden. 4 + 4 = 8, was immer noch in 4 Bits passt, so dass ein Übertrag zwischen Nibble-Elementen in unmöglich isti + (i >> 4)
.Bisher ist dies nur eine ganz normale SIMD mit SWAR-Techniken und einigen cleveren Optimierungen. Wenn Sie für zwei weitere Schritte mit demselben Muster fortfahren, kann dies auf 2x 16-Bit und dann auf 1x 32-Bit-Anzahl erweitert werden. Auf Maschinen mit schneller Hardware-Multiplikation gibt es jedoch einen effizienteren Weg:
Sobald wir wenige "Elemente" haben, kann eine Multiplikation mit einer magischen Konstante alle Elemente zum obersten Element zusammenfassen . In diesem Fall Byte-Elemente. Das Multiplizieren erfolgt durch Verschieben und Addieren nach links, sodass eine Multiplikation der
x * 0x01010101
Ergebnisse erfolgtx + (x<<8) + (x<<16) + (x<<24)
. Unsere 8-Bit-Elemente sind breit genug (und klein genug), dass dies keinen Übertrag in die oberen 8 Bits erzeugt.Eine 64-Bit-Version davon kann 8x 8-Bit-Elemente in einer 64-Bit-Ganzzahl mit einem 0x0101010101010101-Multiplikator ausführen und das High-Byte mit extrahieren
>>56
. Es sind also keine zusätzlichen Schritte erforderlich, sondern nur breitere Konstanten. Dies ist, was GCC__builtin_popcountll
auf x86-Systemen verwendet, wenn die Hardwareanweisungpopcnt
nicht aktiviert ist. Wenn Sie hierfür eingebaute oder intrinsische Funktionen verwenden können, geben Sie dem Compiler die Möglichkeit, zielspezifische Optimierungen vorzunehmen.Mit voller SIMD für breitere Vektoren (z. B. Zählen eines ganzen Arrays)
Dieser bitweise SWAR-Algorithmus könnte parallelisiert werden, um in mehreren Vektorelementen gleichzeitig statt in einem einzelnen Ganzzahlregister ausgeführt zu werden, um eine Beschleunigung auf CPUs mit SIMD, aber ohne verwendbaren Popcount-Befehl zu erreichen. (zB x86-64-Code, der auf jeder CPU ausgeführt werden muss, nicht nur auf Nehalem oder höher.)
Der beste Weg, Vektoranweisungen für Popcount zu verwenden, ist normalerweise die Verwendung eines variablen Shuffle, um eine Tabellensuche für 4 Bits gleichzeitig für jedes Byte parallel durchzuführen. (Die 4 Bits indizieren eine 16-Eintragstabelle, die in einem Vektorregister gehalten wird).
Auf Intel-CPUs kann der Hardware-64- Bit- Popcnt-Befehl eine bitparallele SSSE3
PSHUFB
-Implementierung um etwa den Faktor 2 übertreffen , jedoch nur, wenn Ihr Compiler dies genau richtig macht . Andernfalls kann SSE deutlich voraus sein. Neuere Compilerversionen sind sich des Problems der falschen Abhängigkeit von popcnt von Intel bewusst .Verweise:
quelle
unsigned int
, um leicht zu zeigen, dass es frei von Anzeichen von Komplikationen ist. Wäre esuint32_t
auch sicherer, wenn Sie auf allen Plattformen das bekommen, was Sie erwarten?>>
ist implementierungsdefiniert für negative Werte. Das Argument muss geändert (oder umgewandelt) werdenunsigned
, und da der Code 32-Bit-spezifisch ist, sollte er wahrscheinlich verwendet werdenuint32_t
.Berücksichtigen Sie auch die integrierten Funktionen Ihrer Compiler.
Auf dem GNU-Compiler können Sie beispielsweise einfach Folgendes verwenden:
Im schlimmsten Fall generiert der Compiler einen Aufruf einer Funktion. Im besten Fall gibt der Compiler eine CPU-Anweisung aus, um denselben Job schneller auszuführen.
Die GCC-Eigenschaften funktionieren sogar plattformübergreifend. Popcount wird zum Mainstream in der x86-Architektur, daher ist es sinnvoll, jetzt das Intrinsic zu verwenden. Andere Architekturen haben die Popcount seit Jahren.
Unter x86 können Sie dem Compiler mitteilen, dass er Unterstützung für
popcnt
Anweisungen mit-mpopcnt
oder-msse4.2
zur Aktivierung der Vektoranweisungen übernehmen kann, die in derselben Generation hinzugefügt wurden. Siehe GCC x86-Optionen .-march=nehalem
(oder-march=
welche CPU auch immer Ihr Code annehmen und einstellen soll) könnte eine gute Wahl sein. Das Ausführen der resultierenden Binärdatei auf einer älteren CPU führt zu einem Fehler mit unzulässigen Anweisungen.Verwenden Sie
-march=native
(mit gcc, clang oder ICC), um Binärdateien für den Computer zu optimieren, auf dem Sie sie erstellen .MSVC bietet eine Eigenschaft für den x86-
popcnt
Befehl , aber im Gegensatz zu gcc ist es eine Eigenschaft für die Hardware-Anweisung und erfordert Hardware-Unterstützung.Verwenden
std::bitset<>::count()
anstelle eines eingebautenTheoretisch sollte jeder Compiler, der weiß, wie man effizient für die Ziel-CPU zählt, diese Funktionalität über ISO C ++ verfügbar machen
std::bitset<>
. In der Praxis ist der Bit-Hack AND / shift / ADD in einigen Fällen für einige Ziel-CPUs möglicherweise besser geeignet.Für Zielarchitekturen, bei denen Hardware-Popcount eine optionale Erweiterung ist (wie x86), verfügen nicht alle Compiler über eine
std::bitset
, die diese nutzt, wenn sie verfügbar ist. Zum Beispiel hat MSVC keine Möglichkeit, diepopcnt
Unterstützung zur Kompilierungszeit zu aktivieren , und verwendet immer eine Tabellensuche , auch mit/Ox /arch:AVX
(was SSE4.2 impliziert, obwohl es technisch gesehen ein separates Feature-Bit für gibtpopcnt
.)Aber zumindest erhalten Sie etwas Portables, das überall funktioniert, und mit gcc / clang mit den richtigen Zieloptionen erhalten Sie Hardware-Popcount für Architekturen, die dies unterstützen.
Siehe asm von gcc, clang, icc und MSVC im Godbolt-Compiler-Explorer.
x86-64
gcc -O3 -std=gnu++11 -mpopcnt
gibt Folgendes aus :PowerPC64
gcc -O3 -std=gnu++11
gibt aus (für dieint
arg-Version):Diese Quelle ist überhaupt nicht x86-spezifisch oder GNU-spezifisch, sondern lässt sich nur für x86 mit gcc / clang / icc gut kompilieren.
Beachten Sie auch, dass der Fallback von gcc für Architekturen ohne Popcount für einzelne Befehle eine Tabellensuche nach Byte ist. Dies ist zum Beispiel für ARM nicht wunderbar .
quelle
std::bitset::count
. Nach dem Inlinen wird dies zu einem einzigen__builtin_popcount
Aufruf kompiliert .Meiner Meinung nach ist die "beste" Lösung die, die von einem anderen Programmierer (oder dem ursprünglichen Programmierer zwei Jahre später) ohne ausführliche Kommentare gelesen werden kann. Vielleicht möchten Sie die schnellste oder klügste Lösung, die einige bereits bereitgestellt haben, aber ich bevorzuge jederzeit die Lesbarkeit gegenüber der Klugheit.
Wenn Sie mehr Geschwindigkeit wünschen (und davon ausgehen, dass Sie diese gut dokumentieren, um Ihren Nachfolgern zu helfen), können Sie eine Tabellensuche verwenden:
Obwohl diese auf bestimmten Datentypgrößen beruhen, sind sie nicht so portabel. Da jedoch viele Leistungsoptimierungen ohnehin nicht portierbar sind, ist dies möglicherweise kein Problem. Wenn Sie Portabilität wünschen, würde ich mich an die lesbare Lösung halten.
quelle
if ((value & 1) == 1) { count++; }
mitcount += value & 1
?Aus Hacker's Delight, p. 66, Abbildung 5-2
Wird in ~ 20-ish-Anweisungen (archabhängig) ausgeführt, keine Verzweigung.
Hacker's Delight ist herrlich! Sehr empfehlenswert.
quelle
Integer.bitCount(int)
verwendet genau diese Implementierung.pop
anstattpopulation_count
(oderpop_cnt
wenn Sie eine Abkürzung haben müssen). @ MarcoBolis Ich gehe davon aus, dass dies für alle Java-Versionen gilt, aber offiziell wäre dies implementierungsabhängig :)Ich denke, der schnellste Weg - ohne Nachschlagetabellen und Popcount zu verwenden - ist der folgende. Es zählt die gesetzten Bits mit nur 12 Operationen.
Dies funktioniert, weil Sie die Gesamtzahl der gesetzten Bits zählen können, indem Sie sie in zwei Hälften teilen, die Anzahl der gesetzten Bits in beiden Hälften zählen und sie dann addieren. Auch als
Divide and Conquer
Paradigma bekannt. Lassen Sie uns ins Detail gehen ..Die Anzahl der Bits in zwei Bits sein kann
0b00
,0b01
oder0b10
. Versuchen wir das mit 2 Bits herauszufinden.Dies war erforderlich: Die letzte Spalte zeigt die Anzahl der gesetzten Bits in jedem Zwei-Bit-Paar. Wenn die zwei Bit - Zahl wird
>= 2 (0b10)
dannand
erzeugt0b01
, sonst erzeugt es0b00
.Diese Aussage sollte leicht verständlich sein. Nach der ersten Operation haben wir die Anzahl der gesetzten Bits in jeweils zwei Bits, jetzt addieren wir diese Anzahl in jeweils 4 Bits.
Wir fassen dann das obige Ergebnis zusammen und geben uns die Gesamtzahl der gesetzten Bits in 4 Bits. Die letzte Aussage ist die schwierigste.
Lassen Sie es uns weiter aufschlüsseln ...
Es ist ähnlich wie bei der zweiten Aussage; Stattdessen zählen wir die gesetzten Bits in 4er-Gruppen. Wir wissen - aufgrund unserer vorherigen Operationen -, dass jedes Halbbyte die Anzahl der gesetzten Bits enthält. Schauen wir uns ein Beispiel an. Angenommen, wir haben das Byte
0b01000010
. Dies bedeutet, dass für das erste Halbbyte 4 Bit und für das zweite Halbbyte 2 Bit festgelegt sind. Jetzt addieren wir diese Knabbereien.Es gibt uns die Anzahl der gesetzten Bits in einem Byte im ersten Halbbyte
0b01100010
und daher maskieren wir die letzten vier Bytes aller Bytes in der Zahl (verwerfen sie).Jetzt enthält jedes Byte die Anzahl der gesetzten Bits. Wir müssen sie alle zusammen addieren. Der Trick besteht darin, das Ergebnis mit
0b10101010
einer interessanten Eigenschaft zu multiplizieren . Wenn unsere Nummer vier Bytes hatA B C D
, führt dies zu einer neuen Nummer mit diesen BytesA+B+C+D B+C+D C+D D
. Für eine 4-Byte-Nummer können maximal 32 Bit gesetzt werden, die als dargestellt werden können0b00100000
.Jetzt brauchen wir nur noch das erste Byte, das die Summe aller gesetzten Bits in allen Bytes enthält, und wir bekommen es durch
>> 24
. Dieser Algorithmus wurde für32 bit
Wörter entwickelt, kann jedoch leicht für64 bit
Wörter geändert werden .quelle
c =
? Sieht so aus, als sollte es beseitigt werden. Schlagen Sie außerdem einen zusätzlichen Parensatz A "(((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24" vor, um einige klassische Warnungen zu vermeiden.popcount(int v)
undpopcount(unsigned v)
. Berücksichtigen Sie für die Portabilitätpopcount(uint32_t v)
usw. den Teil * 0x1010101.return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
Wir müssen also keine Buchstaben zählen, um zu sehen, was Sie tatsächlich tun (da Sie die erste verworfen haben0
, dachte ich versehentlich, Sie hätten das falsche (gespiegelte) Bitmuster als Maske verwendet - bis ich feststellte, dass es nur 7 Buchstaben gibt und nicht 8).Ich langweilte mich und plante eine Milliarde Iterationen von drei Ansätzen. Der Compiler ist gcc -O3. CPU ist alles, was sie in das Macbook Pro der 1. Generation stecken.
Am schnellsten ist mit 3,7 Sekunden Folgendes:
Der zweite Platz geht an denselben Code, aber es werden 4 Bytes anstelle von 2 Halbwörtern nachgeschlagen. Das dauerte ungefähr 5,5 Sekunden.
Der dritte Platz geht an den Bit-Twiddling-Ansatz „Seitwärtsaddition“, der 8,6 Sekunden dauerte.
Der vierte Platz geht an GCCs __builtin_popcount () mit beschämenden 11 Sekunden.
Das Zählen nacheinander war etwas langsamer, und es langweilte mich, darauf zu warten, dass es abgeschlossen war.
Wenn Sie also vor allem Wert auf Leistung legen, verwenden Sie den ersten Ansatz. Wenn Sie sich interessieren, aber nicht genug, um 64 KB RAM dafür auszugeben, verwenden Sie den zweiten Ansatz. Verwenden Sie andernfalls den lesbaren (aber langsamen) Einzelbit-zu-Zeit-Ansatz.
Es ist schwer, sich eine Situation vorzustellen, in der Sie den Bit-Twiddling-Ansatz verwenden möchten.
Edit: Ähnliche Ergebnisse hier .
quelle
Wenn Sie Java verwenden, wird dies von der integrierten Methode ausgeführt
Integer.bitCount
.quelle
Lassen Sie mich diesen Algorithmus erklären.
Dieser Algorithmus basiert auf dem Divide and Conquer-Algorithmus. Angenommen, es gibt eine 8-Bit-Ganzzahl 213 (11010101 in Binär), funktioniert der Algorithmus folgendermaßen (jedes Mal, wenn zwei Nachbarblöcke zusammengeführt werden):
quelle
Dies ist eine dieser Fragen, bei denen es hilfreich ist, Ihre Mikroarchitektur zu kennen. Ich habe gerade zwei Varianten unter gcc 4.3.3 zeitlich festgelegt, die mit -O3 unter Verwendung von C ++ - Inlines kompiliert wurden, um den Funktionsaufruf-Overhead zu eliminieren, eine Milliarde Iterationen, wobei die laufende Summe aller Zählungen beibehalten wurde, um sicherzustellen, dass der Compiler nichts Wichtiges entfernt, und rdtsc für das Timing verwendet ( Takt genau).
Das unveränderte Hacker's Delight benötigte 12,2 Gigacycles. Meine parallele Version (doppelt so viele Bits) läuft in 13.0 Gigacycles. Auf einem 2,4-GHz-Core-Duo verstrichen insgesamt 10,5 Sekunden für beide. 25 Gigacycles = etwas mehr als 10 Sekunden bei dieser Taktfrequenz, daher bin ich zuversichtlich, dass mein Timing stimmt.
Dies hat mit Befehlsabhängigkeitsketten zu tun, die für diesen Algorithmus sehr schlecht sind. Ich könnte die Geschwindigkeit mit einem Paar 64-Bit-Registern wieder fast verdoppeln. In der Tat, wenn ich klug wäre und x + ya etwas früher hinzufügen würde, könnte ich einige Schichten rasieren. Die 64-Bit-Version mit einigen kleinen Verbesserungen würde sogar herauskommen, aber wieder doppelt so viele Bits zählen.
Mit 128-Bit-SIMD-Registern, einem weiteren Faktor von zwei, und den SSE-Befehlssätzen gibt es oft auch clevere Abkürzungen.
Es gibt keinen Grund, warum der Code besonders transparent ist. Die Schnittstelle ist einfach, der Algorithmus kann an vielen Stellen online referenziert werden und ist für umfassende Unit-Tests zugänglich. Der Programmierer, der darauf stößt, könnte sogar etwas lernen. Diese Bitoperationen sind auf Maschinenebene äußerst natürlich.
OK, ich habe mich für die optimierte 64-Bit-Version entschieden. Für diese eine Größe von (unsigned long) == 8
Das sieht ungefähr richtig aus (ich teste aber nicht sorgfältig). Jetzt kommen die Timings bei 10,70 Gigacycles / 14,1 Gigacycles heraus. Diese spätere Zahl summierte sich auf 128 Milliarden Bits und entspricht 5,9 Sekunden, die auf dieser Maschine verstrichen sind. Die nicht parallele Version beschleunigt ein kleines bisschen, weil ich im 64-Bit-Modus arbeite und 64-Bit-Register etwas besser mag als 32-Bit-Register.
Mal sehen, ob es hier ein bisschen mehr OOO-Pipelining gibt. Das war etwas komplizierter, also habe ich tatsächlich ein bisschen getestet. Jeder Term allein ergibt 64, alle zusammen 256.
Ich war für einen Moment aufgeregt, aber es stellte sich heraus, dass gcc Inline-Streiche mit -O3 spielt, obwohl ich das Inline-Schlüsselwort in einigen Tests nicht verwende. Wenn ich gcc Streiche spielen lasse, dauert eine Milliarde Aufrufe von pop4 () 12,56 Gigacycles, aber ich habe festgestellt, dass Argumente als konstante Ausdrücke gefaltet werden. Eine realistischere Zahl scheint 19,6 gc für eine weitere Beschleunigung von 30% zu sein. Meine Testschleife sieht jetzt so aus und stellt sicher, dass jedes Argument anders genug ist, um zu verhindern, dass gcc Streiche spielt.
In 8,17 Sekunden summierten sich 256 Milliarden Bits. Funktioniert für 32 Millionen Bit auf 1,02 Sekunden, wie in der 16-Bit-Tabellensuche angegeben. Kann nicht direkt verglichen werden, da die andere Bank keine Taktrate angibt, aber es sieht so aus, als hätte ich den Rotz aus der 64-KB-Tabellenausgabe geschlagen, was in erster Linie eine tragische Verwendung des L1-Cache ist.
Update: beschlossen, das Offensichtliche zu tun und pop6 () zu erstellen, indem vier weitere doppelte Zeilen hinzugefügt wurden. Kam auf 22,8 gc, 384 Milliarden Bits summiert in 9,5s verstrichen. Es gibt also weitere 20% jetzt bei 800 ms für 32 Milliarden Bits.
quelle
Warum nicht iterativ durch 2 teilen?
Ich stimme zu, dass dies nicht das schnellste ist, aber "das Beste" ist etwas mehrdeutig. Ich würde jedoch argumentieren, dass "am besten" ein Element der Klarheit haben sollte
quelle
Das Bit-Twiddling von Hacker's Delight wird viel deutlicher, wenn Sie die Bitmuster ausschreiben.
Der erste Schritt addiert die geraden Bits zu den ungeraden Bits und erzeugt eine Summe von Bits in jeweils zwei. Die anderen Schritte fügen Blöcke höherer Ordnung zu Blöcken niedriger Ordnung hinzu und verdoppeln die Blockgröße bis zum Ende, bis die endgültige Zählung den gesamten Int aufnimmt.
quelle
Für ein fröhliches Medium zwischen einer 2 32- Nachschlagetabelle und dem individuellen Durchlaufen jedes Bits:
Von http://ctips.pbwiki.com/CountBits
quelle
Dies kann in erfolgen
O(k)
, wobeik
die Anzahl der gesetzten Bits ist.quelle
n &= (n-1)
Form verwendete.Es ist nicht die schnellste oder beste Lösung, aber ich fand die gleiche Frage auf meinem Weg und begann zu denken und zu denken. Schließlich wurde mir klar, dass dies so möglich ist, wenn Sie das Problem von der mathematischen Seite her betrachten und ein Diagramm zeichnen. Dann stellen Sie fest, dass es sich um eine Funktion handelt, die einen periodischen Teil hat, und dann erkennen Sie den Unterschied zwischen den Perioden ... also Bitte schön:
quelle
def f(i, d={0:lambda:0, 1:lambda:1, 2:lambda:1, 3:lambda:2}): return d.get(i, lambda: f(i//4) + f(i%4))()
Die gesuchte Funktion wird häufig als "Seitwärtssumme" oder "Bevölkerungszahl" einer Binärzahl bezeichnet. Knuth diskutiert es in Pre-Fascicle 1A, S. 11-12 (obwohl es in Band 2, 4.6.3- (7) eine kurze Referenz gab.)
Der locus classicus ist Peter Wegners Artikel "Eine Technik zum Zählen von Personen in einem binären Computer" aus den Mitteilungen der ACM , Band 3 (1960) Nummer 5, Seite 322 . Dort gibt er zwei verschiedene Algorithmen an, einen, der für Zahlen optimiert ist, von denen erwartet wird, dass sie "spärlich" sind (dh eine kleine Anzahl von Einsen haben), und einen für den umgekehrten Fall.
quelle
quelle
Einige offene Fragen: -
Wir können das Algo so ändern, dass es die negative Zahl wie folgt unterstützt: -
Um das zweite Problem zu lösen, können wir das Algo wie folgt schreiben:
Vollständige Referenz siehe:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
quelle
Ich denke, die Methode von Brian Kernighan wird auch nützlich sein ... Sie durchläuft so viele Iterationen, wie gesetzte Bits vorhanden sind. Wenn wir also ein 32-Bit-Wort haben, bei dem nur das High-Bit gesetzt ist, wird es nur einmal durch die Schleife gehen.
quelle
Ich benutze den folgenden Code, der intuitiver ist.
Logik: n & (n-1) setzt das zuletzt gesetzte Bit von n zurück.
PS: Ich weiß, dass dies keine O (1) -Lösung ist, wenn auch eine interessante Lösung.
quelle
O(ONE-BITS)
. Es ist tatsächlich O (1), da es höchstens 32 Ein-Bits gibt.Was meinst du mit "Bester Algorithmus"? Der Kurzschlusscode oder der Fastencode? Ihr Code sieht sehr elegant aus und hat eine konstante Ausführungszeit. Der Code ist auch sehr kurz.
Aber wenn die Geschwindigkeit der Hauptfaktor und nicht die Codegröße ist, kann das Folgende meiner Meinung nach schneller sein:
Ich denke, dass dies für einen 64-Bit-Wert nicht schneller sein wird, aber ein 32-Bit-Wert kann schneller sein.
quelle
Ich habe ungefähr 1990 ein schnelles Bitcount-Makro für RISC-Maschinen geschrieben. Es verwendet keine fortgeschrittene Arithmetik (Multiplikation, Division,%), Speicherabrufe (viel zu langsam), Verzweigungen (viel zu langsam), aber es wird davon ausgegangen, dass die CPU eine hat 32-Bit-Barrel-Shifter (mit anderen Worten, >> 1 und >> 32 benötigen dieselbe Anzahl von Zyklen). Es wird davon ausgegangen, dass kleine Konstanten (wie 6, 12, 24) nichts zum Laden in die Register kosten oder gespeichert werden in Provisorien und immer wieder verwendet.
Mit diesen Annahmen werden auf den meisten RISC-Maschinen 32 Bit in etwa 16 Zyklen / Anweisungen gezählt. Beachten Sie, dass 15 Anweisungen / Zyklen nahe an einer Untergrenze für die Anzahl der Zyklen oder Anweisungen liegen, da anscheinend mindestens 3 Anweisungen (Maske, Verschiebung, Operator) erforderlich sind, um die Anzahl der Addenden zu halbieren, also log_2 (32). = 5, 5 x 3 = 15 Anweisungen sind quasi eine Untergrenze.
Hier ist ein Geheimnis für den ersten und komplexesten Schritt:
Wenn ich also die erste Spalte (A) oben nehme, sie 1 Bit nach rechts verschiebe und von AB subtrahiere, erhalte ich die Ausgabe (CD). Die Erweiterung auf 3 Bit ist ähnlich; Sie können es mit einer 8-zeiligen booleschen Tabelle wie meiner oben überprüfen, wenn Sie möchten.
quelle
Wenn Sie C ++ verwenden, können Sie auch die Metaprogrammierung von Vorlagen verwenden:
Verwendung wäre:
Sie können diese Vorlage natürlich weiter erweitern, um verschiedene Typen zu verwenden (sogar die automatische Erkennung der Bitgröße), aber ich habe sie aus Gründen der Übersichtlichkeit einfach gehalten.
edit: Ich habe vergessen zu erwähnen, dass dies gut ist, da es in jedem C ++ - Compiler funktionieren sollte und Ihre Schleife im Grunde nur für Sie abrollt, wenn ein konstanter Wert für die Bitanzahl verwendet wird (mit anderen Worten, ich bin mir ziemlich sicher, dass dies die schnellste allgemeine Methode ist du wirst es finden)
quelle
constexpr
.Dieses Beispiel aus der Glücksakte gefällt mir besonders gut:
Ich mag es am liebsten, weil es so hübsch ist!
quelle
Java JDK1.5
Integer.bitCount (n);
Dabei ist n die Zahl, deren Einsen gezählt werden sollen.
Überprüfen Sie auch,
quelle
Ich fand eine Implementierung der Bitzählung in einem Array unter Verwendung von SIMD-Anweisungen (SSSE3 und AVX2). Es hat eine 2-2,5-mal bessere Leistung als wenn es die intrinsische Funktion __popcnt64 verwendet.
SSSE3-Version:
AVX2-Version:
quelle
Ich benutze dies immer in Competitive Programming und es ist einfach zu schreiben und effizient:
quelle
Es gibt viele Algorithmen, um die gesetzten Bits zu zählen. aber ich denke das beste ist das schnellere! Sie können die Details auf dieser Seite sehen:
Bit Twiddling Hacks
Ich schlage vor:
Zählen von Bits in 14-, 24- oder 32-Bit-Wörtern mithilfe von 64-Bit-Anweisungen
Diese Methode erfordert eine 64-Bit-CPU mit schneller Modulteilung, um effizient zu sein. Die erste Option benötigt nur 3 Operationen. Die zweite Option dauert 10; und die dritte Option dauert 15.
quelle
Schnelle C # -Lösung unter Verwendung einer vorberechneten Tabelle der Bytebitanzahl mit Verzweigung nach Eingabegröße.
quelle
(0xe994 >>(k*2))&3
Hier ist ein tragbares Modul (ANSI-C), das jeden Ihrer Algorithmen auf jeder Architektur vergleichen kann.
Ihre CPU hat 9 Bit Bytes? Kein Problem :-) Im Moment werden 2 Algorithmen implementiert, der K & R-Algorithmus und eine byteweise Nachschlagetabelle. Die Nachschlagetabelle ist im Durchschnitt dreimal schneller als der K & R-Algorithmus. Wenn jemand einen Weg finden kann, den "Hacker's Delight" -Algorithmus portabel zu machen, können Sie ihn gerne hinzufügen.
.
quelle
Was Sie tun können, ist
Die Logik dahinter ist, dass die Bits von n-1 vom am weitesten rechts gesetzten Bit von n invertiert werden. Wenn n = 6, dh 110, dann ist 5 101, werden die Bits vom am weitesten rechts gesetzten Bit von n invertiert. Wenn wir und diese beiden also das Bit ganz rechts in jeder Iteration machen und immer zum nächsten ganz rechts gesetzten Bit gehen. Zählen Sie daher das gesetzte Bit. Die schlechteste Zeitkomplexität ist O (logn), wenn jedes Bit gesetzt ist.
quelle