Was ist der effizienteste Algorithmus, um Folgendes zu erreichen:
0010 0000 => 0000 0100
Die Konvertierung erfolgt von MSB-> LSB zu LSB-> MSB. Alle Bits müssen umgekehrt werden. Das heißt, dies ist kein Endianness-Swapping.
c
algorithm
bit-manipulation
green_t
quelle
quelle
Antworten:
HINWEIS : Alle unten aufgeführten Algorithmen sind in C, sollten jedoch in die Sprache Ihrer Wahl portierbar sein (sehen Sie mich nur nicht an, wenn sie nicht so schnell sind :)
Optionen
Geringer Speicher (32-Bit-
int
, 32-Bit-Computer) (von hier ):Von der berühmten Bit Twiddling Hacks-Seite :
Am schnellsten (Nachschlagetabelle) :
Sie können diese Idee auf 64-Bit-
int
Dateien erweitern oder den Speicher gegen Geschwindigkeit austauschen (vorausgesetzt, Ihr L1-Datencache ist groß genug) und 16 Bit gleichzeitig mit einer Nachschlagetabelle mit 64 KB-Einträgen umkehren.Andere
Einfach
Schneller (32-Bit-Prozessor)
Schneller (64-Bit-Prozessor)
Wenn Sie dies mit 32 Bit tun möchten
int
, kehren Sie einfach die Bits in jedem Byte um und kehren Sie die Reihenfolge der Bytes um. Das ist:Ergebnisse
Ich habe die beiden vielversprechendsten Lösungen verglichen, die Nachschlagetabelle und das bitweise UND (die erste). Die Testmaschine ist ein Laptop mit 4 GB DDR2-800 und einem Core 2 Duo T7500 mit 2,4 GHz und 4 MB L2-Cache. YMMV. Ich habe gcc 4.3.2 unter 64-Bit-Linux verwendet. OpenMP (und die GCC-Bindungen) wurden für hochauflösende Timer verwendet.
reverse.c
reverse_lookup.c
Ich habe beide Ansätze bei verschiedenen Optimierungen ausprobiert, 3 Versuche auf jeder Ebene durchgeführt und jeder Versuch 100 Millionen zufällige Versuche rückgängig gemacht
unsigned ints
. Für die Option für die Nachschlagetabelle habe ich beide Schemata (Optionen 1 und 2) ausprobiert, die auf der Seite für bitweise Hacks angegeben sind. Die Ergebnisse sind unten gezeigt.Bitweises UND
Nachschlagetabelle (Option 1)
Nachschlagetabelle (Option 2)
Fazit
Verwenden Sie die Nachschlagetabelle mit Option 1 (die Byteadressierung ist nicht überraschend langsam), wenn Sie Bedenken hinsichtlich der Leistung haben. Wenn Sie das letzte Byte Speicher aus Ihrem System herausholen müssen (und wenn Sie sich für die Leistung der Bitumkehr interessieren), sind die optimierten Versionen des bitweisen UND-Ansatzes auch nicht allzu schäbig.
Vorbehalt
Ja, ich weiß, dass der Benchmark-Code ein vollständiger Hack ist. Vorschläge zur Verbesserung sind mehr als willkommen. Dinge, die ich weiß:
ld
ist ein verrückter Fehler bei der Neudefinition von Symbolen aufgetreten ), daher glaube ich nicht, dass der generierte Code für meine Mikroarchitektur optimiert ist.32-Bit
EDIT: Ich habe es auch versucht
uint64_t
Typen auf meinem Computer zu verwenden, um festzustellen, ob es eine Leistungssteigerung gab. Die Leistung war etwa 10% schneller als die von 32-Bit und war nahezu identisch, unabhängig davon, ob Sie nur 64-Bit-Typen zum gleichzeitigen Umkehren von Bits auf zwei 32-Bit-int
Typen verwendeten oder ob Sie tatsächlich Bits in halb so vielen 64-Bit-Typen umkehrten. Bitwerte. Der Assembler-Code wird unten gezeigt (für den ersteren Fall Umkehren von Bits für zwei 32-Bit-int
Typen gleichzeitig):quelle
Dieser Thread hat meine Aufmerksamkeit erregt, da er sich mit einem einfachen Problem befasst, das selbst für eine moderne CPU viel Arbeit (CPU-Zyklen) erfordert. Und eines Tages stand ich auch mit dem gleichen ¤ #% "#" Problem da. Ich musste Millionen von Bytes umdrehen. Ich weiß jedoch, dass alle meine Zielsysteme auf modernem Intel basieren. Beginnen wir also mit der Optimierung auf das Äußerste !!!
Also habe ich Matt Js Lookup-Code als Basis verwendet. Das System, auf dem ich ein Benchmarking durchführe, ist ein i7 haswell 4700eq.
Matt Js Lookup-Bitflipping 400 000 000 Bytes: Ungefähr 0,272 Sekunden.
Ich ging dann voran und versuchte zu sehen, ob Intels ISPC-Compiler die Arithmetik in umgekehrter Reihenfolge vektorisieren konnte. C.
Ich werde Sie hier nicht mit meinen Erkenntnissen langweilen, da ich viel versucht habe, dem Compiler bei der Suche nach Dingen zu helfen. Trotzdem hatte ich eine Leistung von ungefähr 0,15 Sekunden, um 400 000 000 Bytes zu bitflippen. Es ist eine großartige Reduzierung, aber für meine Anwendung ist das immer noch viel zu langsam.
Die Leute ließen mich den schnellsten Intel-basierten Bitflipper der Welt vorstellen. Getaktet um:
Zeit zum Bitflip 400000000 Bytes: 0.050082 Sekunden !!!!!
Die printf's sind zum Debuggen ..
Hier ist das Arbeitstier:
Der Code benötigt 32 Bytes und maskiert dann die Knabbereien. Das hohe Halbbyte wird um 4 nach rechts verschoben. Dann verwende ich vpshufb und ymm4 / ymm3 als Nachschlagetabellen. Ich könnte eine einzelne Nachschlagetabelle verwenden, aber dann müsste ich nach links wechseln, bevor ich die Knabbereien wieder zusammenfügen kann.
Es gibt noch schnellere Möglichkeiten, die Bits umzudrehen. Aber ich bin an Single Thread und CPU gebunden, also war dies die schnellste, die ich erreichen konnte. Kannst du eine schnellere Version machen?
Bitte machen Sie keine Kommentare zur Verwendung der Intel C / C ++ Compiler Intrinsic Equivalent-Befehle ...
quelle
pshub
, denn schließlich wird auch der beste Popcount damit gemacht! Ich hätte es hier geschrieben, wenn nicht für dich. Ein großes Lob.popcnt
,tzcnt
undpext
alle an Port 1. Also kostet jederpext
oder jedertzcnt
Sie einenpopcnt
Durchsatz. Wenn Ihre Daten im L1D-Cache heiß sind, können Sie ein Array auf Intel-CPUs am schnellsten mit AVX2 pshufb zählen. (Ryzen hat einenpopcnt
Durchsatz von 4 pro Takt , das ist wahrscheinlich optimal, aber die Bulldozer-Familie hat einen Durchsatz von 4 pro Taktpopcnt r64,r64
... agner.org/optimize ).Dies ist eine weitere Lösung für Leute, die Rekursion lieben.
Die Idee ist einfach. Teilen Sie die Eingabe durch die Hälfte und tauschen Sie die beiden Hälften aus. Fahren Sie fort, bis das einzelne Bit erreicht ist.
Hier ist eine rekursive Funktion, um es zu lösen. (Hinweis: Ich habe vorzeichenlose Ints verwendet, damit es für Eingaben bis zu einer Größe von (vorzeichenlosen Int) * 8 Bit verwendet werden kann.
Dies ist die Ausgabe:
quelle
numBits
ist int, wenn Sie 3 durch 2 für den Funktionsparameter teilen, wird es auf 1 abgerundet?Nun, dies wird sicherlich keine Antwort wie die von Matt J sein, aber hoffentlich wird es immer noch nützlich sein.
Dies ist genau die gleiche Idee wie bei Matts bestem Algorithmus, außer dass es diesen kleinen Befehl namens BSWAP gibt, der die Bytes (nicht die Bits) einer 64-Bit-Zahl vertauscht. So wird aus b7, b6, b5, b4, b3, b2, b1, b0 b0, b1, b2, b3, b4, b5, b6, b7. Da wir mit einer 32-Bit-Nummer arbeiten, müssen wir unsere bytegetauschte Nummer um 32 Bit nach unten verschieben. Dies lässt uns nur die Aufgabe, die 8 Bits jedes Bytes auszutauschen, was erledigt ist und voila! Wir sind fertig.
Timing: Auf meinem Computer lief Matts Algorithmus in ~ 0,52 Sekunden pro Versuch. Meins lief in ungefähr 0,42 Sekunden pro Versuch. 20% schneller ist nicht schlecht, denke ich.
Wenn Sie sich Sorgen über die Verfügbarkeit der Anweisung BSWAP Wikipedia machen listet den Befehl BSWAP als mit 80846 hinzugefügt auf, der 1989 herauskam. Es sollte beachtet werden, dass Wikipedia auch angibt, dass dieser Befehl nur mit 32-Bit-Registern funktioniert, was eindeutig nicht der Fall ist Fall auf meinem Computer funktioniert es sehr viel nur auf 64-Bit-Registern.
Diese Methode funktioniert für jeden integralen Datentyp gleich gut, sodass die Methode trivial verallgemeinert werden kann, indem die gewünschte Anzahl von Bytes übergeben wird:
was dann wie folgt aufgerufen werden kann:
Der Compiler sollte in der Lage sein, den zusätzlichen Parameter zu optimieren (vorausgesetzt, der Compiler integriert die Funktion), und für den
sizeof(size_t)
Fall würde die Rechtsverschiebung vollständig entfernt. Beachten Sie, dass GCC zumindest nicht in der Lage ist, BSWAP und Rechtsverschiebung zu entfernen, wenn es bestanden wirdsizeof(char)
.quelle
unsigned long long int
die mindestens 64 Bit sein müssen, wie hier und hierDie Antwort von Anders Cedronius bietet eine großartige Lösung für Benutzer mit einer x86-CPU mit AVX2-Unterstützung. Für x86-Plattformen ohne AVX-Unterstützung oder Nicht-x86-Plattformen sollte eine der folgenden Implementierungen gut funktionieren.
Der erste Code ist eine Variante der klassischen binären Partitionierungsmethode, die so codiert ist, dass die Verwendung des auf verschiedenen ARM-Prozessoren nützlichen Shift-Plus-Logik-Idioms maximiert wird. Darüber hinaus wird die On-the-Fly-Maskengenerierung verwendet, was für RISC-Prozessoren von Vorteil sein kann, die ansonsten mehrere Anweisungen zum Laden jedes 32-Bit-Maskenwerts benötigen. Compiler für x86-Plattformen sollten eine konstante Weitergabe verwenden, um alle Masken zur Kompilierungszeit und nicht zur Laufzeit zu berechnen.
In Band 4A von "The Art of Computer Programming" zeigt D. Knuth clevere Möglichkeiten zum Umkehren von Bits, die überraschenderweise weniger Operationen erfordern als die klassischen binären Partitionierungsalgorithmen. Ein solcher Algorithmus für 32-Bit-Operanden, den ich in TAOCP nicht finden kann, wird in diesem Dokument auf der Hacker's Delight-Website gezeigt.
Mit dem Intel Compiler C / C ++ - Compiler 13.1.3.198 werden beide oben genannten Funktionen automatisch vektorisiert
XMM
Registerregister . Sie können auch ohne großen Aufwand manuell vektorisiert werden.Auf meinem IvyBridge Xeon E3 1270v2 wurden unter Verwendung des automatisch vektorisierten Codes 100 Millionen
uint32_t
Wörter in 0,070 Sekunden mitbrev_classic()
und 0,068 Sekunden mit bitumgekehrtbrev_knuth()
. Ich habe darauf geachtet, dass mein Benchmark nicht durch die Bandbreite des Systemspeichers begrenzt ist.quelle
brev_knuth()
? Die Zuschreibung im PDF von Hacker's Delight scheint darauf hinzudeuten, dass diese Zahlen direkt von Knuth selbst stammen. Ich kann nicht behaupten, Knuths Beschreibung der zugrunde liegenden Entwurfsprinzipien in TAOCP ausreichend verstanden zu haben, um zu erklären, wie die Konstanten abgeleitet wurden oder wie man die abgeleiteten Konstanten und Verschiebungsfaktoren für beliebige Wortgrößen vorgehen würde.Angenommen, Sie haben ein Array von Bits, wie wäre es damit: 1. Schieben Sie die Bits ausgehend von MSB nacheinander in einen Stapel. 2. Pop-Bits von diesem Stapel in ein anderes Array (oder dasselbe Array, wenn Sie Platz sparen möchten), platzieren Sie das erste Popped-Bit in MSB und fahren Sie von dort aus mit weniger signifikanten Bits fort.
quelle
Der native ARM-Befehl "rbit" kann dies mit 1 CPU-Zyklus und 1 zusätzlichen CPU-Register tun, was unschlagbar ist.
quelle
Für einen Menschen ist das kein Job! ... aber perfekt für eine Maschine
Dies ist 2015, 6 Jahre nachdem diese Frage zum ersten Mal gestellt wurde. Compiler sind seitdem unsere Meister geworden, und unsere Aufgabe als Mensch ist es nur, ihnen zu helfen. Was ist der beste Weg, um der Maschine unsere Absichten zu geben?
Bit-Umkehrung ist so häufig, dass Sie sich fragen müssen, warum die ständig wachsende ISA des x86 keine Anweisung enthält, dies auf einmal zu tun.
Der Grund: Wenn Sie dem Compiler Ihre wahre, präzise Absicht geben, sollte die Bitumkehr nur ~ 20 CPU-Zyklen dauern . Lassen Sie mich Ihnen zeigen, wie Sie reverse () herstellen und verwenden:
Das Kompilieren dieses Beispielprogramms mit der Clang-Version> = 3.6, -O3, -march = native (getestet mit Haswell) liefert Code in Grafikqualität unter Verwendung der neuen AVX2-Anweisungen mit einer Laufzeit von 11 Sekunden , die ~ 1 Milliarde reverse () s verarbeitet. Das sind ~ 10 ns pro Umkehrung (), wobei ein CPU-Zyklus von 0,5 ns bei 2 GHz die süßen 20 CPU-Zyklen erreicht.
Vorsichtsmaßnahme: Dieser Beispielcode sollte einige Jahre lang als anständiger Maßstab dienen, aber er wird irgendwann sein Alter zeigen, sobald die Compiler klug genug sind, main () zu optimieren, um nur das Endergebnis auszudrucken, anstatt wirklich etwas zu berechnen. Aber im Moment funktioniert es, um reverse () zu präsentieren.
quelle
Bit-reversal is so common...
Das weiß ich nicht. Ich arbeite mit Code, der praktisch jeden Tag mit Daten auf Bitebene umgeht, und ich kann mich nicht erinnern, jemals dieses spezielle Bedürfnis gehabt zu haben. In welchen Szenarien brauchen Sie es? - Nicht, dass es kein interessantes Problem wäre, es selbst zu lösen.Natürlich ist die offensichtliche Quelle für Bit-Twiddling-Hacks hier: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
quelle
Ich weiß, es ist nicht C, sondern asm:
Dies funktioniert mit dem Übertragsbit, sodass Sie auch Flags speichern können
quelle
rcl
CF verschiebenvar1
, anstatt nurshl
Flags zu lesen. (Oderadc dx,dx
). Selbst mit diesem Fix ist dies lächerlich langsam, wenn man die langsameloop
Anweisung verwendet undvar1
im Gedächtnis bleibt ! Eigentlich denke ich, dass dies die Ausgabe in AX erzeugen soll, aber es speichert / stellt den alten Wert von AX über dem Ergebnis wieder her.Implementierung mit wenig Speicher und am schnellsten.
quelle
Nun, dies ist im Grunde dasselbe wie das erste "reverse ()", aber es ist 64 Bit und benötigt nur eine sofortige Maske, um aus dem Befehlsstrom geladen zu werden. GCC erstellt Code ohne Sprünge, daher sollte dies ziemlich schnell gehen.
quelle
Ich war gespannt, wie schnell die offensichtliche Rohrotation sein würde. Auf meinem Computer (i7 @ 2600) lag der Durchschnitt für 1.500.150.000 Iterationen
27.28 ns
(über einen zufälligen Satz von 131.071 64-Bit-Ganzzahlen).Vorteile: Der Speicherbedarf ist gering und der Code einfach. Ich würde sagen, es ist auch nicht so groß. Die erforderliche Zeit ist für jede Eingabe vorhersehbar und konstant (128 arithmetische SHIFT-Operationen + 64 logische UND-Operationen + 64 logische ODER-Operationen).
Ich habe mit der besten Zeit verglichen, die @Matt J erhalten hat - der die akzeptierte Antwort hat. Wenn ich seine Antwort richtig lese, ist das Beste, was er hat,
0.631739
Sekunden für1,000,000
Iterationen, was zu einem Durchschnitt von631 ns
pro Umdrehung führt.Das Code-Snippet, das ich verwendet habe, ist das folgende:
quelle
Möglicherweise möchten Sie die Standardvorlagenbibliothek verwenden. Es ist möglicherweise langsamer als der oben genannte Code. Es scheint mir jedoch klarer und leichter zu verstehen.
quelle
Generisch
C-Code. Verwenden Sie als Beispiel die 1-Byte-Eingabedaten num.
quelle
Wie wäre es mit folgendem:
Klein und einfach (allerdings nur 32 Bit).
quelle
Ich dachte, dies ist einer der einfachsten Wege, um das Bit umzukehren. Bitte lassen Sie mich wissen, wenn diese Logik fehlerhaft ist. Grundsätzlich überprüfen wir in dieser Logik den Wert des Bits in Position. Setzen Sie das Bit, wenn der Wert in umgekehrter Position 1 ist.
quelle
quelle
k
ist immer eine Potenz von 2, aber Compiler werden das wahrscheinlich nicht beweisen und es in Bit-Scan / Shift umwandeln.Ich denke, die einfachste Methode, die ich kenne, folgt.
MSB
ist Eingabe undLSB
ist 'umgekehrte' Ausgabe:quelle
quelle
Eine weitere schleifenbasierte Lösung, die schnell beendet wird, wenn die Anzahl niedrig ist (in C ++ für mehrere Typen).
oder in C für ein vorzeichenloses int
quelle
Es scheint, dass viele andere Beiträge über die Geschwindigkeit besorgt sind (dh am besten = am schnellsten). Was ist mit Einfachheit? Erwägen:
und hoffe, dass der clevere Compiler für Sie optimiert.
Wenn Sie eine längere Liste von Bits (die
sizeof(char) * n
Bits enthalten ) umkehren möchten , können Sie diese Funktion verwenden, um Folgendes zu erhalten:Dies würde [10000000, 10101010] in [01010101, 00000001] umkehren.
quelle
ith_bit = (c >> i) & 1
. Auch speichert SUB durch Verschiebenreversed_char
statt das Stück verschoben wird , es sei denn , Sie hoffen , es auf x86 kompilieren wirdsub something
/bts reg,reg
das n - te Bit im Zielregister zu setzen.Bitumkehr im Pseudocode
Quelle -> umzukehrendes Byte b00101100 Ziel -> umgekehrt, muss ebenfalls vom Typ ohne Vorzeichen sein, damit das Vorzeichenbit nicht nach unten übertragen wird
Kopieren in Temp, damit das Original nicht betroffen ist. Es muss auch vom Typ ohne Vorzeichen sein, damit das Vorzeichenbit nicht automatisch verschoben wird
LOOP8: // Diesen 8-maligen Test durchführen, wenn die Bytekopie <0 ist (negativ)
quelle
Meine einfache Lösung
quelle
i
? Was ist diese magische Konstante* 4
? Ist esCHAR_BIT / 2
?Dies ist für 32 Bit, wir müssen die Größe ändern, wenn wir 8 Bit berücksichtigen.
Lesen der Eingabe-Ganzzahl "num" in der Reihenfolge LSB-> MSB und Speichern in num_reverse in der Reihenfolge MSB-> LSB.
quelle
quelle