Ich habe in meiner Freizeit versucht, C zu lernen, und andere Sprachen (C#, Java usw.) haben das gleiche Konzept (und oft die gleichen Operatoren) ...
Was ich mich frage, ist, was die Bitverschiebung ( << , >> , >>> ) tun, welche Probleme können damit gelöst werden, und welche Probleme lauern hinter der Kurve? Mit anderen Worten: ein Leitfaden für absolute Anfänger in Sachen Bit-Shifting in all seinen Vorzügen.
Die Bitverschiebungsoperatoren tun genau das, was ihr Name besagt. Sie verschieben Bits. Hier ist eine kurze (oder auch nicht so kurze) Einführung in die verschiedenen Verschiebeoperatoren.
>> ist der arithmetische (oder vorzeichenbehaftete) Rechtsschiebeoperator.>>> ist der logische (oder vorzeichenlose) Rechtsschiebeoperator.<< ist der Linksverschiebungsoperator und erfüllt die Anforderungen sowohl für logische als auch für arithmetische Verschiebungen.Alle diese Operatoren können auf ganzzahlige Werte angewendet werden ( int , long möglicherweise short y byte o char ). In einigen Sprachen ist die Anwendung der Verschiebungsoperatoren auf jeden Datentyp kleiner als int ändert automatisch die Größe des Operanden, so dass er ein int .
Beachten Sie, dass <<< ist kein Operator, da dies redundant wäre.
Beachten Sie auch, dass C und C++ unterscheiden nicht zwischen den Rechtsverschiebungsoperatoren . Sie liefern nur die >> Operator, und das Rechtsverschiebungsverhalten ist für vorzeichenbehaftete Typen durch die Implementierung festgelegt. Der Rest der Antwort verwendet die C#/Java-Operatoren.
(In allen gängigen C- und C++-Implementierungen, einschließlich GCC und Clang/LLVM, >> bei vorzeichenbehafteten Typen ist Arithmetik. Einige Codes gehen davon aus, aber der Standard garantiert dies nicht. Es ist nicht undefiniert Die Norm verlangt jedoch, dass die Implementierungen dies auf die eine oder andere Weise definieren. Linksverschiebungen von negativen vorzeichenbehafteten Zahlen es undefiniertes Verhalten (vorzeichenbehafteter Integer-Überlauf). Wenn Sie also keine arithmetische Rechtsverschiebung benötigen, ist es in der Regel eine gute Idee, die Bitverschiebung mit vorzeichenlosen Typen durchzuführen).
Ganzzahlen werden im Speicher als eine Reihe von Bits gespeichert. Zum Beispiel wird die Zahl 6 als 32-Bit int wäre:
00000000 00000000 00000000 00000110Die Verschiebung dieses Bitmusters um eine Position nach links ( 6 << 1 ) würde die Zahl 12 ergeben:
00000000 00000000 00000000 00001100Wie Sie sehen, haben sich die Ziffern um eine Position nach links verschoben, und die letzte Ziffer auf der rechten Seite ist mit einer Null aufgefüllt. Sie können auch feststellen, dass die Verschiebung nach links der Multiplikation mit Potenzen von 2 entspricht. 6 << 1 ist gleichbedeutend mit 6 * 2 y 6 << 3 ist gleichbedeutend mit 6 * 8 . Ein guter optimierender Compiler ersetzt Multiplikationen durch Verschiebungen, wenn dies möglich ist.
Bitte beachten Sie, dass es sich um no zirkuläre Verschiebungen. Die Verschiebung dieses Wertes um eine Position nach links ( 3,758,096,384 << 1 ):
11100000 00000000 00000000 00000000ergibt 3.221.225.472:
11000000 00000000 00000000 00000000Die Ziffer, die "vom Ende weg" verschoben wird, geht verloren. Sie wird nicht umgeschlagen.
Eine logische Rechtsverschiebung ist das Gegenstück zur Linksverschiebung. Anstatt Bits nach links zu verschieben, werden sie einfach nach rechts verschoben. Zum Beispiel die Verschiebung der Zahl 12:
00000000 00000000 00000000 00001100um eine Position nach rechts ( 12 >>> 1 ) erhalten wir unsere ursprüngliche 6 zurück:
00000000 00000000 00000000 00000110Wir sehen also, dass eine Verschiebung nach rechts einer Division durch Potenzen von 2 entspricht.
Eine Verschiebung kann jedoch keine "verlorenen" Bits zurückgewinnen. Wenn wir zum Beispiel dieses Muster verschieben:
00111000 00000000 00000000 00000110nach links 4 Positionen ( 939,524,102 << 4 ), erhalten wir 2.147.483.744:
10000000 00000000 00000000 01100000und dann zurückschieben ( (939,524,102 << 4) >>> 4 ) erhalten wir 134.217.734:
00001000 00000000 00000000 00000110Wenn wir Bits verloren haben, können wir unseren ursprünglichen Wert nicht wiedererlangen.
Die arithmetische Rechtsverschiebung entspricht genau der logischen Rechtsverschiebung, nur dass sie nicht mit Null, sondern mit dem höchstwertigen Bit aufgefüllt wird. Der Grund dafür ist, dass das höchstwertige Bit das Zeichen Bit oder das Bit, das zwischen positiven und negativen Zahlen unterscheidet. Durch Auffüllen mit dem höchstwertigen Bit ist die arithmetische Rechtsverschiebung vorzeichenerhaltend.
Wenn wir dieses Bitmuster zum Beispiel als negative Zahl interpretieren:
10000000 00000000 00000000 01100000haben wir die Zahl -2.147.483.552. Wenn wir diese Zahl mit der arithmetischen Verschiebung (-2.147.483.552 >> 4) um 4 Stellen nach rechts verschieben, erhalten wir:
11111000 00000000 00000000 00000110oder die Zahl -134.217.722.
Wir sehen also, dass wir das Vorzeichen unserer negativen Zahlen erhalten haben, indem wir die arithmetische Rechtsverschiebung und nicht die logische Rechtsverschiebung verwendet haben. Und wieder einmal sehen wir, dass wir eine Division durch Potenzen von 2 durchführen.
Nehmen wir an, wir haben ein einzelnes Byte:
0110110Mit einer einzigen Bitverschiebung nach links erhalten wir:
1101100Die äußerste linke Null wurde aus dem Byte herausgeschoben, und eine neue Null wurde am rechten Ende des Bytes angehängt.
Die Bits rollen nicht um, sondern werden verworfen. Das heißt, wenn Sie 1101100 nach links schieben und dann nach rechts schieben, erhalten Sie nicht das gleiche Ergebnis zurück.
Eine Linksverschiebung um N ist gleichbedeutend mit einer Multiplikation mit 2 N .
Die Rechtsverschiebung um N ist (bei Verwendung von Einerkomplement ) ist das Äquivalent zur Division durch 2 N und Rundung auf Null.
Bitshifting kann für wahnsinnig schnelle Multiplikationen und Divisionen verwendet werden, vorausgesetzt man arbeitet mit einer Potenz von 2. Fast alle Low-Level-Grafikroutinen verwenden Bitshifting.
Früher haben wir zum Beispiel den Modus 13h (320x200 256 Farben) für Spiele verwendet. Im Modus 13h wurde der Videospeicher sequentiell pro Pixel angelegt. Das bedeutete, dass man zur Berechnung des Speicherplatzes eines Pixels die folgende Rechnung anstellen musste:
memoryOffset = (row * 320) + columnDamals war die Geschwindigkeit entscheidend, deshalb haben wir für diesen Vorgang Bitshifts verwendet.
Da 320 jedoch keine Zweierpotenz ist, müssen wir herausfinden, was eine Zweierpotenz ist, die zusammengenommen 320 ergibt:
(row * 320) = (row * 256) + (row * 64)Jetzt können wir das in Linksverschiebungen umwandeln:
(row * 320) = (row << 8) + (row << 6)Für ein Endergebnis von:
memoryOffset = ((row << 8) + (row << 6)) + columnJetzt erhalten wir denselben Offset wie zuvor, nur dass wir statt einer teuren Multiplikationsoperation die beiden Bitshifts verwenden... in x86 würde das ungefähr so aussehen (Anmerkung: Es ist ewig her, dass ich Assembler gemacht habe (Anmerkung des Herausgebers: ein paar Fehler korrigiert und ein 32-Bit-Beispiel hinzugefügt)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last movInsgesamt: 28 Zyklen auf einer uralten CPU mit diesen Timings.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]12 Zyklen auf der gleichen alten CPU.
Ja, wir würden so hart arbeiten, um 16 CPU-Zyklen einzusparen.
Im 32- oder 64-Bit-Modus sind beide Versionen wesentlich kürzer und schneller. Moderne CPUs mit Out-of-Order-Ausführung wie Intel Skylake (siehe http://agner.org/optimize/ ) haben eine sehr schnelle Hardware-Multiplikation (niedrige Latenzzeit und hoher Durchsatz), so dass der Gewinn viel geringer ist. Die AMD Bulldozer-Familie ist etwas langsamer, insbesondere bei der 64-Bit-Multiplikation. Bei Intel-CPUs und AMD Ryzen sind zwei Verschiebungen mit etwas geringerer Latenz, aber mehr Anweisungen als eine Multiplikation (was zu einem geringeren Durchsatz führen kann):
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.Die Compiler erledigen dies für Sie: Siehe wie GCC, Clang und Microsoft Visual C++ verwenden alle die Tastenkombination Shift+Lea beim Optimieren return 320*row + col;,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:36.97169647716434,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g63,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-O3+-std%3Dc%2B%2B11+-Wall',source:1),l:'5',n:'0',o:'x86-64+gcc+6.3+(Editor+%231,+Compiler+%231)',t:'0')),k:30.33026438926557,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:clang400,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-O3+-std%3Dc%2B%2B11+-Wall',source:1),l:'5',n:'0',o:'x86-64+clang+4.0.0+(Editor+%231,+Compiler+%232)',t:'0')),header:(),k:32.69803913357011,l:'4',m:61.21344498970813,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cl19_64,filters:(b:'0',commentOnly:'0',directives:'0',intel:'0'),options:'-Ox',source:1),l:'5',n:'0',o:'x86-64+CL+19+2017+RTW+(Editor+%231,+Compiler+%233)',t:'0')),header:(),l:'4',m:38.78655501029187,n:'0',o:'',s:0,t:'0')),k:32.69803913357011,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4) .
Interessant ist hier vor allem die Feststellung, dass x86 hat einen Shift-und-Add-Befehl ( LEA ) die gleichzeitig kleine Linksverschiebungen und Additionen durchführen kann, wobei die Leistung als add Unterricht. ARM ist sogar noch leistungsfähiger: Ein Operand eines beliebigen Befehls kann kostenlos nach links oder rechts verschoben werden. So kann die Skalierung mit einer Kompilierzeitkonstante, die bekanntermaßen eine Potenz von 2 ist, sogar effizienter sein als eine Multiplikation.
OK, zurück in die modernen Tage... etwas nützlicher wäre es jetzt, Bitshifting zu verwenden, um zwei 8-Bit-Werte in einer 16-Bit-Ganzzahl zu speichern. Zum Beispiel, in C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;In C++ sollten die Compiler dies für Sie tun, wenn Sie eine struct mit zwei 8-Bit-Mitgliedern, aber in der Praxis ist das nicht immer der Fall.
Bitweise Operationen, einschließlich Bitverschiebung, sind grundlegend für Low-Level-Hardware oder eingebettete Programmierung. Wenn Sie eine Spezifikation für ein Gerät oder sogar einige binäre Dateiformate lesen, werden Sie Bytes, Worte und Wörter sehen, die in nicht byteausgerichtete Bitfelder unterteilt sind, die verschiedene Werte von Interesse 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:
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |Um den grünen Wert zu erhalten, müssen Sie Folgendes tun:
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;Erläuterung
Um den Wert von ONLY green zu erhalten, der bei Offset 5 beginnt und bei 10 endet (d.h. 6 Bits lang ist), müssen Sie eine (Bit-)Maske verwenden, die, wenn sie auf das gesamte 16-Bit-Pixel angewendet wird, nur die Bits liefert, an denen wir interessiert sind.
#define GREEN_MASK 0x7E0Die entsprechende Maske ist 0x7E0, was im Binärformat 0000011111100000 (dezimal 2016) entspricht.
uint16_t green = (pixel & GREEN_MASK) ...;Um eine Maske anzuwenden, verwenden Sie den Operator AND (&).
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;Nach Anwendung der Maske erhalten Sie eine 16-Bit-Zahl, die eigentlich nur eine 11-Bit-Zahl ist, da ihr MSB im 11. Bit liegt. Grün ist eigentlich nur 6 Bits lang, also 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 für die schnelle Multiplikation und Division mit 2er-Potenzen:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
Bit-Shifting wird häufig in der Low-Level-Grafikprogrammierung verwendet. Ein Beispiel: Ein bestimmter Pixel-Farbwert ist in einem 32-Bit-Wort kodiert.
Pixel-Color Value in Hex: B9B9B900
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000Zum besseren Verständnis wird derselbe Binärwert mit der Angabe versehen, welche Abschnitte für welchen Farbteil stehen.
Red Green Blue Alpha
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000Nehmen wir zum Beispiel an, wir wollen den Grünwert der Farbe dieses Pixels ermitteln. Wir können diesen Wert leicht ermitteln, indem wir Maskierung y wechseln. .
Unsere Maske:
Red Green Blue Alpha
color : 10111001 10111001 10111001 00000000
green_mask : 00000000 11111111 00000000 00000000
masked_color = color & green_mask
masked_color: 00000000 10111001 00000000 00000000Die logische & Operator stellt sicher, dass nur die Werte, bei denen die Maske 1 ist, erhalten bleiben. Das letzte, was wir jetzt tun müssen, ist, den korrekten ganzzahligen Wert zu erhalten, indem wir alle diese Bits um 16 Stellen nach rechts verschieben (logische Rechtsverschiebung) .
green_value = masked_color >>> 16Et voilà, wir haben die ganze Zahl, die den Anteil von Grün in der Farbe des Pixels darstellt:
Pixels-Green Value in Hex: 000000B9
Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001
Pixels-Green Value in Decimal: 185Dies wird häufig zur Kodierung oder Dekodierung von Bildformaten wie jpg , png , usw.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
