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


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.


1189
2017-09-26 19:47


Ursprung


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 signierte) Rechtsverschiebungsoperator.
  • >>> ist der logische (oder vorzeichenlose) Operator für die Verschiebung nach rechts.
  • << ist der Linksverschiebungsoperator und erfüllt sowohl die Anforderungen der logischen als auch der arithmetischen Verschiebungen.

Alle diese Operatoren können auf ganzzahlige Werte angewendet werden (int, long, möglicherweise short und byte oder char). In einigen Sprachen können Sie die Shift-Operatoren auf einen beliebigen Datentyp anwenden, der kleiner ist als int passt die Größe des Operanden automatisch an int.

Beachten Sie, dass <<< ist kein Operator, weil es überflüssig wäre. Beachten Sie auch, dass C und C ++ nicht zwischen den rechten Shift-Operatoren unterscheiden. Sie bieten nur die >> Operator und das rechtsschiebende Verhalten ist die Implementierung für signierte Typen definiert.


Linke Verschiebung (<<)

Ganzzahlen werden im Speicher als eine Reihe von Bits gespeichert. Zum Beispiel wird die Nummer 6 als 32-Bit gespeichert int wäre:

00000000 00000000 00000000 00000110

Verschieben dieses Bitmuster auf die linke Position (6 << 1) würde die Zahl 12 ergeben:

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 der Multiplikation mit Potenzen von 2 entspricht 6 << 1 ist ä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 dies ist nicht kreisförmige Verschiebungen. 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 unsere ursprünglichen 6:

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ückschieben ((939,524,102 << 4) >>> 4) wir bekommen 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 ist Schild Bit 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.


1508
2017-09-26 20:46



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 der Multiplikation mit 2N.

Die Verschiebung um N ist (wenn Sie verwenden Einser ergänzen) ist das Äquivalent der Division durch 2N und Rundung 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 sehr schnelle Hardware multiplizieren (niedrige 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 das für Sie tun: Sehen Sie, wie gcc, clang und MSVC verwenden alle shift + lea bei der Optimierung return 320*row + col;.

Das interessanteste, was hier zu beachten ist, ist dass x86 hat eine Shift-and-Add-Anweisung (LEA) das kann kleine Linksverschiebungen machen und gleichzeitig mit der Performance als und hinzufügen add Anweisung. 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 verwendet haben struct mit zwei 8-Bit-Mitgliedern, aber in der Praxis nicht immer.


169
2017-09-26 19:55



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) verkleinern, 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;

83
2017-09-26 22:22



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 erreichen Maskierung und Verschiebung.

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

Das logische & Der 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,....


39
2018-03-31 10:49



Ein Problem besteht darin, dass das Folgende implementierungsabhängig ist (gemäß dem ANSI-Standard):

char x = -1;
x >> 1;

x kann jetzt 127 (01111111) oder noch -1 (11111111) sein.

In der Praxis ist es normalerweise Letzteres.


26
2017-09-26 20:07



Beachten Sie, dass in der Java-Implementierung die Anzahl der zu verschiebenden Bits durch die Größe der Quelle geändert wird.

Beispielsweise:

(long) 4 >> 65

gleich 2. Man könnte erwarten, dass die Bits 65 Mal nach rechts verschoben werden, um alles auf Null zu setzen, aber es entspricht tatsächlich:

(long) 4 >> (65 % 64)

Dies gilt für <<, >> und >>>. Ich habe es nicht in anderen Sprachen ausprobiert.


8
2017-08-28 13:16



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üfen, ob n die Potenz von 2 ist (1,2,4,8, ...): überprüfen !(n & (n-1))
  4. Bekommen xth ein bisschen n: n |= (1 << x)
  5. Überprüfen, ob x gerade oder ungerade ist: x&1 == 0 (sogar)
  6. Toggle die nth Bit von x: x ^ (1<<n)

6
2017-10-11 22:43