Für Code, der sich auf diese Frage bezieht , muss ich Folgendes so schnell wie möglich berechnen:
Geben Sie für eine 32-Bit-Ganzzahl i die Position des n -ten niedrigstwertigen gesetzten Bits an. Sowohl n als auch das Ergebnis sollten 0-indiziert sein.
Wenn zum Beispiel die Zahl i = 11010110101 2 und n = 4 ist, ist die gewünschte Anzahl 7 als das vierte gesetzte Bit auf Position 7: 110 1 0110101.
Mit der Anweisung pdep aus der BMI2-Befehlssatzerweiterung für x86 und der allgemein verfügbaren __builtin_ctz() -Intrinsfunktion kann dies leicht berechnet werden:
Viele Computer haben jedoch nicht die Anweisung pdep , was diesen Ansatz etwas unpraktisch macht. Sie können solche Bitpositionen auch ohne pdep wie folgt berechnen:
Allerdings ist das ziemlich langsam.
Ich bin auf Computer ausgerichtet, die mindestens __builtin_popcount() und __builtin_ctz() enthalten. Wie kann ich solche Bitpositionen schneller finden?
Die Version von Bit-Twiddling-Hacks , die für diesen Fall angepasst wurde, ist zum Beispiel
%Vor% ergibt bei Kompilierung in einer separaten Kompilierungseinheit auf gcc-5.4.0 mit -Wall -O3 -march=native -mtune=native auf Intel Core i5-4200u
Bei einer Kompilierung als separate Kompilierungseinheit ist das Timing auf dieser Maschine schwierig, da die eigentliche Operation so schnell ist wie das Aufrufen einer Do-Nothing-Funktion (ebenfalls in einer separaten Kompilierungseinheit kompiliert); Im Wesentlichen wird die Berechnung während der Latenzen durchgeführt, die mit dem Funktionsaufruf verbunden sind.
Es scheint etwas schneller zu sein als mein Vorschlag einer binären Suche,
%Vor%wo die Schleife genau fünfmal ausgeführt wird, kompiliert zu
%Vor%wie in nicht mehr als 31 Zyklen in 95% der Aufrufe der binären Suchversion, verglichen mit nicht mehr als 28 Zyklen in 95% der Aufrufe der Bit-Hack-Version; beide laufen in 50% der Fälle innerhalb von 28 Zyklen ab. (Die Schleife Version dauert bis zu 56 Zyklen in 95% der Anrufe, bis zu 37 Zyklen Median.)
Um zu bestimmen, welche im tatsächlichen Code besser ist, müsste man einen richtigen Benchmark innerhalb der realen Aufgabe machen; zumindest bei aktuellen x86-64-Architekturprozessoren wird die Arbeit leicht in anderen Latenzen verborgen (wie Funktionsaufrufe).
Meine Antwort basiert hauptsächlich auf diese Implementierung einer 64-Bit-Wortauswahlmethode (Hinweis: Schauen Sie sich nur die Codepays MARISA_USE_POPCNT, MARISA_X64, MARISA_USE_SSE3 an):
Es funktioniert in zwei Schritten, indem zuerst das Byte ausgewählt wird, das das n-te gesetzte Bit enthält, und dann eine Nachschlagetabelle innerhalb des Bytes verwendet wird:
n an alle Bytes (SSE Broadcast oder erneut Multiplikation mit 0x01010101 ...) n ) Jetzt wissen wir, welches Byte das Bit enthält, und eine einfache Byte-Lookup-Tabelle wie in grek40s Antwort reicht aus, um das Ergebnis zu erhalten.
Beachten Sie jedoch, dass ich dieses Ergebnis nicht wirklich mit anderen Implementierungen verglichen habe, nur dass ich festgestellt habe, dass es ziemlich effizient (und nicht verzweigt) ist.
Bearbeiten
Nachdem ich einige Gedanken gemacht und die __builtin_popcount -Funktion verwendet habe, dachte ich, es wäre vielleicht besser, sich für das relevante Byte zu entscheiden und dann das ganze Ergebnis zu berechnen, anstatt Zahlen inkrementell zu addieren / subtrahieren. Hier ist eine aktualisierte Version:
Ich hatte das Gefühl, eine LUT-basierte Lösung zu erstellen, bei der die Anzahl in Byte-Chunks untersucht wird, die LUT für die n-te Bitposition wurde jedoch recht groß (256 * 8) und die LUT-freie Version, die diskutiert wurde die Kommentare könnten besser sein.
Im Allgemeinen würde der Algorithmus so aussehen:
%Vor%Es könnte sich lohnen, die Schleife in bis zu 4 Iterationen zu entpacken, um die beste Leistung bei 32-Bit-Zahlen zu erzielen.
Die LUT für Bitcount (könnte durch __builtin_popcount ersetzt werden):
Die LUT für die Bitposition innerhalb eines Bytes:
%Vor%Mein Ansatz besteht darin, die Bevölkerungszahl für jede 8-Bit-Viertel der 32-Bit-Ganzzahl parallel zu berechnen, Finde dann, welches Viertel das n-te Bit enthält. Die Bevölkerungszahl von Vierteln, die niedriger als die gefundene sind, kann als Anfangswert der späteren Berechnung zusammengefasst werden.
Nach dieser Zählung setzen Sie die Bits nacheinander, bis die n erreicht ist. Ohne Verzweigungen und mit einer unvollständigen Implementierung des Populationszählungsalgorithmus ist mein Beispiel wie folgt:
Ein einfacher Ansatz, der Schleifen und Bedingungen verwendet, kann auch der folgende sein:
%Vor% Basierend auf einer Methode von Juha Järvi, die in den berühmten Bit Twiddling Hacks veröffentlicht wurde, habe ich das getestet Implementierung wobei n und i wie in der Frage verwendet werden:
Nach meinen eigenen Tests ist das ungefähr so schnell wie die Schleife auf x86, während es bei arm64 um 20% schneller ist und aufgrund der schnellen bedingten Anweisungen wahrscheinlich viel schneller ist, aber ich kann das nicht richtig testen jetzt.
Tags und Links c bit-fiddling