Was sind bitweise Verschiebung (Bit-Shift) Operatoren und wie funktionieren sie?
https://stackoverflow.com/questions/141525
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
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 frage mich heißt, bei einer Kern Ebene, was bedeutet Bit-Verschiebung (<<, >>, >>>) haben, welche Probleme kann es zu lösen, und welche Fallstricke lauern um die Kurve? Mit anderen Worten: Verschiebung eines absoluten Anfänger-Guide für Bit in all seine Güte.
Lösung
Die Bitverschiebung Betreiber tun genau das, was der Name schon sagt. Sie verlagern Bits. Hier ist eine kurze (oder nicht so kurz) Einführung in die verschiedenen Shift-Operatoren.
Die Operatoren
-
>>ist die arithmetische (oder signiert) rechten Shift-Operator. -
>>>ist die logische (oder ohne Vorzeichen) rechte Shift-Operator. -
<<ist die linke Shift-Operator, und erfüllt die Bedürfnisse sowohl logische als auch arithmetische Verschiebungen.
Alle diese Operatoren können auf ganzzahlige Werte angewendet werden (int, long, möglicherweise short und byte oder char). In einigen Sprachen auf jeden Datentyp kleiner als int die Shift-Operatoren Anwendung paßt die Größe automatisch die Operanden ein int sein.
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 >> Betreiber und das Recht schieb Verhalten ist Implementierung für signierte Typen definiert.
Linksverschiebung (<<)
Die ganzen Zahlen gespeichert sind, im Speicher, als eine Reihe von Bits. Zum Beispiel 6 die Zahl als int 32-Bit gespeichert wäre:
00000000 00000000 00000000 00000110
Shifting dieses Bitmuster nach links um eine Position (6 << 1) in der Nummer 12 führen würde:
00000000 00000000 00000000 00001100
Wie Sie sehen können, haben die Ziffern der um eine Position nach links verschoben, und die letzte Ziffer auf der rechten Seite mit einer Null gefüllt. Sie beachten, könnte auch, dass linke Verschiebung durch Potenzen von 2 zu einer Multiplikation entspricht So ist 6 << 1 zu 6 * 2 Äquivalent und 6 << 3 entspricht 6 * 8. Ein guter optimierenden Compiler Multiplikationen mit Verschiebungen, wenn möglich, ersetzen wird.
Unrund Verschiebung
Bitte beachten Sie, dass diese nicht Kreisverschiebungen. Verschieben Sie diesen Wert nach links um eine Position (3,758,096,384 << 1):
11100000 00000000 00000000 00000000
Ergebnisse in 3221225472:
11000000 00000000 00000000 00000000
Die Ziffer, die „über das Ende“ verschoben wird, verloren. Es nicht umlaufen.
Logische Rechtsverschiebung (>>>)
Eine logische Verschiebung nach rechts ist die Umkehrung nach links Verschiebung. Anstatt Bits nach links zu bewegen, sie einfach nach rechts bewegen. Zum Beispiel Verschieben der Nummer 12:
00000000 00000000 00000000 00001100
nach rechts um eine Position (12 >>> 1) wird wieder unsere ursprüngliche 6:
00000000 00000000 00000000 00000110
So sehen wir, dass durch Potenzen von 2.
Teilung nach rechts zu verschieben entsprichtverlorenen Bits sind weg
Allerdings kann eine Verschiebung nicht „verloren“ Bits zurückzufordern. Zum Beispiel, wenn wir verschieben dieses Muster:
00111000 00000000 00000000 00000110
nach links 4 Positionen (939,524,102 << 4), erhalten wir 2147483744:
10000000 00000000 00000000 01100000
und dann Verschiebung zurück ((939,524,102 << 4) >>> 4) erhalten wir 134.217.734:
00001000 00000000 00000000 00000110
Wir können unseren ursprünglichen Wert nicht zurück, sobald wir Bits verloren haben.
Arithmetic Verschiebung nach rechts (>>)
Die arithmetische Verschiebung nach rechts ist genau wie die logische Verschiebung nach rechts, außer statt Polsterung mit Null, es Pads mit dem höchstwertigen Bit. Dies liegt daran, das signifikanteste Bit ist die Zeichen Bit oder das Bit, das positive und negative Zahlen unterscheidet. Durch das Auffüllen mit dem höchstwertigen Bit, die arithmetischen Rechtsverschiebung ist ausgeschildert erhalten.
Zum Beispiel, wenn wir diesen Bitmuster als negative Zahl interpretiert:
10000000 00000000 00000000 01100000
Wir haben die Zahl -2147483552. Shifting dies auf der rechten Seite 4 Positionen mit der Stellenverschiebung (-2147483552 >> 4) würde uns:
11111000 00000000 00000000 00000110
oder die Zahl -134.217.722.
So sehen wir, dass wir die Zeichen unserer negativen Zahlen sind erhalten durch die arithmetische Verschiebung nach rechts, anstatt der logischen Verschiebung nach rechts. Einerneut d, sehen wir, dass wir eine Division durch Potenzen von 2 durchführen.
Andere Tipps
Nehmen wir an, wir haben ein einziges Byte:
0110110
eine einzige linke bitshift Anwendung bringt uns:
1101100
Die linke Null wurde aus dem Byte verschoben und ein neuer Null wurde mit dem rechten Ende des Bytes angehängt.
Die Bits Rollover nicht; sie werden verworfen. Das heißt, wenn Sie nach links verschoben 1101100 und dann nach rechts verschieben es, Sie werden nicht das gleiche Ergebnis zurück.
N durch Linksverschiebung entspricht Multiplikation mit 2 N .
von N rechts verschoben ist (wenn Sie mit Ergänzung sind) ist die Äquivalent Dividieren durch 2 N und auf Null gerundet wird.
Bitshifting kann für irrsinnig schnelle Multiplikation und Division verwendet werden, vorausgesetzt, Sie arbeiten mit einer Leistung von 2 Fast alle Low-Level-Grafikroutinen bitshifting verwenden.
Zum Beispiel Weg zurück in den alten Tagen, benutzten wir Modus 13h (320x200 256 Farben) für Spiele. Im Modus 13h wurde der Videospeicher sequentiell pro Pixel angelegt. Das bedeutete, dass sich die Position für ein Pixel zu berechnen, würden Sie die folgende mathematische verwenden:
memoryOffset = (row * 320) + column
Nun, zurück in diesem Tag und Alter, Geschwindigkeit war kritisch, so würden wir bitshifts verwenden diese Operation zu tun.
Allerdings 320 ist nicht eine Zweierpotenz, so dies umgehen wir herausfinden müssen, was eine Zweierpotenz ist, die zusammen 320 macht hinzugefügt:
(row * 320) = (row * 256) + (row * 64)
Jetzt können wir das in Linksverschiebungen konvertieren:
(row * 320) = (row << 8) + (row << 6)
Für ein endgültiges Ergebnis:
memoryOffset = ((row << 8) + (row << 6)) + column
Jetzt bekommen wir das gleiche wie zuvor versetzt, außer, statt einer teueren Multiplikationsoperation, verwenden wir die beiden bitshifts ... in x86 wäre es so etwas wie diese (beachten Sie, es ist schon immer, seit ich Assembly (Editor getan habe Hinweis: korrigiert ein paar Fehler und fügte eine 32-Bit-Beispiel)):
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
Insgesamt wurden. 28 Zyklen auf, was alte CPU diese Zeitpunkte 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 dem gleichen alten CPU.
Ja, würden wir diese harte Arbeit 16 CPU-Zyklen scheren.
In 32 oder 64-Bit-Modus, erhalten beiden Versionen viel kürzer und schneller. Moderne Out-of-Order-Ausführung CPUs wie Intel Skylake (siehe http://agner.org/optimize/ ) hat sehr schnelle Hardware-Erweiterung (mit niedriger Latenz und hohen Durchsatz), so dass der Gewinn ist viel kleiner. AMD Bulldozer-Familie ist ein wenig langsamer, vor allem für 64-Bit-Multiplikations. Auf Intel-CPUs und AMD Ryzen, sind zwei Schichten etwas niedrige Latenz aber mehr Anweisungen als ein mehrfach (was zu geringerem 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.
Compiler wird dies für Sie: Sehen Sie, wie gcc, Klirren und MSVC jegliche Nutzung shift + lea wenn return 320*row + col; Optimierung
Interessanteste, was zu beachten ist hier, dass x86 hat eine Verschiebung-und -add Anweisung (LEA) , die kleinen links~~POS=TRUNC und fügen Sie zugleich, mit der Leistung wie und add Anweisung tun können. ARM ist noch leistungsfähiger: einen Operanden jeder Anweisung gelassen werden kann oder rechts kostenlos verschoben. So Skalierung durch eine Kompilierung Zeitkonstante, das ist bekannt, kann als ein mehrfach sein noch effizienter eine Potenz von 2 zu sein.
OK, zurück in den modernen Zeiten ... etwas nützlicher wäre jetzt bitshifting zu verwenden, um zwei 8-Bit-Werte in einem 16-Bit-Integer. Zum Beispiel in C #:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
In C ++ Compiler sollte dies für Sie tun, wenn Sie einen struct mit zwei 8-Bit-Elemente verwendet, aber in der Praxis nicht immer.
bitweise Operationen, einschließlich Bit-Verschiebung, sind von grundlegender Bedeutung für Low-Level-Hardware oder Embedded-Programmierung. Wenn Sie eine Spezifikation für ein Gerät oder sogar einige Binärdateiformate lesen, werden Sie sehen, Bytes, Wörter und D-Worte in nicht-Byte ausgerichtet bitfields aufgebrochen, die verschiedene Werte von Interesse enthalten. Zugriff auf diese Bit-Felder zum Lesen / Schreiben ist die am weitesten verbreitete Anwendung.
Ein einfaches reales Beispiel in Grafik-Programmierung ist, dass ein 16-Bit-Pixel dargestellt wird, wie folgt:
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |
auf dem grünen Wert erhalten Sie das tun würden:
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Erklärung
Um den Wert von Grün zu erhalten ONLY, die bei 5 versetzt beginnt und endet bei 10 (dh 6-Bit lang), benötigen Sie einen (Bit) Maske zu verwenden, die, wenn sie gegen die gesamte 16-Bit-Pixel angewendet werden nur die Bits liefern wir interessiert sind.
#define GREEN_MASK 0x7E0
Die entsprechende Maske ist 0x7E0 die binär ist 0000011111100000 (die 2016 in dezimal).
uint16_t green = (pixel & GREEN_MASK) ...;
eine Maske anwenden zu können, verwenden Sie den Operator AND (&).
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Nach dem Auftragen der Maske, werden Sie mit einem 16-Bit-Zahl am Ende, das ist wirklich nur eine 11-Bit-Zahl seit seiner MSB im 11. Bit ist. Grün ist eigentlich nur 6 Bit lang, so müssen wir es verkleinern, eine Verschiebung nach rechts mit. (11-6 = 5), also die Verwendung von 5 als Offset (#define GREEN_OFFSET 5)
Auch gemeinsam Bit-Verschiebungen für die schnelle Multiplikation mit und Division durch Potenzen von 2:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
Bit Masking & Shifting
Bitverschiebung oft in niedrigen Niveau Grafik-Programmierung verwendet. Zum Beispiel codiert ein gegebenes Pixelfarbwert in einem 32-Bit-Wort.
Pixel-Color Value in Hex: B9B9B900
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
Zum besseren Verständnis des gleiche binäre Wert markiert mit welchen Abschnitten darstellt, welche Farbe Teil.
Red Green Blue Alpha
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
Nehmen wir zum Beispiel sagen, dass wir den grünen Wert dieser Pixel Farbe erhalten möchten. Man kann sich leicht den Wert erhalten, indem 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
Die logischen & Betreiber stellen sicher, dass nur die Werte, wo die Maske 1 gehalten. Das letzte, was wir jetzt tun müssen, ist den richtigen Integer-Wert zu erhalten, indem all diese Bits nach rechts um 16 Plätzen (logische Verschiebung nach rechts) verschieben .
green_value = masked_color >>> 16
voilá Et, haben wir die ganze Zahl die Menge der grünen Pixel in der Farbe darstellt:
Pixels-Green Value in Hex: 000000B9
Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001
Pixels-Green Value in Decimal: 185
Dies wird häufig für die Codierung oder Decodierung Bildformate wie jpg, png, ... verwendet.
Eine gotcha ist, dass die folgende Umsetzung abhängig ist (entsprechend dem ANSI-Standard):
char x = -1;
x >> 1;
x kann nun 127 (01111111) oder noch -1 (11111111).
In der Praxis ist es meist die letztere.
Ich schreibe Tipps und Tricks nur in Tests / Prüfungen nützlich sein kann.
-
n = n*2:n = n<<1 -
n = n/2:n = n>>1 - Überprüfen, ob n Potenz von 2 (1,2,4,8, ...): überprüfen
!(n & (n-1)) - Erste x th Bit
n:n |= (1 << x) - Überprüfen, ob x gerade oder ungerade ist:
x&1 == 0(auch) - Drücken Sie die n th Bit von x:
x ^ (1<<n)
Beachten Sie, dass in der Java-Implementierung, die Anzahl der Bits wird durch die Größe der Quelle zu verschieben mod'd.
Zum Beispiel:
(long) 4 >> 65
ist gleich 2. Sie erwarten die Bits auf der rechten Seite 65 mal Verschiebung würde Null alles, aber es ist eigentlich das Äquivalent:
(long) 4 >> (65 % 64)
Dies gilt für <<, >> und >>>. Ich habe es nicht in anderen Sprachen ausprobiert werden.
Einige nützliche Bit Betrieb / Manipulation in Python. Umgesetzt @Ravi Prakash Antworten in Python.
# basic bit operations
# int to bin
print(bin(10))
# bin to int
print(int('1010',2))
# multiplying x with 2 .... x**2== x << 1
print(200<<1)
# dividing x with 2 .... x /2 == x >> 1
print(200>>1)
# modulo x with 2 .... x%2 == x&1
if 20&1==0:
print("20 is a even number")
# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))
# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
Beachten Sie, dass nur 32-Bit-Version von PHP auf der Windows-Plattform verfügbar ist.
Dann, wenn Sie zum Beispiel Verschiebung << oder >> mehr als von 31 Bits, die Ergebnisse unexpectable sind. Normalerweise ist die ursprüngliche Zahl anstelle von Nullen zurückgegeben werden, und es kann ein wirklich kniffliger Fehler sein.
Natürlich, wenn Sie 64-Bit-Version von PHP (Unix) verwenden, sollten Sie von mehr als 63 Bits Verschiebung vermeiden. Jedoch zum Beispiel MySQL verwendet die 64-Bit-BIGINT, so sollte es keine Kompatibilitätsprobleme sein.
UPDATE: Von PHP7 Windows PHP-Builds ist endlich in der Lage volle 64-Bit-Zahlen zu verwenden: Die Größe einer ganze Zahl ist plattformabhängig, ein Maximalwert von etwa zwei Milliarden der üblicher Wert ist (das ist 32 Bit signed). 64-Bit-Plattformen haben in der Regel einen Maximalwert von etwa 9E18, außer unter Windows vor PHP 7, wo es war immer 32 Bit.
