Ich habe versucht, C in meiner Freizeit zu lernen, und andere Sprachen (C #, Java usw.) haben das gleiche Konzept (und oft die gleichen Operatoren) ...
Was ich frage mich ist, bei einer Kern Ebene, was bedeutet Bit-Verschiebung ( <<
, >>
, >>>
) zu tun, welche Probleme kann es lösen helfen, und was gotchas lauert die Biegung herum? Mit anderen Worten, ein absoluter Anfängerleitfaden für Bit Shifting in all seiner Güte.
operators
bit-manipulation
bit-shift
binary-operators
John Rudy
quelle
quelle
Antworten:
Die Bitverschiebungsoperatoren tun genau das, was ihr Name impliziert. Sie verschieben Bits. Hier ist eine kurze (oder nicht so kurze) Einführung in die verschiedenen Schichtbetreiber.
Die Betreiber
>>
ist der arithmetische (oder vorzeichenbehaftete) Rechtsverschiebungsoperator.>>>
ist der logische (oder vorzeichenlose) Rechtsschichtoperator.<<
ist der Linksverschiebungsoperator und erfüllt die Anforderungen sowohl logischer als auch arithmetischer Verschiebungen.Alle diese Operatoren können auf ganzzahlige Werte angewendet werden (
int
,long
, gegebenenfallsshort
undbyte
oderchar
). In einigen Sprachen wirdint
der Operand durch Anwenden der Verschiebungsoperatoren auf einen beliebigen Datentyp, der kleiner als automatisch ist, automatisch geändertint
.Beachten Sie, dass dies
<<<
kein Operator ist, da er redundant wäre.Beachten Sie auch, dass C und C ++ nicht zwischen den rechten Schichtoperatoren unterscheiden . Sie stellen nur den
>>
Operator bereit , und das Rechtsverschiebungsverhalten ist die für signierte Typen definierte Implementierung. Der Rest der Antwort verwendet die C # / Java-Operatoren.(In allen gängigen C- und C ++ - Implementierungen, einschließlich GCC und Clang / LLVM, sind
>>
signierte Typen arithmetisch. Einige Codes setzen dies voraus, dies wird jedoch vom Standard nicht garantiert. Es ist jedoch nicht undefiniert . Der Standard erfordert Implementierungen, um ihn zu definieren So oder so. Linksverschiebungen von negativ vorzeichenbehafteten Zahlen sind jedoch undefiniertes Verhalten (vorzeichenbehafteter Ganzzahlüberlauf). Wenn Sie also keine arithmetische Rechtsverschiebung benötigen, ist es normalerweise eine gute Idee, Ihre Bitverschiebung mit vorzeichenlosen Typen durchzuführen.)Linksverschiebung (<<)
Ganzzahlen werden im Speicher als eine Reihe von Bits gespeichert. Die als 32-Bit gespeicherte Nummer 6
int
wäre beispielsweise:Wenn Sie dieses Bitmuster um eine Position (
6 << 1
) nach links verschieben, erhalten Sie die Nummer 12:Wie Sie sehen können, haben sich die Ziffern um eine Position nach links verschoben, und die letzte Ziffer rechts ist mit einer Null gefüllt. Sie können auch feststellen, dass das Verschieben nach links einer Multiplikation mit Potenzen von 2
6 << 1
entspricht . Dies entspricht also6 * 2
und6 << 3
entspricht6 * 8
. Ein guter optimierender Compiler ersetzt Multiplikationen nach Möglichkeit durch Verschiebungen.Nicht kreisförmige Verschiebung
Bitte beachten Sie, dass dies keine Kreisverschiebungen sind. Verschieben Sie diesen Wert um eine Position nach links (
3,758,096,384 << 1
):Ergebnisse in 3.221.225.472:
Die Ziffer, die "vom Ende" verschoben wird, geht verloren. Es wickelt sich nicht herum.
Logische Rechtsverschiebung (>>>)
Eine logische Rechtsverschiebung ist die Umkehrung zur Linksverschiebung. Anstatt Bits nach links zu verschieben, bewegen sie sich einfach nach rechts. Zum Beispiel die Nummer 12 verschieben:
rechts um eine Position (
12 >>> 1
) erhalten wir unsere ursprüngliche 6 zurück:Wir sehen also, dass eine Verschiebung nach rechts einer Division durch Potenzen von 2 entspricht.
Verlorene Teile sind weg
Eine Verschiebung kann jedoch keine "verlorenen" Bits zurückfordern. Wenn wir zum Beispiel dieses Muster verschieben:
links 4 Positionen (
939,524,102 << 4
) erhalten wir 2.147.483.744:und dann zurückschalten (
(939,524,102 << 4) >>> 4
) erhalten wir 134.217.734:Wir können unseren ursprünglichen Wert nicht zurückerhalten, wenn wir Bits verloren haben.
Arithmetische Rechtsverschiebung (>>)
Die arithmetische Rechtsverschiebung entspricht genau der logischen Rechtsverschiebung, außer dass anstelle des Auffüllens mit Null das höchstwertige Bit aufgefüllt wird. Dies liegt daran, dass das höchstwertige Bit das Vorzeichenbit oder das Bit ist, das positive und negative Zahlen unterscheidet. Durch Auffüllen mit dem höchstwertigen Bit bleibt die arithmetische Rechtsverschiebung vorzeichenerhaltend.
Wenn wir dieses Bitmuster beispielsweise als negative Zahl interpretieren:
Wir haben die Nummer -2.147.483.552. Wenn wir dies mit der arithmetischen Verschiebung (-2.147.483.552 >> 4) um 4 Positionen nach rechts verschieben, erhalten wir:
oder die Nummer -134,217,722.
Wir sehen also, dass wir das Vorzeichen unserer negativen Zahlen beibehalten haben, indem wir die arithmetische Rechtsverschiebung anstelle der logischen Rechtsverschiebung verwenden. Und wieder sehen wir, dass wir eine Division durch Potenzen von 2 durchführen.
quelle
A good optimizing compiler will substitute shifts for multiplications when possible.
Was? Bitshifts sind um Größenordnungen schneller, wenn es um die Low-Level-Operationen einer CPU geht. Ein guter optimierender Compiler würde genau das Gegenteil tun , dh gewöhnliche Multiplikationen mit Zweierpotenzen in Bitverschiebungen umwandeln.Nehmen wir an, wir haben ein einzelnes Byte:
Das Anwenden einer einzelnen linken Bitverschiebung bringt uns:
Die Null ganz links wurde aus dem Byte heraus verschoben, und eine neue Null wurde an das rechte Ende des Bytes angehängt.
Die Bits rollen nicht über; Sie werden verworfen. Das heißt, wenn Sie die Schicht 1101100 nach links und dann nach rechts verschieben, erhalten Sie nicht das gleiche Ergebnis zurück.
Schalten durch N links äquivalent von 2 bis Multiplizieren N .
Das Verschieben nach rechts um N ist (wenn Sie das Einsenkomplement verwenden ) das Äquivalent zum Teilen durch 2 N und Runden auf Null.
Bitshifting kann für wahnsinnig schnelle Multiplikation und Division verwendet werden, vorausgesetzt, Sie arbeiten mit einer Potenz von 2. Fast alle Low-Level-Grafikroutinen verwenden Bitshifting.
Zum Beispiel haben wir früher den Modus 13h (320x200 256 Farben) für Spiele verwendet. Im Modus 13h wurde der Videospeicher nacheinander pro Pixel angeordnet. Um den Ort für ein Pixel zu berechnen, würden Sie die folgende Mathematik verwenden:
Damals war die Geschwindigkeit entscheidend, daher verwendeten wir Bit-Shifts, um diesen Vorgang durchzuführen.
320 ist jedoch keine Zweierpotenz. Um dies zu umgehen, müssen wir herausfinden, was eine Zweierpotenz ist, die zusammen 320 ergibt:
Jetzt können wir das in Linksverschiebungen umwandeln:
Für ein Endergebnis von:
Jetzt erhalten wir den gleichen Versatz wie zuvor, außer dass wir anstelle einer teuren Multiplikationsoperation die beiden Bitverschiebungen verwenden ... in x86 wäre es ungefähr so (Hinweis, es ist für immer her, seit ich die Montage durchgeführt habe (Anmerkung des Herausgebers: korrigiert) ein paar Fehler und ein 32-Bit-Beispiel hinzugefügt)):
Insgesamt: 28 Zyklen auf einer alten CPU mit diesen Timings.
Vrs
12 Zyklen auf derselben alten CPU.
Ja, wir würden so hart arbeiten, um 16 CPU-Zyklen zu sparen.
Im 32- oder 64-Bit-Modus werden beide Versionen viel kürzer und schneller. Moderne Out-of-Order-Ausführungs-CPUs wie Intel Skylake (siehe http://agner.org/optimize/ ) weisen eine sehr schnelle Hardware-Multiplikation auf (geringe Latenz und hoher Durchsatz), sodass die Verstärkung viel geringer ist. Die AMD Bulldozer-Familie ist etwas langsamer, insbesondere für die 64-Bit-Multiplikation. Auf Intel-CPUs und AMD Ryzen bedeuten zwei Schichten eine etwas geringere Latenz, aber mehr Anweisungen als eine Multiplikation (was zu einem geringeren Durchsatz führen kann):
vs.
Compiler erledigen dies für Sie: Sehen Sie, wie GCC, Clang und Microsoft Visual C ++ bei der Optimierung alle Shift + Lea verwenden
return 320*row + col;
.Das Interessanteste dabei ist, dass x86 über eine Shift-and-Add-Anweisung (
LEA
) verfügt , die kleine Linksverschiebungen ausführen und gleichzeitig hinzufügen kann, wobei die Leistung eineadd
Anweisung ist. ARM ist noch leistungsfähiger: Ein Operand einer Anweisung kann kostenlos nach links oder rechts verschoben werden. Die Skalierung mit einer Kompilierungszeitkonstante, die als Zweierpotenz bekannt ist, kann also noch effizienter sein als eine Multiplikation.OK, früher ... etwas Nützlicheres wäre jetzt, Bitshifting zu verwenden, um zwei 8-Bit-Werte in einer 16-Bit-Ganzzahl zu speichern. Zum Beispiel in C #:
In C ++ sollten Compiler dies für Sie tun, wenn Sie a
struct
mit zwei 8-Bit-Mitgliedern verwendet haben, in der Praxis jedoch nicht immer.quelle
c=4*d
Sie eine Schicht. Wenn Sie schreibenk = (n<0)
, kann dies auch mit Schichten geschehen:k = (n>>31)&1
um eine Verzweigung zu vermeiden. Unterm Strich bedeutet diese Verbesserung der Cleverness von Compilern, dass diese Tricks jetzt nicht mehr im C-Code verwendet werden müssen und die Lesbarkeit und Portabilität beeinträchtigen. Immer noch sehr gut, sie zu kennen, wenn Sie zB SSE-Vektorcode schreiben; oder in jeder Situation, in der Sie es schnell brauchen und es einen Trick gibt, den der Compiler nicht verwendet (z. B. GPU-Code).if(x >= 1 && x <= 9)
kann Folgendes getan werden, da dasif( (unsigned)(x-1) <=(unsigned)(9-1))
Ändern von zwei bedingten Tests zu einem großen Geschwindigkeitsvorteil sein kann. insbesondere, wenn eine prädizierte Ausführung anstelle von Verzweigungen möglich ist. Ich habe dies jahrelang verwendet (wo dies gerechtfertigt war), bis ich vor ungefähr 10 Jahren bemerkte, dass Compiler begonnen hatten, diese Transformation im Optimierer durchzuführen, und dann hörte ich auf. Immer noch gut zu wissen, da es ähnliche Situationen gibt, in denen der Compiler die Transformation nicht für Sie durchführen kann. Oder wenn Sie an einem Compiler arbeiten.Bitweise Operationen, einschließlich Bitverschiebung, sind für Hardware auf niedriger Ebene oder eingebettete Programmierung von grundlegender Bedeutung. Wenn Sie eine Spezifikation für ein Gerät oder sogar einige binäre Dateiformate lesen, werden Bytes, Wörter und Wörter angezeigt, die in nicht byteorientierte Bitfelder unterteilt sind, die verschiedene interessante Werte enthalten. Der Zugriff auf diese Bitfelder zum Lesen / Schreiben ist die häufigste Verwendung.
Ein einfaches reales Beispiel in der Grafikprogrammierung ist, dass ein 16-Bit-Pixel wie folgt dargestellt wird:
Um den grünen Wert zu erreichen, würden Sie Folgendes tun:
Erläuterung
Um den Wert von NUR Grün zu erhalten, der bei Offset 5 beginnt und bei 10 endet (dh 6 Bit lang), müssen Sie eine (Bit-) Maske verwenden, die bei Anwendung auf das gesamte 16-Bit-Pixel ergibt nur die Teile, die uns interessieren.
Die entsprechende Maske ist 0x7E0, was in Binärform 0000011111100000 ist (was 2016 in Dezimalzahl ist).
Um eine Maske anzuwenden, verwenden Sie den AND-Operator (&).
Nach dem Anwenden der Maske erhalten Sie eine 16-Bit-Nummer, die eigentlich nur eine 11-Bit-Nummer ist, da sich das MSB im 11. Bit befindet. Grün ist eigentlich nur 6 Bit lang, daher müssen wir es mit einer Rechtsverschiebung (11 - 6 = 5) verkleinern, daher die Verwendung von 5 als Offset (
#define GREEN_OFFSET 5
).Ebenfalls üblich ist die Verwendung von Bitverschiebungen zur schnellen Multiplikation und Division durch Potenzen von 2:
quelle
Bit Masking & Shifting
Bitverschiebung wird häufig in der Grafikprogrammierung auf niedriger Ebene verwendet. Zum Beispiel ein gegebener Pixelfarbwert, der in einem 32-Bit-Wort codiert ist.
Zum besseren Verständnis wird derselbe Binärwert angegeben, der mit welchen Abschnitten welchen Farbteil darstellt.
Angenommen, wir möchten den Grünwert der Farbe dieses Pixels ermitteln. Wir können diesen Wert leicht durch Maskieren und Verschieben erhalten .
Unsere Maske:
Der logische
&
Operator stellt sicher, dass nur die Werte beibehalten werden, bei denen die Maske 1 ist. Das Letzte, was wir jetzt tun müssen, ist, den richtigen ganzzahligen Wert zu erhalten, indem alle diese Bits um 16 Stellen nach rechts verschoben werden (logische Rechtsverschiebung) .Et voilà, wir haben die Ganzzahl, die die Menge an Grün in der Farbe des Pixels darstellt:
Dies wird oft verwendet zum Codieren oder Decodieren Bildformate wie
jpg
,png
usw.quelle
Ein Problem ist, dass Folgendes implementierungsabhängig ist (gemäß dem ANSI-Standard):
x kann jetzt 127 (01111111) oder noch -1 (11111111) sein.
In der Praxis ist es normalerweise Letzteres.
quelle
Ich schreibe nur Tipps und Tricks. Es kann bei Tests und Prüfungen nützlich sein.
n = n*2
::n = n<<1
n = n/2
::n = n>>1
!(n & (n-1))
n
:n |= (1 << x)
x&1 == 0
(gerade)x ^ (1<<n)
quelle
Beachten Sie, dass in der Java-Implementierung die Anzahl der zu verschiebenden Bits von der Größe der Quelle abhängt.
Zum Beispiel:
gleich 2. Sie könnten erwarten, dass eine 65-fache Verschiebung der Bits nach rechts alles auf Null setzen würde, aber es ist tatsächlich das Äquivalent von:
Dies gilt für <<, >> und >>>. Ich habe es nicht in anderen Sprachen ausprobiert.
quelle
gcc 5.4.0
gibt eine Warnung, gibt aber2
für 5 >> 65; auch.Einige nützliche Bitoperationen / -manipulationen in Python.
Ich habe Ravi Prakashs Antwort in Python implementiert .
quelle
Beachten Sie, dass auf der Windows-Plattform nur eine 32-Bit-Version von PHP verfügbar ist.
Wenn Sie beispielsweise << oder >> um mehr als 31 Bit verschieben, sind die Ergebnisse unerwartet. Normalerweise wird die ursprüngliche Zahl anstelle von Nullen zurückgegeben, und es kann ein wirklich kniffliger Fehler sein.
Wenn Sie eine 64-Bit-Version von PHP (Unix) verwenden, sollten Sie natürlich eine Verschiebung um mehr als 63 Bit vermeiden. Beispielsweise verwendet MySQL jedoch den 64-Bit-BIGINT, sodass keine Kompatibilitätsprobleme auftreten sollten.
UPDATE: Unter PHP 7 Windows können PHP-Builds endlich vollständige 64-Bit-Ganzzahlen verwenden: Die Größe einer Ganzzahl ist plattformabhängig, obwohl ein Maximalwert von etwa zwei Milliarden der übliche Wert ist (das sind 32 Bit mit Vorzeichen). 64-Bit-Plattformen haben normalerweise einen Maximalwert von etwa 9E18, außer unter Windows vor PHP 7, wo es immer 32-Bit war.
quelle