Arithmetische Bitverschiebung bei einer vorzeichenbehafteten Ganzzahl

Lesezeit: 7 Minuten

Benutzeravatar von newprint
Neudruck

Ich versuche herauszufinden, wie genau arithmetische Bitverschiebungsoperatoren in C funktionieren und wie sie sich auf vorzeichenbehaftete 32-Bit-Ganzzahlen auswirken.

Nehmen wir der Einfachheit halber an, wir arbeiten innerhalb eines Bytes (8 Bits):

x = 1101.0101
MSB[ 1101.0101 ]LSB

Als ich andere Beiträge auf Stack Overflow und einigen Websites las, fand ich Folgendes:
<< verschiebt sich in Richtung MSB (in meinem Fall nach links) und füllt “leere” LSB-Bits mit 0s.

Und >> verschiebt sich in Richtung LSB (in meinem Fall nach rechts) und füllt “leere” Bits mit MS-Bit

So, x = x << 7 führt dazu, dass LSB nach MSB verschoben und alles auf 0 gesetzt wird.

1000.0000

Nun, sagen wir, ich würde >> 7, letztes Ergebnis. Dies würde zur Folge haben [0000.0010]? Habe ich recht?

Liege ich mit meinen Annahmen zu Schichtbetreibern richtig?

Ich habe gerade auf meiner Maschine getestet, **

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

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

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

Wieso den?

  • mögliches Duplikat des Shift-Operators in C

    – Jens Gustedt

    24. Oktober 2010 um 19:42 Uhr

  • “Warum?” Da Ihre Umsetzung sagt es. Überprüfen Sie die Dokumentation: it muss Definieren Sie das Verhalten der Rechtsverschiebung eines negativen Werts (oder Sie haben keinen C-Compiler).

    – pmg

    24. Oktober 2010 um 20:02 Uhr

  • @pseudonym27, die Sie in der Dokumentation finden müssen

    – Neudruck

    21. November 2014 um 18:55 Uhr

  • @pseudonym27: Rechtsverschiebung ist gut definiert, Linksverschiebung nicht. Betrachten Sie die Verschiebung nach links als aufeinanderfolgende Multiplikationen mit 2. Wenn eine Multiplikation überläuft, haben Sie Undefiniertes Verhalten.

    – pmg

    22. November 2014 um 10:23 Uhr

  • Das Entwurf des C11-Standards (PDF-Dokument) ist online frei verfügbar.

    – pmg

    23. November 2014 um 10:26 Uhr

Benutzeravatar von Matthew Slattery
Matthew Slattery

Die Rechtsverschiebung einer negativen vorzeichenbehafteten Zahl 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 zu 8-Bit-Beispielen wechseln), haben Sie eine negative Zahl. Das Verschieben nach rechts kann je nach Plattform und/oder Compiler “leere” Bits mit dem ursprünglichen MSB füllen (dh Vorzeichenerweiterung durchführen) oder es kann in Nullen verschoben werden.

(Implementierungsdefiniertes Verhalten bedeutet, dass der Compiler etwas Vernünftiges tut, aber auf plattformabhängige Weise; die Compiler-Dokumentation soll Ihnen sagen, was.)


Eine Verschiebung nach links, wenn die Zahl entweder negativ beginnt oder die Verschiebungsoperation eine 1 entweder zum oder über das Vorzeichenbit verschieben würde, hat ein undefiniertes Verhalten (wie die meisten Operationen mit vorzeichenbehafteten Werten, die einen Überlauf verursachen).

(Undefiniertes Verhalten bedeutet, dass überhaupt alles passieren könnte.)


Die gleichen Operationen auf ohne Vorzeichen Werte sind in beiden Fällen wohldefiniert: die “leeren” Bits werden mit 0 gefüllt.

  • Es sei darauf hingewiesen, dass die Rechtsverschiebung mit standardmäßiger, portabler Semantik auch als Division durch ein Potenz-von-Zwei-Literal bekannt ist. Die meisten Compiler generieren arithmetische Verschiebungen für solche Divisionen, was zu schnellem Code führt, der die Erweiterung wie gewünscht signiert.

    – Kuba hat Monica nicht vergessen

    16. Juni 2014 um 17:51 Uhr

  • @KubaOber: Moderne Standards erfordern das x/2 verhalten sich anders als bei einer Rechtsverschiebung in dem Fall, wo x ist eine negative ungerade Zahl. Eine normale arithmetische Rechtsverschiebung führt eine Bodendivision durch (also in Fällen, die nicht überlaufen (n+d)/d == (n/d)+1aber die Division ist erforderlich, um die abgeschnittene Division zu verwenden, wodurch Compiler daran gehindert werden, eine einfache Verschiebung zu verwenden.

    – Superkatze

    9. Juli 2014 um 18:02 Uhr

  • @KubaOber: Es sollte beachtet werden, dass die Linksverschiebung eines vorzeichenbehafteten Werts früher eine vorzeichenbehaftete Zweierpotenz-Multiplikation war, aber neuere Compiler scheinen die Unterstützung für die Linksverschiebung negativer Zahlen abgelehnt zu haben.

    – Superkatze

    16. April 2015 um 5:49 Uhr

  • Es könnte gut sein, darauf hinzuweisen, dass bei hypermodernen Compilern “alles” das Umordnen der Programmlogik umfasst, um vorzugeben, dass negative Werte positiv sind. Gegeben void foo(int x) { if (x >= 0) printf("Kaboom!"); int y= x<<4; } Berufung foo(-1); könnte sehr wahrscheinlich “Kaboom!” drucken.

    – Superkatze

    16. April 2015 um 5:56 Uhr

Benutzeravatar von pmg
pmg

Für negative Werte sind bitweise Schiebeoperationen nicht definiert

für ‘<<'

6.5.7/4 […] Wenn E1 einen vorzeichenbehafteten Typ und einen nichtnegativen Wert hat und E1×2E2 im Ergebnistyp darstellbar ist, dann ist das 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 Operationen für vorzeichenbehaftete Zahlen in einer bestimmten Implementierung zu untersuchen, da Sie nicht garantieren können, dass es in jeder anderen Implementierung genauso funktioniert (eine Implementierung ist beispielsweise Ihr Compiler auf Ihrem Computer mit Ihrer spezifische Befehlszeilenparameter).

Es funktioniert möglicherweise nicht einmal für eine ältere oder neuere Version desselben Compilers. Der Compiler könnte diese Bits sogar als zufällig oder undefiniert definieren. Dies würde bedeuten, dass dieselbe Codesequenz völlig unterschiedliche Ergebnisse liefern könnte, wenn sie in Ihren Quellen verwendet wird, oder sogar von Dingen wie Assembler-Optimierung oder anderer Registernutzung abhängt. Wenn es in eine Funktion eingekapselt ist, erzeugt es möglicherweise nicht einmal das gleiche Ergebnis in diesen Bits bei zwei aufeinanderfolgenden Aufrufen mit denselben Argumenten.

Es werden nur nicht negative Werte berücksichtigtder Effekt der Linksverschiebung um 1 (expression << 1) ist dasselbe wie die Multiplikation des Ausdrucks mit 2 (vorausgesetzt, Ausdruck * 2 läuft nicht über) und die Wirkung der Rechtsverschiebung um 1 (expression >> 1) ist dasselbe wie eine Division durch 2.

Ab c++20 Die bitweisen Verschiebungsoperatoren für vorzeichenbehaftete Ganzzahlen sind wohldefiniert.

Die Linksverschiebung a<<b ist äquivalent zu a*2^b Modul 2^N wo N ist die Anzahl der Bits im resultierenden Typ. Im Speziellen 1<<31 ist in der Tat die kleinste int Wert.

Die richtige Verschiebung a>>b ist äquivalent zu a/2^b, abgerundet (dh gegen minus unendlich). Also zB -1>>10 == -1.

Für einige weitere Details siehe https://en.cppreference.com/w/cpp/language/operator_arithmetic .

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

  • Und wie wäre es mit Golang oder einer anderen Sprache mit einer leichten Ähnlichkeit zu C?

    – trifft sich

    18. Juni 2020 um 18:43 Uhr

  • @mevets: Alle vernünftigen (oder zumindest vernünftigen Implementierungen davon) haben bereits auf diese Weise funktioniert, mit >> Bei vorzeichenbehafteten Typen ist eine arithmetische Rechtsverschiebung erforderlich. C++ kommt gerade erst dazu, tatsächlich zu dokumentieren, was jeder von seinen Compilern sowieso will und welche Sprachen wie Rust und Java von Anfang an gemacht haben. Garantiertes Rechenrecht richtig, statt implementierungsdefiniert.

    – Peter Cordes

    30. April 2021 um 7:29 Uhr

  • @mevets: Überprüfen Sie hier bezüglich Python: realpython.com/python-bitwise-operators

    – Hari

    24. Januar um 20:04 Uhr

  • C++20 garantiert nicht, dass “1<<31 ist in der Tat die kleinste int Wert.” int Es ist nicht nötig int32_t.

    – Ben Voigt

    7. Juli um 16:44 Uhr


Wie andere sagten, ist die Verschiebung des negativen Werts implementierungsdefiniert.

Die meisten Implementierungen behandeln eine vorzeichenbehaftete Rechtsverschiebung als floor(x/2N) durch Auffüllen von verschobenen Bits mit Vorzeichenbit. Es ist in der Praxis sehr praktisch, da diese Operation so üblich ist. Wenn Sie andererseits eine vorzeichenlose Ganzzahl nach rechts verschieben, werden die in Bits verschobenen Bits auf Null gesetzt.

Von der Maschinenseite aus gesehen haben die meisten Implementierungen zwei Arten von Rechtsverschiebungsbefehlen:

  1. Eine “arithmetische” Verschiebung nach rechts (oft mit Mnemonik ASR oder SRA), die wie von mir erklärt funktioniert.

  2. Eine “logische” Rechtsverschiebung (oft mit Mnemonik LSR oder SRL oder SR), die wie erwartet funktioniert.

Die meisten Compiler verwenden erstens für signierte Typen und zweitens für unsignierte. Nur aus Bequemlichkeit.

Im 32-Bit-Compiler

x = x >> 31;

hier ist x die vorzeichenbehaftete ganze Zahl, also ist das 32. Bit ein Vorzeichenbit.

der endgültige x-Wert ist 100000…000. und das 32. Bit geben einen -ive-Wert an.

Hier wird der x-Wert in das 1er-Komplement implementiert.

dann ist das letzte x -32768

Benutzeravatar von Andreas Haferburg
Andreas Häferburg

Auf meinem i7:

uint64_t:

0xffffffffffffffff >> 0 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 1 is 0b0111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 2 is 0b0011111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 3 is 0b0001111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 4 is 0b0000111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 62 is 0b0000000000000000000000000000000000000000000000000000000000000011
0xffffffffffffffff >> 63 is 0b0000000000000000000000000000000000000000000000000000000000000001
0xffffffffffffffff >> 64 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 65 is 0b0111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 66 is 0b0011111111111111111111111111111111111111111111111111111111111111

int64_t -1

0xffffffffffffffff >> 0 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 1 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 2 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 3 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 4 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 62 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 63 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 64 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 65 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 66 is 0b1111111111111111111111111111111111111111111111111111111111111111

int64_t 2^63-1

0x7fffffffffffffff >> 0 is 0b0111111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 1 is 0b0011111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 2 is 0b0001111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 3 is 0b0000111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 4 is 0b0000011111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 62 is 0b0000000000000000000000000000000000000000000000000000000000000001
0x7fffffffffffffff >> 63 is 0b0000000000000000000000000000000000000000000000000000000000000000
0x7fffffffffffffff >> 64 is 0b0111111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 65 is 0b0011111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 66 is 0b0001111111111111111111111111111111111111111111111111111111111111

1415740cookie-checkArithmetische Bitverschiebung bei einer vorzeichenbehafteten Ganzzahl

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy