operators - rechner - shift operator c




Was sind bitweise Shift(Bit-Shift) Operatoren und wie funktionieren sie? (6)

Ich habe versucht, C in meiner Freizeit zu lernen, und andere Sprachen (C #, Java, etc.) haben das gleiche Konzept (und oft die gleichen Operatoren) ...

Was ich mich wundere, ist, auf einer zentralen Ebene, was Bit-Shifting (<<, >>, >>>) tun, welche Probleme kann es helfen zu lösen, und was gotchas lauern um die Ecke? Mit anderen Worten, ein absoluter Anfängerführer für Bitverschiebungen in all seiner Güte.


Bit Masking & Shifting

Bit-Shifting wird oft in Low-Level-Grafik-Programmierung verwendet. Zum Beispiel ein gegebener Pixelfarbwert, der in einem 32-Bit-Wort codiert ist.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Zum besseren Verständnis ist derselbe binäre Wert, der mit den Abschnitten markiert ist, die den Farbteil darstellen.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Sagen wir zum Beispiel, wir wollen den grünen Wert dieser Pixelfarbe erhalten. Wir können diesen Wert leicht durch Maskieren und Verschieben erreichen .

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  00000000

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 wir alle diese Bits um 16 Stellen nach rechts verschieben (logische Rechtsverschiebung) .

 green_value = masked_color >>> 16

Et voilá, wir haben die ganze Zahl, die den Betrag von Grün in der Pixelfarbe darstellt:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

Dies wird oft zum Kodieren oder Dekodieren von Bildformaten wie jpg , png , ... .


Beachten Sie, dass auf der Windows-Plattform nur eine 32-Bit-Version von PHP verfügbar ist.

Wenn Sie zum Beispiel << oder >> um mehr als 31 Bits verschieben, sind die Ergebnisse nicht zu erwarten. 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 die Verschiebung um mehr als 63 Bit vermeiden. Zum Beispiel verwendet MySQL das 64-Bit-BIGINT, daher sollte es keine Kompatibilitätsprobleme geben.

UPDATE: Von PHP7 Windows aus können PHP-Builds endlich volle 64-Bit-Integer verwenden: Die Größe einer Ganzzahl ist plattformabhängig, obwohl ein Maximalwert von etwa zwei Milliarden der übliche Wert ist (das sind 32 Bit, die signiert sind). 64-Bit-Plattformen haben normalerweise einen maximalen Wert von etwa 9E18, außer bei Windows vor PHP 7, wo es immer 32 Bit waren.


Bitweise Operationen, einschließlich Bit-Shift, sind grundlegend für Low-Level-Hardware oder Embedded-Programmierung. Wenn Sie eine Spezifikation für ein Gerät oder sogar einige binäre Dateiformate lesen, werden Sie Bytes, Wörter und Dwords sehen, die in Nicht-Byte-ausgerichtete Bitfelder aufgeteilt sind, die verschiedene interessierende Werte enthalten. Der Zugriff auf diese Bitfelder zum Lesen / Schreiben ist die gebräuchlichste 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 erreichen, würden 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 grün ONLY zu erhalten, der bei Offset 5 beginnt und bei 10 endet (dh 6 Bits lang), müssen Sie eine (Bit-) Maske verwenden, die, wenn sie auf das gesamte 16-Bit-Pixel angewendet wird, nachgibt nur die Teile, an denen wir interessiert sind.

#define GREEN_MASK  0x7E0

Die entsprechende Maske ist 0x7E0, die binär ist 0000011111100000 (das ist 2016 in Dezimal).

uint16_t green = (pixel & GREEN_MASK) ...;

Um eine Maske anzuwenden, verwenden Sie den UND-Operator (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Nach dem Anwenden der Maske erhalten Sie eine 16-Bit-Zahl, die wirklich nur eine 11-Bit-Zahl ist, da sich das MSB im 11. Bit befindet. Grün ist eigentlich nur 6 Bits lang, also müssen wir es mit einer Rechtsverschiebung (11 - 6 = 5) #define GREEN_OFFSET 5 , daher die Verwendung von 5 als Offset ( #define GREEN_OFFSET 5 ).

Ebenfalls üblich ist die Verwendung von Bitverschiebungen für schnelle Multiplikation und Division durch Potenzen von 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

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 signierte) Rechtsverschiebungsoperator.
  • >>> ist der logische (oder vorzeichenlose) Rechtsverschiebungsoperator.
  • << ist der Operator für die linke Schicht und erfüllt die Anforderungen sowohl für logische als auch für arithmetische Verschiebungen.

Alle diese Operatoren können auf ganzzahlige Werte ( int , long , möglicherweise short und byte oder char ) angewendet werden. In einigen Sprachen ändert die Anwendung der Verschiebungsoperatoren auf einen Datentyp, der kleiner als int ist, den Operand automatisch zu einem int .

Beachten Sie, dass <<< kein Operator ist, da dies überflüssig wäre. Beachten Sie auch, dass C und C ++ nicht zwischen den rechten Shift-Operatoren unterscheiden. Sie stellen nur den Operator >> , und das Verhalten der rechten Verschiebung ist die Implementierung für signierte Typen.

Linke Verschiebung (<<)

Ganzzahlen werden im Speicher als eine Reihe von Bits gespeichert. Zum Beispiel wäre die Zahl 6, die als 32-Bit- int gespeichert ist, wie int :

00000000 00000000 00000000 00000110

Das Verschieben dieses Bitmusters auf die linke Position ( 6 << 1 ) würde zu der Zahl 12 führen:

00000000 00000000 00000000 00001100

Wie Sie sehen können, sind die Ziffern um eine Position nach links verschoben, und die letzte Ziffer rechts ist mit einer Null gefüllt. Sie können auch bemerken, dass das Verschieben nach links einer Multiplikation mit Potenzen von 2 entspricht. Also ist 6 << 1 äquivalent zu 6 * 2 und 6 << 3 ist äquivalent zu 6 * 8 . Ein guter optimierender Compiler wird, wenn möglich, Multiplikationen durch Verschiebungen ersetzen.

Nicht-kreisförmige Verschiebung

Bitte beachten Sie, dass es sich nicht um Zirkularverschiebungen handelt. Verschieben Sie diesen Wert um eine Position nach links ( 3,758,096,384 << 1 ):

11100000 00000000 00000000 00000000

Ergebnisse in 3.221.225.472:

11000000 00000000 00000000 00000000

Die Ziffer, die "vom Ende" verschoben wird, ist verloren. Es geht nicht um.

Logische Rechtsverschiebung (>>>)

Eine logische Rechtsverschiebung ist die Umkehrung der linken Verschiebung. Anstatt Bits nach links zu verschieben, bewegen sie sich einfach nach rechts. Zum Beispiel, Verschieben der Zahl 12:

00000000 00000000 00000000 00001100

nach rechts um eine Position ( 12 >>> 1 ) erhalten wir unsere ursprüngliche 6 zurück:

00000000 00000000 00000000 00000110

Wir sehen also, dass eine Verschiebung nach rechts einer Division durch Potenzen von 2 entspricht.

Verlorene Bits sind weg

Eine Verschiebung kann jedoch keine "verlorenen" Bits zurückfordern. Zum Beispiel, wenn wir dieses Muster verschieben:

00111000 00000000 00000000 00000110

nach links 4 Positionen ( 939,524,102 << 4 ), erhalten wir 2.147.483.744:

10000000 00000000 00000000 01100000

und dann zurückschiebend ( (939,524,102 << 4) >>> 4 ) erhalten wir 134,217,734:

00001000 00000000 00000000 00000110

Sobald wir Bits verloren haben, können wir unseren ursprünglichen Wert nicht mehr zurückerhalten.

Arithmetische Rechtsverschiebung (>>)

Die arithmetische Rechtsverschiebung ist genau wie die logische Rechtsverschiebung, außer dass sie anstelle des Auffüllens mit Null mit dem höchstwertigen Bit auffüllt. Dies liegt daran, dass das höchstwertige Bit das Vorzeichenbit ist oder das Bit, das positive und negative Zahlen unterscheidet. Durch Auffüllen mit dem höchstwertigen Bit ist die arithmetische Rechtsverschiebung zeichenerhaltend.

Zum Beispiel, wenn wir dieses Bitmuster als negative Zahl interpretieren:

10000000 00000000 00000000 01100000

wir haben die Nummer -2.147.483.552. Wenn wir dies mit der arithmetischen Verschiebung (-2,147,483,552 >> 4) nach rechts verschieben würden, würden wir:

11111000 00000000 00000000 00000110

oder die Nummer -134,217,722.

Wir sehen also, dass wir das Zeichen unserer negativen Zahlen beibehalten haben, indem wir die arithmetische Rechtsverschiebung anstelle der logischen Rechtsverschiebung verwendet haben. Und wieder sehen wir, dass wir Division durch Zweierpotenzen durchführen.


Ich schreibe nur Tipps und Tricks, die in Tests / Prüfungen nützlich sein können.

  1. n = n*2 : n = n<<1
  2. n = n/2 : n = n>>1
  3. Überprüfung ob n die Potenz von 2 ist (1,2,4,8, ...): check !(n & (n-1))
  4. Das x- te Bit von n : n |= (1 << x)

Nehmen wir an, wir haben ein einzelnes Byte:

0110110

Wenn wir eine einzelne linke Bitshift anwenden, bekommen wir:

1101100

Die äußerste linke Null wurde aus dem Byte herausgeschoben, und eine neue Null wurde an das rechte Ende des Bytes angehängt.

Die Bits rollen nicht; sie werden verworfen. Das heißt, wenn Sie die Schicht 1101100 verlassen und dann nach rechts schieben, erhalten Sie das gleiche Ergebnis nicht zurück.

Die Verschiebung um N nach links entspricht einer Multiplikation mit 2 N.

Die Verschiebung nach rechts um N ist (wenn man das Einerkomplement verwendet ) das Äquivalent zum Dividieren durch 2 N und zum Runden auf Null.

Bitshifting kann für wahnsinnig schnelle Multiplikation und Division verwendet werden, vorausgesetzt, Sie arbeiten mit einer Potenz von 2. Nahezu alle Low-Level-Grafikroutinen verwenden Bitshifting.

Zum Beispiel haben wir in den alten Tagen Modus 13h (320x200 256 Farben) für Spiele verwendet. Im Modus 13h wurde der Videospeicher sequentiell pro Pixel ausgelegt. Um den Ort für ein Pixel zu berechnen, würden Sie die folgende Formel verwenden:

memoryOffset = (row * 320) + column

Heute, damals, war Geschwindigkeit entscheidend, also würden wir Bitships verwenden, um diese Operation durchzuführen.

Allerdings ist 320 keine Zweierpotenz, also müssen wir herausfinden, was eine Zweierpotenz ist, die zusammen 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)) + column

Jetzt erhalten wir den gleichen Offset wie zuvor, außer dass wir statt einer teuren Multiplikation die beiden Bitshifts verwenden ... in x86 wäre es ungefähr so ​​(Anmerkung, es ist seit der Assemblierung für immer geschehen (Anmerkung des Redakteurs: korrigiert) ein paar Fehler und fügte ein 32-Bit-Beispiel hinzu)):

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 mov

Total: 28 Zyklen, egal welche alte CPU diese Zeit hatte.

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 zu sparen.

Im 32- oder 64-Bit-Modus werden beide Versionen viel kürzer und schneller. Moderne Out-of-Order-CPUs wie Intel Skylake (siehe http://agner.org/optimize/ ) haben eine sehr schnelle Hardware-Multiplikation (geringe Latenz und hoher Durchsatz), so dass der Gewinn viel kleiner ist. AMD Bulldozer-Familie ist ein bisschen langsamer, vor allem für 64-Bit-Multiplikation. Bei Intel-CPUs und AMD Ryzen haben zwei Schichten eine geringfügig niedrigere Latenz, aber mehr Anweisungen als eine Multiplikation (was zu einem niedrigeren 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.

gegen

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.

Compiler werden dies für Sie tun: Sehen Sie, wie gcc, clang und MSVC alle shift + lea verwenden, wenn Sie die return 320*row + col; optimieren return 320*row + col; .

Das Interessanteste, was hier zu beachten ist, ist, dass x86 eine Shift-and-Add-Anweisung ( LEA ) hat , die kleine Linksverschiebungen ausführen und gleichzeitig mit der Performance as add Anweisung add kann. ARM ist noch leistungsfähiger: Ein Operand einer Anweisung kann umsonst links oder rechts verschoben werden. Die Skalierung um eine Kompilierzeitkonstante, die als Zweierpotenz bekannt ist, kann sogar effizienter sein als eine Multiplikation.

Ok, zurück in den modernen Tagen ... etwas nützlicher wäre 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 Compiler dies für Sie tun, wenn Sie eine struct mit zwei 8-Bit-Membern verwenden, aber in der Praxis nicht immer.





binary-operators