Das mache ich gerade:
%Vor%Wirklich scheußlich, ich weiß, und es bringt Leistung.
Was ist der schnellste Weg, den Bit-Offset des ersten Satzes von x aufeinanderfolgende 0 Bits in einem char-Array zu finden, wobei 0 < x < 7 ? Ich bin auf GCC mit SSE 4.2 so eingebaut wie __builtin_ctz, __builtin_popcountl sind eine Option, ich kann einfach nicht herausfinden, die beste Art, sie zu verwenden.
Wie viele Nummern haben 6 aufeinanderfolgende 0 Bits (auch wenn 2 aufeinanderfolgende Bytes berücksichtigt werden)?
%Vor%Wenn wir also 1 Byte gleichzeitig betrachten, dann 0/1/2/3/64/128/192
%Vor% Also ein absolutes Maximum von 12 Tests gibt Ihnen alle Kombinationen.
Ich bin sicher, wenn Sie die Vergleiche klug machen, können Sie das reduzieren.
Wenn wir @ Michael Burr Lösung unten für einen tabellengesteuerten Ansatz verwenden. Dann können wir es so organisieren, dass Sie einen oder zwei Vergleiche pro Byte durchführen können.
%Vor%Erste paar Tabelleneinträge:
%Vor%Hier ist eine Funktion, die der Ausgabe der in der Frage angegebenen entspricht (zumindest bei eingeschränkten Tests). Es verwendet eine Tabellensuche, wobei die Tabelle von einem einmaligen Skript generiert wurde. Ich bin ehrlich gesagt nicht sicher, ob seine Leistung mit den Vorschlägen konkurriert, die Bit-Test-Hacker oder GCC-Built-Ins verwenden, aber ich wette, es ist nicht allzu weit weg.
%Vor% Iterate durch das Array Wort für Wort (32-Bit oder 64-Bit hängt von Ihrem Bogen ab). Verwenden Sie __builtin_clz und __builtin_ctz , um die führenden und abschließenden Nullen für jedes Wort zu berechnen.
Es gibt zwei Fälle von aufeinanderfolgenden Nullen:
Der erste Fall ist leicht zu überprüfen. Im zweiten Fall muss geprüft werden, ob führende Nullen dieses Elements + nachfolgende Nullen des vorherigen Elements & gt; = 6 sind.
Beachten Sie diese arithmetischen Tricks:
%Vor%Also wäre ein möglicher Algorithmus, diese Tricks mit großer Ganzzahlarithmetik zu verwenden und loop bis Länge == 0 (kein Loch mehr) oder Länge & gt; = n (Sie starten nächste Schleife mit x = z;).
Sie können die große Ganzzahl selbst emulieren, indem Sie Byte für Byte auf die Auflistung anwenden und anhalten, wenn kein Übertrag mehr vorhanden ist.
Dies würde so etwas geben:
%Vor%Sie können es effizienter machen, indem Sie länger als ein Byte für die Basissammlung verwenden ...
BEARBEITEN: beschleunigen, wenn Sie eine feste Größe für Nzero wie 6
haben
Der obige Algorithmus wiederholt alle Löcher und kann bei kleinen Löchern Zeit verlieren.
Sie können dies vermeiden, indem Sie einen vorberechneten Tisch mit kleinen Löchern füllen.
Zum Beispiel hat 10010101 3 Löcher, die zu kurz sind, so dass Sie sie durch 11111111 ersetzen können.
Aber Sie müssen führende und nachfolgende Nullen unverändert beibehalten.
Um eine solche Tabelle zu initialisieren, nehmen Sie einfach 0xFF und xor mit einer Maske, die 1 Bits anstelle von abschließenden Nullen (x|(x-1))^x enthält, und einer Maske mit 1 Bits anstelle von führenden Nullen ((1<<highbit(x))-1)^0xFF .
Fügen Sie eine Ausnahme für 10000001 hinzu, wobei das einzige Byte 6 Nullen zwischen Einsen enthält.
EDIT2 : Ich habe die Bitsequenz zuerst mit dem niedrigstwertigen Bit des ersten Bytes behandelt, was gut zur arithmetischen Vorgehensweise passt. Die Frage verwendet explizit das höchstwertige Bit des ersten Bytes zuerst. Also muss ich die Bits umkehren, um die Frage zu erfüllen, die während der Initialisierung der Tabelle gemacht wird ...
%Vor% Dann ersetzen Sie einfach die Vorkommen von x=bits[ i ] durch x=fillShortHoles[ bits[ i ] ] , und Sie sind fertig:
EDIT3: Schließlich wäre für nzero & lt; = 9 ein schnellerer Weg, die Position für jedes Byte-Paar zu cachen.
%Vor%Beachten Sie, dass die Initialisierung x = 0xFF die Fälle von nbytes & lt; 2.
behandeltUnabhängig davon, wie Sie die Cacheposition füllen, wird es nur bei der Initialisierung aufgerufen. Ich schlage natürlich den arithmetischen Weg vor:
%Vor%Für ein Byte müssen Sie nur 3 Tests durchführen:
%Vor% Es sollte relativ einfach sein, dies auf weitere Werte auszuweiten. Zum Beispiel für uint32_t :
Der obige Code sieht nicht nach dem besten Weg aus (weil es das wahrscheinlich nicht ist). Ich habe es absichtlich so geschrieben, um es einfacher zu sehen, wie es mit SSE gemacht werden kann. Für SSE wäre es ähnlich wie oben (aber breiter).
Allerdings können Sie für SSE alle Vergleiche parallel durchführen und viele Zweige loswerden. Zum Beispiel könnten Sie UND mit jeder der 3 Masken und verwenden Sie PCMPEQB 3 mal und dann ODER diese Ergebnisse zusammen, dann tun Sie ein PMOVMSKB ; Das würde Ihnen einen 16-Bit-Wert geben (der 16 Bytes repräsentiert - ein Bit pro Quellbyte), der mit einem einzelnen if(result_flags == 0) { /* None of the 16 bytes matched */ } getestet werden kann, wobei dieser letzte Test am Ende einer "do / while" -Schleife sein könnte / p>
Angenommen, Sie suchen nach genau 6 aufeinander folgenden Nullen. Sie könnten ein Code-Snippet wie folgt verwenden:
%Vor% d1 kombiniert das letzte Byte des vorherigen Laufs mit drei neuen Bytes. So können Sie Ihre Daten in Vielfachen von 3 iterieren. Sie könnten Vielfache von 2 versuchen, was effizienter sein könnte, da Sie Ihre Daten als 16-Bit-Atomgrößen behandeln können. Sie können auch Vielfache von 4 versuchen und die nachfolgende Berechnung auf 64-Bit-Zahlen durchführen, insbesondere wenn Sie auf einer 64-Bit-Plattform arbeiten. Oder Sie führen einen Sonderfall für Nullsequenzen ein, die Bytes umfassen.
d2 kehrt das Bitmuster um, was nützlich ist, weil Verschiebungen künstliche Nullen, aber keine künstlichen Nullen einführen. d3 sucht nach drei übereinstimmenden Einsen, bei den Offsets 0, 2 und 4. d4 fügt dann ein weiteres Offset-Bit hinzu und kombiniert damit alle Offsets von 0 bis 5. So wird d4 genau dann nicht Null ist eine Folge von 6 aufeinanderfolgenden Nullen in d1 . Sie können dann __builtin_clz verwenden, um den Ort des höchstwertigen in d4 zu identifizieren, der auch die Position des ersten dieser 6 Bits in d1 ist. Von diesem können Sie die Position in data erhalten.
Sie können den Code an andere Lauflängen anpassen, entweder indem Sie eine Schleife hinzufügen und hoffen, dass der Compiler sie optimiert, oder indem Sie eine Inline-Template-Funktion zur Verfügung stellen, die d4 von d2 in einer für die gewünschte Lauflänge.
Lass mich versuchen - wie wäre es mit:
%Vor%Das war nur zum Spaß ...
Nun, wenn Sie wirklich etwas Leistung ausdrücken möchten, werde ich vorschlagen
%Vor%Dies ist ziemlich schwierig zu lesen, aber das Konzept ist einfach - iterieren Sie einfach über jeden int-großen Block und für jeden sehen Sie, ob führende Nullen + nachfolgende Nullen von vorherigem & gt; = n sind. Wenn nicht nur führende Nullen und nachfolgende Einsen wiederholt werden (gesetzte Bits), und nochmals auf abschließende Nullen & gt; = n geprüft wird, solange wir nicht zu nachlaufenden Bytes gelangen.
Und nur noch eine Idee:
%Vor% Sie könnten versucht sein, einen Zeiger auf Variablen, die sich noch im Puffer befinden, direkt auf das Wort ( reinterpret_cast<unsigned short int*>(buffer[i]) ) zu setzen und Masken ohne Union anzuwenden. Beachten Sie jedoch, dass bei der Hälfte dieser Operationen nicht ausgerichtete Variablen verwendet werden, die die Leistung beeinträchtigen und auf einigen Plattformen sogar Ausnahmen generieren können.
Tags und Links algorithm c c++ bit-manipulation bit