webentwicklung-frage-antwort-db.com.de

Arithmetische Bitverschiebung bei einer vorzeichenbehafteten Ganzzahl

Ich versuche herauszufinden, wie genau arithmetische Bit-Shift-Operatoren in C funktionieren und wie sich dies auf 32-Bit-Ganzzahlen mit Vorzeichen auswirkt.

Nehmen wir zur Vereinfachung an, dass wir innerhalb eines Bytes (8 Bits) arbeiten:

x = 1101.0101
MSB[ 1101.0101 ]LSB

Beim Lesen anderer Beiträge zu Stack Overflow und einigen Websites habe ich festgestellt, dass: << in Richtung MSB verschoben wird (in meinem Fall nach links) und "leere" LSB-Bits mit 0 füllen.

Und >> wird in Richtung LSB (in meinem Fall nach rechts) verschoben und "leere" Bits mit MS-Bit füllen

Also wird x = x << 7 dazu führen, dass LSB in MSB verschoben wird und alles auf 0 gesetzt wird.

1000.0000

Nun, sagen wir, ich würde >> 7, letztes Ergebnis. Dies würde zu [0000.0010] führen. Habe ich recht?

Bin ich mit meinen Annahmen zu Schichtbetreibern richtig?

Ich habe gerade auf meinem Rechner getestet **

int x = 1;   //000000000......01

x = x << 31; //100000000......00

x = x >> 31; //111111111......11 (Everything is filled with 1s !!!!!) 

Warum?

48
newprint

Die Rechtsverschiebung einer negativen vorzeichenbehafteten Nummer hat ein implementierungsdefiniertes Verhalten.

Wenn Ihre 8 Bits einen vorzeichenbehafteten 8-Bit-Wert darstellen sollen (da Sie von einer "vorzeichenbehafteten 32-Bit-Ganzzahl" sprechen, bevor Sie auf 8-Bit-Beispiele umschalten), haben Sie eine negative Zahl. Durch Verschieben nach rechts können "leere" Bits mit dem ursprünglichen MSB gefüllt werden (d. H. Vorzeichenerweiterung durchführen) oder je nach Plattform und/oder Compiler Nullen verschoben werden.

(Durch die Implementierung definiertes Verhalten bedeutet, dass der Compiler etwas plattformabhängig tut; die Compiler-Dokumentation soll Ihnen sagen, was.)


Eine Linksverschiebung, wenn die Zahl entweder negativ beginnt oder die Verschiebungsoperation eine 1 auf das Vorzeichenbit oder darüber hinaus verschieben würde, hat undefiniertes Verhalten (wie die meisten Operationen mit vorzeichenbehafteten Werten, die einen Überlauf verursachen).

(Undefiniertes Verhalten bedeutet, dass überhaupt etwas passieren kann.)


Die gleichen Operationen für unsigned Werte sind in beiden Fällen gut definiert: Die "leeren" Bits werden mit 0 gefüllt.

53

Bitweises Verschieben ist für negative Werte nicht definiert

für "<<"

6.5.7/4 [...] Wenn E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat und E1 × 2E2 ist im Ergebnistyp darstellbar, dann ist dies der Ergebniswert; Andernfalls ist das Verhalten undefiniert.

und für '>>'

6.5.7/5 [...] Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert implementierungsdefiniert.

Es ist Zeitverschwendung, das Verhalten dieser Vorgänge in Bezug auf signierte Zahlen in einer bestimmten Implementierung zu untersuchen, da Sie nicht garantieren können, dass es bei jeder anderen Implementierung genauso funktioniert (eine Implementierung ist zum Beispiel der Compiler auf Ihrem Computer mit Ihrer spezifische Commad-Line-Parameter).

Es funktioniert möglicherweise nicht einmal für eine ältere oder eine neuere Version desselben Compilers. Der Compiler kann diese Bits sogar als zufällig oder undefiniert definieren. Dies würde bedeuten, dass die gleiche Codefolge zu völlig unterschiedlichen Ergebnissen führen kann, wenn sie in Ihren Quellen verwendet wird oder sogar von Elementen wie der Optimierung von Baugruppen oder der Verwendung anderer Register abhängt. Wenn es in einer Funktion gekapselt ist, kann es bei zwei aufeinanderfolgenden Aufrufen mit denselben Argumenten nicht einmal zu demselben Ergebnis in diesen Bits kommen.

Betrachtet man nur nicht negative Werte , so ist der Effekt der Linksverschiebung um 1 (expression << 1) derselbe wie der Multiplikator des Ausdrucks mit 2 (der Ausdruck * 2 überläuft nicht) und der Effekt der Rechtsverschiebung um 1 (expression >> 1). ist das gleiche wie durch 2 teilen.

34
pmg

Wie andere wird die Verschiebung des negativen Werts durch die Implementierung definiert.

Die meisten Implementierungen behandeln vorzeichenbehaftete Rechtsverschiebungen als Boden (x/2)N) durch in Bits verschobene Zeichen mit Vorzeichenbit. Dies ist in der Praxis sehr praktisch, da diese Operation so üblich ist. Wenn Sie dagegen die Ganzzahl ohne Vorzeichen nach rechts verschieben, wird die Verschiebung in Bits auf Null gesetzt.

Von der Maschinenseite aus gesehen, verfügen die meisten Implementierungen über zwei Arten von Anweisungen zum Verschieben nach rechts:

  1. Eine "Arithmetik" verschiebt sich nach rechts (oft mit ASR oder SRA), die wie ich erklärte.

  2. Eine "logische" Verschiebung nach rechts (z. B. mit LSR oder SRL oder SR), die wie erwartet funktionieren.

Die meisten Compiler verwenden First für signierte Typen und Second für nicht signierte Typen. Nur zur Bequemlichkeit.

5
Vovanium

Ab c ++ 20 sind die bitweisen Verschiebungsoperatoren für Ganzzahlen mit Vorzeichen gut definiert.

Die Linksverschiebung a<<b ist äquivalent zu a*2^b Modul 2^N wobei N die Anzahl der Bits im resultierenden Typ ist. Speziell 1<<31 ist der kleinste int Wert.

Die richtige Verschiebung a>>b ist äquivalent zu a/2^b, abgerundet (dh gegen negative Unendlichkeit). So kann z.B. -1>>10 == -1.

Weitere Informationen finden Sie unter https://en.cppreference.com/w/cpp/language/operator_arithmetic .

(für die älteren Standards siehe die Antwort von Matthew Slattery)

1
example

Im 32-Bit-Compiler 

x = x >> 31; 

hier ist x die vorzeichenbehaftete Ganzzahl, also ist das 32. Bit das Vorzeichenbit.

Der endgültige x-Wert beträgt 100000 ... 000 . und das 32. Bit zeigt den positiven Wert an.

hier x Wert um 1 Kompliment.

dann ist x endgültig -32768

0
user3060837