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

Question

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.

Answer 1

Ich schreibe nur Tipps und Tricks. Sie können bei Tests und Prüfungen nützlich sein.

1. n = n*2 : n = n<<1
2. n = n/2 : n = n>>1
3. Prüfen, ob n eine Potenz von 2 ist (1,2,4,8,...): prüfen !(n & (n-1))
4. Unter x th kleines bisschen n : n |= (1 << x)
5. Prüfen, ob x gerade oder ungerade ist: x&1 == 0 (gerade)
6. Schalten Sie die n th Bit von x: x ^ (1<<n)

Answer 2

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

Zum Beispiel:

(long) 4 >> 65

gleicht 2. Man könnte annehmen, dass das 65-malige Verschieben der Bits nach rechts alles auf Null setzen würde, aber es ist tatsächlich das Äquivalent von:

(long) 4 >> (65 % 64)

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

Answer 3

Einige nützliche Bit-Operationen/Manipulationen in Python.

I umgesetzt Ravi Prakashs Antwort in Python.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
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 second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))

Answer 4

Die Bitwise-Operatoren werden verwendet, um Operationen auf Bitebene durchzuführen oder Bits auf unterschiedliche Weise zu manipulieren. Die bitweisen Operationen werden als viel schneller empfunden und werden manchmal verwendet, um die Effizienz eines Programms zu verbessern. Grundsätzlich können bitweise Operatoren auf die Ganzzahltypen angewendet werden: lang , int , kurz , char y Byte .

Bitweise Verschiebungsoperatoren

Sie werden in zwei Kategorien eingeteilt: die Linksverschiebung und die Rechtsverschiebung.

• Linksverschiebung(<<): Der Linksverschiebungs-Operator verschiebt alle Bits des Werts um eine bestimmte Anzahl von Malen nach links. Syntax: Wert << num. Hier gibt num die Anzahl der Positionen an, um die der Wert in value nach links verschoben wird. Das heißt, << verschiebt alle Bits im angegebenen Wert um die durch num angegebene Anzahl von Bitpositionen nach links. Bei jeder Linksverschiebung wird das höherwertige Bit herausgeschoben (und ignoriert/verloren), und auf der rechten Seite wird eine Null eingefügt. Das bedeutet, dass bei einer Linksverschiebung in einem 32-Bit-Compiler die Bits verloren gehen, sobald sie über die Bitposition 31 hinaus verschoben werden. Bei einem 64-Bit-Compiler gehen die Bits ab Bitposition 63 verloren.

Leistung: 6 Hier ist die binäre Darstellung von 3 0...0011 (unter Berücksichtigung des 32-Bit-Systems), so dass bei der einmaligen Verschiebung die führende Null ignoriert/verloren wird und alle restlichen 31 Bits nach links verschoben werden. Und am Ende wird eine Null hinzugefügt. Daraus wurde 0...0110, die Dezimaldarstellung dieser Zahl ist 6.

• Im Falle einer negativen Zahl:

Leistung: -2 In Java wird eine negative Zahl durch das 2er-Komplement dargestellt. SO, -1 wird durch 2^32-1 dargestellt, was 1....11 entspricht (bei einem 32-Bit-System). Bei einer einmaligen Verschiebung wird das führende Bit ignoriert/verloren und die restlichen 31 Bits werden nach links verschoben und am Ende wird eine Null hinzugefügt. Daraus wird dann 11...10 und die dezimale Entsprechung ist -2. Ich denke, Sie haben nun genug über die Linksverschiebung und ihre Funktionsweise erfahren.

• Rechte Umschalttaste(>>): Der Rechtsschiebe-Operator verschiebt alle Bits im Wert um ein bestimmtes Vielfaches nach rechts. Syntax: value >> num, num gibt die Anzahl der Positionen an, um den Wert in value nach rechts zu verschieben. Das heißt, >> verschiebt alle Bits in dem angegebenen Wert um die durch num angegebene Anzahl von Bitpositionen nach rechts. Das folgende Codefragment verschiebt den Wert 35 um zwei Positionen nach rechts:

Leistung: 8 Die binäre Darstellung von 35 in einem 32-Bit-System ist 00...00100011. Wenn wir sie also zweimal nach rechts verschieben, werden die ersten 30 führenden Bits nach rechts verschoben, die beiden niederwertigen Bits gehen verloren und zwei Nullen werden an den führenden Bits hinzugefügt. Daraus wird 00....00001000, die dezimale Entsprechung dieser binären Darstellung ist 8. Oder es gibt eine einfacher mathematischer Trick um die Ausgabe des folgenden Codes zu ermitteln: Um dies zu verallgemeinern, können wir sagen, dass x >> y = floor(x/pow(2,y)). Betrachten wir das obige Beispiel: x=35 und y=2, also 35/2^2 = 8,75 und wenn wir den Bodenwert nehmen, dann ist die Antwort 8.

Ausgabe:

Aber denken Sie daran, dass dieser Trick für kleine Werte von y in Ordnung ist, wenn Sie die großen Werte von y nehmen, erhalten Sie eine falsche Ausgabe.

• Im Falle einer negativen Zahl: Wegen der negativen Zahlen arbeitet der Rechtsschiebeoperator in zwei Modi: mit und ohne Vorzeichen. Beim Rechtsschiebeoperator mit Vorzeichen (>>) werden bei einer positiven Zahl die führenden Bits mit 0 und bei einer negativen Zahl mit 1 aufgefüllt. Um das Vorzeichen zu erhalten. Dies wird 'Vorzeichenerweiterung' genannt.

Ausgabe: -5 Wie ich oben erklärt habe, speichert der Compiler den negativen Wert als 2er-Komplement. So wird -10 als 2^32-10 und in der binären Darstellung unter Berücksichtigung des 32-Bit-Systems 11....0110 dargestellt. Wenn wir einmal schieben/verschieben, werden die ersten 31 führenden Bits nach rechts verschoben und das niederwertige Bit geht verloren/ignoriert. Daraus wird 11...0011 und die Dezimaldarstellung dieser Zahl ist -5 (Woher kenne ich das Vorzeichen der Zahl? weil das führende Bit 1 ist). Interessant ist, dass, wenn man -1 nach rechts verschiebt, das Ergebnis immer -1 bleibt, da die Vorzeichenerweiterung immer mehr Einsen in den höherwertigen Bits bringt.

• Rechtsverschiebung ohne Vorzeichen(>>>): Dieser Operator verschiebt auch Bits nach rechts. Der Unterschied zwischen vorzeichenbehaftet und vorzeichenlos besteht darin, dass bei letzterem die führenden Bits mit 1 aufgefüllt werden, wenn die Zahl negativ ist, und bei ersterem in jedem Fall mit Null. Nun stellt sich die Frage, warum wir eine vorzeichenlose Rechtsverschiebung benötigen, wenn wir mit dem Operator für vorzeichenbehaftete Rechtsverschiebung die gewünschte Ausgabe erhalten. Wenn Sie etwas verschieben, das keinen numerischen Wert darstellt, möchten Sie vielleicht keine Vorzeichenerweiterung vornehmen. Diese Situation tritt häufig auf, wenn Sie mit pixel-basierten Werten und Grafiken arbeiten. In diesen Fällen möchten Sie in der Regel eine Null in das höherwertige Bit verschieben, unabhängig vom ursprünglichen Wert.

Leistung: 2147483647 Denn -2 wird in einem 32-Bit-System als 11...10 dargestellt. Wenn wir das Bit um eins verschieben, werden die ersten 31 führenden Bits nach rechts verschoben, und das niederwertige Bit geht verloren bzw. wird ignoriert und die Null wird zum führenden Bit hinzugefügt. Daraus ergibt sich 011...1111 (2^31-1) und die dezimale Entsprechung ist 2147483647.

Answer 5

Die bitweisen Schiebeoperatoren verschieben die Bitwerte eines binären Objekts. Der linke Operand gibt den zu verschiebenden Wert an. Der rechte Operand gibt die Anzahl der Positionen an, um die die Bits des Wertes verschoben werden sollen. Das Ergebnis ist kein l-Wert. Beide Operanden haben den gleichen Vorrang und sind von links nach rechts assoziativ.

Operator     Usage

 <<           Indicates the bits are to be shifted to the left.

 >>           Indicates the bits are to be shifted to the right.

Jeder Operand muss einen Integral- oder Aufzählungstyp haben. Der Compiler führt Integral-Promotionen an den Operanden durch und konvertiert dann den rechten Operanden in den Typ int. Das Ergebnis hat denselben Typ wie der linke Operand (nach den arithmetischen Umwandlungen).

Der rechte Operand darf weder einen negativen Wert noch einen Wert haben, der größer oder gleich der Breite des zu verschiebenden Ausdrucks in Bits ist. Das Ergebnis von bitweisen Verschiebungen bei solchen Werten ist unvorhersehbar.

Wenn der rechte Operand den Wert 0 hat, ist das Ergebnis der Wert des linken Operanden (nach den üblichen arithmetischen Umrechnungen).

Der <<-Operator füllt frei gewordene Bits mit Nullen auf. Wenn zum Beispiel left_op den Wert 4019 hat, ist das Bitmuster (im 16-Bit-Format) von left_op:

0000111110110011

Der Ausdruck left_op << 3 ergibt sich:

0111110110011000

Der Ausdruck left_op >> 3 ergibt sich:

0000000111110110