Warum ruft die linke Verschiebungsoperation Undefined Behavior auf, wenn der linke Operand einen negativen Wert hat?

In C ruft die bitweise Verschiebung nach links das Verhalten Undefiniert auf, wenn der Operand der linken Seite einen negativen Wert hat.

Relevantes Zitat aus ISO C99 (6.5.7 / 4)

Das Ergebnis von E1 << E2 ist E1 nach links verschobene E2-Bitpositionen; frei gewordene Bits werden mit Nullen gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 × 2 E2 , modulo um eins mehr reduziert als der Maximalwert, der im Ergebnistyp darstellbar ist. Wenn E1 einen Typ mit Vorzeichen und einen nichtnegativen Wert hat und E1 × 2 E2 im Ergebnistyp darstellbar ist, dann ist dies der resultierende Wert; Andernfalls ist das Verhalten nicht definiert .

Aber in C ++ ist das Verhalten gut definiert.

ISO C ++ – 03 (5.8 / 2)

Der Wert von E1 << E2 ist E1 (interpretiert als ein Bitmuster) nach links verschobene E2-Bitpositionen; frei gewordene Bits sind Null-gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 multipliziert mit der auf die Leistung E2 angehobenen Menge 2, reduzierter Modulo ULONG_MAX + 1, wenn E1 den Typ unsigned long hat, andernfalls UINT_MAX + 1. [Hinweis: Die Konstanten ULONG_MAXund UINT_MAX sind in der Kopfzeile definiert). ]

Das bedeutet

int a = -1, b=2, c; c= a << b ; 

ruft Undefiniertes Verhalten in C auf, aber das Verhalten ist in C ++ gut definiert.

Was zwang das Komitee von ISO C ++ dazu, dieses Verhalten im Gegensatz zum Verhalten in C als gut definiert zu betrachten?

Auf der anderen Seite ist das Verhalten eine implementation defined für eine bitweise Rechtsverschiebeoperation implementation defined ist, wenn der linke Operand negativ ist, richtig?

Meine Frage ist, warum ruft links Shift-Operation Undefined Behaviour in C und warum ruft Rechts Shift-Operator nur Implementierung definierte Verhalten?

PS: Bitte gib keine Antworten wie “Es ist undefiniertes Verhalten, weil der Standard es sagt”. : P

Der kopierte Absatz bezieht sich auf nicht signierte Typen. Das Verhalten ist in C ++ nicht definiert. Aus dem letzten C ++ 0x-Entwurf:

Der Wert von E1 < < E2 ist E1 nach links verschobene E2-Bitpositionen; frei gewordene Bits sind Null-gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 × 2E ^ 2, modulo um eins mehr reduziert als der Maximalwert, der im Ergebnistyp darstellbar ist. Andernfalls, wenn E1 einen vorzeichenbehafteten Typ und nicht-negativen Wert hat und E1 × 2E ^ 2 im Ergebnistyp darstellbar ist, dann ist das der resultierende Wert; Andernfalls ist das Verhalten nicht definiert .

EDIT: Werfen Sie einen Blick auf C ++ 98 Papier. Es werden nur signierte Typen überhaupt nicht erwähnt. Es ist also immer noch undefiniertes Verhalten.

Rechtsverschiebung negativ ist Implementierung definiert, rechts. Warum? Meiner Meinung nach: Es ist einfach zu implementieren-definieren, weil es keine Kürzung von den linken Ausgaben gibt. Wenn Sie nach links wechseln, müssen Sie nicht nur sagen, was von rechts verschoben wurde, sondern auch, was mit den anderen Bits passiert, z. B. mit der Zweierkomplementdarstellung, was eine andere Geschichte ist.

In C ruft die bitweise Verschiebung nach links das Verhalten Undefiniert auf, wenn der Operand der linken Seite einen negativen Wert hat. […] Aber in C ++ ist das Verhalten gut definiert. […] Warum […]

Die einfache Antwort lautet: Weil die Standards das sagen.

Eine längere Antwort ist: Es hat wahrscheinlich etwas damit zu tun, dass C und C ++ beide andere Darstellungen für negative Zahlen neben Zweierkomplement erlauben. Wenn Sie weniger Garantien dafür geben, was passieren wird, können Sie die Sprachen auf anderer Hardware verwenden, einschließlich obskurer und / oder alter Maschinen.

Aus irgendeinem Grund hatte das C ++ – Standardisierungskomitee das Gefühl, eine kleine Garantie dafür zu geben, wie sich die Bitdarstellung ändert. Aber da negative Zahlen immer noch durch 1er-Komplement oder Vorzeichen + Betrag dargestellt werden können, variieren die resultierenden Wertmöglichkeiten immer noch.

Nehmen wir 16 Bit-Ints, wir haben

  -1 = 1111111111111111 // 2's complement -1 = 1111111111111110 // 1's complement -1 = 1000000000000001 // sign+magnitude 

Um 3 nach links verschoben, werden wir bekommen

  -8 = 1111111111111000 // 2's complement -15 = 1111111111110000 // 1's complement 8 = 0000000000001000 // sign+magnitude 

Was zwang das Komitee von ISO C ++ dazu, dieses Verhalten im Gegensatz zum Verhalten in C als gut definiert zu betrachten?

Ich schätze, sie haben diese Garantie gemacht, so dass Sie < < angemessen verwenden können, wenn Sie wissen, was Sie tun (dh wenn Sie sicher sind, dass Ihr Computer das Zweierkomplement verwendet).

Auf der anderen Seite ist das Verhalten eine Implementierung, die für eine bitweise Rechtsverschiebeoperation definiert ist, wenn der linke Operand negativ ist, richtig?

Ich müsste den Standard überprüfen. Aber du hast vielleicht Recht. Eine Rechtsverschiebung ohne Vorzeichenerweiterung auf einer 2er-Komplement-Maschine ist nicht besonders nützlich. Der aktuelle Zustand ist also definitiv besser als die Forderung, leere Bits auf Null zu setzen, weil sie Platz für Maschinen lässt, die Zeichenerweiterungen machen – auch wenn dies nicht garantiert ist.

Um Ihre echte Frage wie im Titel angegeben zu beantworten: Wie bei jeder Operation mit einem signierten Typ hat dies ein undefiniertes Verhalten, wenn das Ergebnis der mathematischen Operation nicht in den Zieltyp passt (Unter- oder Überlauf). Signed Integer-Typen sind so gestaltet.

Für die linke Shift-Operation, wenn der Wert positiv oder 0 ist, ist die Definition des Operators als eine Multiplikation mit einer Potenz von 2 sinnvoll, also ist alles in Ordnung, es sei denn, das Ergebnis überläuft, nichts überraschend.

Wenn der Wert negativ ist, könnten Sie die gleiche Interpretation der Multiplikation mit einer Potenz von 2 haben, aber wenn Sie nur in Bezug auf die Bitverschiebung denken, wäre dies vielleicht überraschend. Offensichtlich wollte der Normenausschuss eine solche Mehrdeutigkeit vermeiden.

Meine Schlussfolgerung:

  • Wenn Sie echte Bitmusteroperationen ausführen möchten, verwenden Sie unsignierte Typen
  • Wenn du einen Wert (mit oder ohne Vorzeichen) mit einer Potenz von zwei multiplizieren willst, tue genau das, etwas ähnliches

    i * (1u < < k)

Ihr Compiler wird dies auf jeden Fall in einen anständigen Assembler umwandeln.

Viele dieser Dinge sind ein Gleichgewicht zwischen dem, was gewöhnliche CPUs tatsächlich in einer einzigen statement unterstützen können und was nützlich genug ist, um zu erwarten, dass Compiler-Schreiber sogar dann garantieren, wenn zusätzliche statementen benötigt werden. Im Allgemeinen erwartet ein Programmierer, der Bitverschiebungsoperatoren verwendet, dass diese auf einzelne statementen auf CPUs mit solchen statementen abgebildet werden. Aus diesem Grund gibt es ein undefiniertes oder Implementierungsverhalten, bei dem CPUs verschiedene “Randbedingungen” handhaben, anstatt ein Verhalten zu verlangen und die Operation auszuführen sei unerwartet langsam. Beachten Sie, dass die zusätzlichen Vor- / Nachbereitungs- oder Handhabungsanweisungen auch für die einfacheren Anwendungsfälle erstellt werden können. Undefiniertes Verhalten könnte notwendig gewesen sein, wenn einige CPUs Traps / Exceptions / Interrupts erzeugt haben (im Unterschied zu C ++ -Trust- / Catch-Typ-Exceptions) oder allgemein nutzlose / unerklärliche Ergebnisse, während, wenn der Satz von CPUs vom Standard Committee zu diesem Zeitpunkt berücksichtigt wurde zumindest ein definiertes Verhalten, dann könnten sie die Verhaltensimplementierung definieren.

Meine Frage ist, warum ruft links Shift-Operation Undefined Behaviour in C und warum ruft Rechts Shift-Operator nur Implementierung definierte Verhalten?

Die Leute von LLVM spekulieren, dass der Schichtbetreiber Einschränkungen hat, weil die statement auf verschiedenen Plattformen implementiert ist. Von was jeder C-Programmierer über undefiniertes Verhalten wissen sollte # 1/3 :

… Meine Vermutung ist, dass dies entstand, weil die zugrundeliegenden Schiebeoperationen auf verschiedenen CPUs unterschiedliche Dinge damit machen: zum Beispiel schneidet X86 die 32-Bit-Verschiebungsmenge auf 5 Bits ab (so ist eine Verschiebung um 32 Bits die gleiche wie eine Verschiebung) um 0 Bits), aber PowerPC schneidet die 32-Bit-Verschiebungsbeträge auf 6 Bits ab (so ergibt eine Verschiebung um 32 Null). Wegen dieser Hardware-Unterschiede ist das Verhalten von C völlig undefiniert …

Nate, dass die Diskussion über eine Verschiebung eines Betrags größer als die Registergröße war. Aber es ist der nächste, den ich gefunden habe, um die Verschiebungsbeschränkungen von einer Autorität zu erklären.

Ich denke, ein zweiter Grund ist die mögliche Änderung des Zeichens auf der Komplimentmaschine der 2. Aber ich habe es nirgends gelesen (nichts gegen @ sellibitze (und ich stimme ihm zu)).

Das Verhalten in C ++ 03 ist das gleiche wie in C ++ 11 und C99, Sie müssen nur über die Regel für Linksverschiebung hinausschauen.

Abschnitt 5p5 des Standards besagt, dass:

Wenn das Ergebnis bei der Auswertung eines Ausdrucks nicht mathematisch definiert ist oder nicht im Bereich darstellbarer Werte für seinen Typ liegt, ist das Verhalten nicht definiert

Die Linksverschiebungsausdrücke, die in C99 und C ++ 11 speziell als undefiniertes Verhalten genannt werden, sind dieselben, die zu einem Ergebnis außerhalb des Bereichs darstellbarer Werte ausgewertet werden.

Tatsächlich ist der Satz über vorzeichenlose Typen, die modulare Arithmetik verwenden, spezifisch, um zu vermeiden, dass Werte außerhalb des darstellbaren Bereichs erzeugt werden, was automatisch ein undefiniertes Verhalten wäre.

In C89 wurde das Verhalten von linksverschiebenden negativen Werten eindeutig auf Zweierkomplement-Plattformen definiert, die keine Füllbits für Ganzzahlenarten mit und ohne Vorzeichen verwendeten. Die Wert-Bits, die signierte und vorzeichenlose Typen gemeinsam hatten, befanden sich an den gleichen Stellen, und die einzige Stelle, an der das Vorzeichen-Bit für einen signierten Typ gehen konnte, war an der gleichen Stelle wie das obere Wert-Bit für vorzeichenlose Typen sei links von allem anderen.

Die C89-mandatierten Verhaltensweisen waren nützlich und sinnvoll für Zweierkomplement-Plattformen ohne Auffüllung, zumindest in Fällen, in denen das Behandeln von ihnen als Multiplikation keinen Überlauf verursachen würde. Das Verhalten war möglicherweise auf anderen Plattformen oder bei Implementierungen, die den vorzeichenbehafteten Integer-Überlauf zuverlässig abfangen möchten, nicht optimal. Die Autoren von C99 wollten wahrscheinlich die Flexibilität der Implementierungen in Fällen erlauben, in denen das C89-mandatierte Verhalten weniger als ideal gewesen wäre, aber nichts in der Begründung suggeriert die Absicht, dass Qualitätsimplementierungen sich nicht in der alten Art und Weise verhalten sollten kein zwingender Grund, etwas anderes zu tun.

Obwohl es keine Implementierungen von C99 gab, die keine Zweierkomplement-Mathematik verwenden, wollten die Autoren von C11 leider nicht das allgemeine (nicht überlaufende) Verhalten definieren; IIRC behauptete, dies würde die “Optimierung” behindern. Wenn der Operator für die linke Verschiebung Undefined Behavior aufruft, wenn der linke Operand negativ ist, können Compiler annehmen, dass die Verschiebung nur erreichbar ist, wenn der linke Operand nicht negativ ist. Dies ermöglicht Compilern, die Code wie erhalten:

 int do_something(int x) { if (x >= 0) { launch_missiles(); exit(1); } return x< <4; } 

zu erkennen, dass eine solche Methode niemals mit einem negativen Wert für x aufgerufen wird, und daher kann der if Test gelöscht und der Aufruf von launch_missiles() bedingungslos gemacht werden. Da bekannt ist, dass exit nicht zurückkehrt, kann der Compiler auch die Berechnung von x< <4 auslassen. Gäbe es eine solche Regel nicht, müsste ein Programmierer eine klobige __assume(x >= 0); einfügen __assume(x >= 0); statement, ein solches Verhalten anzufordern, aber Linksverschiebungen negativer Werte zu machen Undefiniertes Verhalten beseitigt die Notwendigkeit, einen Programmierer zu haben, der offensichtlich eine solche Semantik haben möchte (aufgrund der Ausführung der Linksverschiebung), um den Code mit ihnen zu überladen.

Beachten Sie, dass in dem hypothetischen Fall, dass der Code do_something(-1) , es sich um ein nicht definiertes Verhalten handelt, also wäre das Aufrufen von launch_missiles eine völlig legitime Sache.

Das Ergebnis der Verschiebung hängt von der numerischen Darstellung ab. Verschiebung verhält sich wie Multiplikation nur, wenn Zahlen als Zweierkomplement dargestellt werden. Aber das Problem ist nicht ausschließlich für negative Zahlen. Betrachten Sie eine vorzeichenbehaftete 4-Bit-Zahl, die im Überschuss von 8 dargestellt wird (auch als Offset-Binärwert bezeichnet). Die Zahl 1 wird als 1 + 8 oder 1001 dargestellt. Wenn wir das als Bits verschieben, erhalten wir 0010, was die Darstellung für -6 ist. In ähnlicher Weise wird -1 als -1 + 8 0111 dargestellt, was bei linksbündiger Verschiebung zu 1110 wird, die Darstellung für +6. Das bitweise Verhalten ist wohldefiniert, aber das numerische Verhalten hängt stark vom Darstellungssystem ab.