webentwicklung-frage-antwort-db.com.de

Warum ruft die Linksverschiebungsoperation Undefiniertes Verhalten auf, wenn der linke Operand einen negativen Wert hat?

In C ruft eine bitweise Linksverschiebung ein undefiniertes Verhalten auf, wenn der linke Operand einen negativen Wert hat.

Relevantes Zitat aus ISO C99 (6.5.7/4)

Das Ergebnis von E1 << E2 ist E1 linksverschobene E2-Bitpositionen; leere Bits werden mit Nullen gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 × 2E2, Modulo eins mehr reduziert als der im Ergebnistyp darstellbare Maximalwert. Wenn E1 einen vorzeichenbehafteten Typ und einen nichtnegativen Wert hat, und E1 × 2E2 Ist im Ergebnistyp darstellbar, so ist dies der resultierende Wert; andernfalls ist das Verhalten nicht definiert .

In C++ ist das Verhalten jedoch klar definiert.

ISO C++ - 03 (5.8/2)

Der Wert von E1 << E2 ist E1 (interpretiert als Bitmuster) linksverschobene E2-Bitpositionen; freiwerdende Bits werden mit Nullen gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 multipliziert mit der auf die Potenz E2 angehobenen Größe 2, reduziert modulo ULONG_MAX + 1, wenn E1 einen vorzeichenlosen langen Typ hat, andernfalls UINT_MAX + 1. [Anmerkung: Die Konstanten ULONG_MAX und UINT_MAX sind im Header definiert.] ]

Das bedeutet

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

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

Was hat das ISO C++ - Komitee gezwungen, dieses Verhalten als gut definiert im Gegensatz zum Verhalten in C zu betrachten?

Auf der anderen Seite ist das Verhalten implementation defined für bitweise Rechtsverschiebung, wenn der linke Operand negativ ist, oder?

Meine Frage ist, warum Linksschichtbetrieb undefiniertes Verhalten in C aufruft und warum Rechtsschichtoperator nur definiertes Verhalten der Implementierung aufruft.

P.S: Bitte geben Sie keine Antworten wie "Es ist undefiniertes Verhalten, weil der Standard dies sagt". : P

39
Prasoon Saurav

Der Absatz, den Sie kopiert haben, handelt von vorzeichenlosen Typen. Das Verhalten ist undefiniert in C++. Aus dem letzten C++ 0x-Entwurf:

Der Wert von E1 << E2 ist E1 linksverschobene E2-Bitpositionen; freiwerdende Bits werden mit Nullen gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1 × 2E ^ 2, reduziert modulo eins mehr als der im Ergebnistyp darstellbare Maximalwert. Wenn andernfalls E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat und E1 × 2E ^ 2 im Ergebnistyp darstellbar ist, ist dies der resultierende Wert. sonst ist das Verhalten undefiniert .

EDIT: habe mir C++ 98 angeschaut. Es werden nur überhaupt keine signierten Typen erwähnt. Es ist also immer noch undefiniertes Verhalten.

Rechtsverschiebung negativ ist Umsetzung definiert, richtig. Warum? Meiner Meinung nach ist es einfach, die Implementierung zu definieren, da die linken Punkte nicht gekürzt werden. Wenn Sie nach links verschieben, müssen Sie nicht nur sagen, was von rechts verschoben ist, sondern auch, was mit den restlichen Bits geschieht, z. mit Zweierkomplementdarstellung, die eine andere Geschichte ist.

31
ybungalobill

In C ruft eine bitweise Linksverschiebung ein undefiniertes Verhalten auf, wenn der linke Operand einen negativen Wert hat. [...] Aber in C++ ist das Verhalten gut definiert. [...] Warum [...]

Die einfache Antwort lautet: Weil die Standards es so sagen.

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

Aus irgendeinem Grund wollte das C++ - Standardisierungskomitee eine kleine Garantie hinzufügen, wie sich die Bitdarstellung ändert. Da negative Zahlen jedoch immer noch über das 1er-Komplement oder Vorzeichen + Größe dargestellt werden können, variieren die resultierenden Wertemöglichkeiten immer noch.

Angenommen, 16-Bit-Ints haben wir

 -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 hat das ISO C++ - Komitee gezwungen, dieses Verhalten als gut definiert im Gegensatz zum Verhalten in C zu betrachten?

Ich nehme an, sie haben diese Garantie gegeben, damit Sie << entsprechend verwenden können, wenn Sie wissen, was Sie tun (dh wenn Sie sicher sind, dass Ihre Maschine das 2er-Komplement verwendet).

Andererseits ist das Verhalten für die bitweise Verschiebung nach rechts definiert, wenn der linke Operand negativ ist, oder?

Ich müsste den Standard überprüfen. Aber vielleicht hast du recht. Eine Rechtsverschiebung ohne Vorzeichenerweiterung auf einer 2er-Komplement-Maschine ist nicht besonders nützlich. Der aktuelle Status ist also definitiv besser als die Anforderung, dass leere Bits mit Nullen gefüllt werden müssen, da hier Platz für Maschinen bleibt, die eine Vorzeichenerweiterung durchführen - auch wenn dies nicht garantiert ist.

15
sellibitze

Zur Beantwortung Ihrer eigentlichen Frage wie im Titel angegeben: Wie bei jeder Operation für einen signierten Typ weist diese ein undefiniertes Verhalten auf, wenn das Ergebnis der mathematischen Operation nicht in den Zieltyp (Unter- oder Überlauf) passt. Ganzzahlige Typen mit Vorzeichen sind so aufgebaut.

Für die Linksverschiebung, wenn der Wert positiv oder 0 ist, ist die Definition des Operators als Multiplikation mit einer Potenz von 2 sinnvoll, sodass alles in Ordnung ist, sofern das Ergebnis nicht überläuft.

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 das Normungsgremium solche Unklarheiten vermeiden.

Meine Schlussfolgerung:

  • wenn Sie echte Bitmusteroperationen ausführen möchten, verwenden Sie vorzeichenlose Typen
  • wenn Sie einen Wert (mit oder ohne Vorzeichen) mit einer Zweierpotenz multiplizieren möchten, tun Sie genau das, so etwas wie

    i * (1u << k)

ihr Compiler wird dies in jedem Fall in einen anständigen Assembler verwandeln.

7
Jens Gustedt

Viele dieser Dinge sind ein Gleichgewicht zwischen dem, was herkömmliche CPUs in einem einzelnen Befehl tatsächlich unterstützen können, und dem, was nützlich genug ist, um zu erwarten, dass Compiler-Writer garantieren, dass es zusätzliche Anweisungen benötigt. Im Allgemeinen erwartet ein Programmierer, der Bitverschiebungsoperatoren verwendet, dass diese einzelnen Anweisungen auf CPUs mit solchen Anweisungen zugeordnet werden. Aus diesem Grund gibt es undefiniertes oder Implementierungsverhalten, bei dem CPUs unterschiedliche "Edge" -Bedingungen handhaben, anstatt ein Verhalten zu fordern und die Operation auszuführen unerwartet langsam sein. Beachten Sie, dass die zusätzlichen Vor-/Nach- oder Handhabungsanweisungen auch für die einfacheren Anwendungsfälle gemacht werden können. undefiniertes Verhalten kann notwendig gewesen sein, wenn einige CPUs Traps/Ausnahmen/Interrupts (im Unterschied zu C++ - Ausnahmen vom Typ try/catch) oder im Allgemeinen unbrauchbare/unerklärliche Ergebnisse generiert haben, während der Satz von CPUs, der zum Zeitpunkt der Bereitstellung vom Normungsausschuss geprüft wurde, alle zu Zumindest einige definierte Verhalten, dann könnten sie die Verhaltensimplementierung definieren.

3
Tony Delroy

Meine Frage ist, warum Linksschichtbetrieb undefiniertes Verhalten in C aufruft und warum Rechtsschichtoperator nur definiertes Verhalten der Implementierung aufruft.

Die Leute bei LLVM spekulieren, dass der Schichtbetreiber aufgrund der Art und Weise, wie die Anweisung auf verschiedenen Plattformen implementiert wird, Einschränkungen hat. Aus Was jeder C-Programmierer über undefiniertes Verhalten # 1/3 wissen sollte :

... Vermutlich ist dies darauf zurückzuführen, dass die zugrunde liegenden Verschiebevorgänge auf verschiedenen CPUs unterschiedliche Auswirkungen haben: Beispielsweise verkürzt X86 die 32-Bit-Verschiebung auf 5 Bit (eine Verschiebung um 32 Bit entspricht also einer Verschiebung) um 0 Bits), aber PowerPC schneidet die 32-Bit-Verschiebung auf 6 Bits ab (eine Verschiebung um 32 ergibt also Null). Aufgrund dieser Hardwareunterschiede ist das Verhalten von C ...

Nate, dass es in der Diskussion darum ging, einen Betrag zu verschieben, der größer als die Registergröße ist. Aber es ist das Beste, was ich gefunden habe, um die Verschiebungsbeschränkungen einer Behörde zu erklären.

Ich denke ein zweiter Grund ist der mögliche Vorzeichenwechsel auf einem 2er-Kompliment-Automaten. Aber ich habe es nirgendwo gelesen (nichts gegen @sellibitze (und ich stimme ihm zu)).

1
jww

In C89 wurde das Verhalten von linksverschiebenden negativen Werten eindeutig auf Zweierkomplement-Plattformen definiert, die keine Füllbits für vorzeichenbehaftete und vorzeichenlose Ganzzahltypen verwendeten. Die Wertebits, die vorzeichenlose und vorzeichenlose Typen gemeinsam hatten, befanden sich an derselben Stelle, und das Vorzeichenbit für einen vorzeichenlosen Typ konnte nur an derselben Stelle abgelegt werden wie das obere Wertebit für vorzeichenlose Typen, was wiederum erforderlich war sei links von allem anderen.

Das von C89 vorgeschriebene Verhalten war nützlich und sinnvoll für Plattformen mit zwei Komplementen ohne Polsterung, zumindest in Fällen, in denen eine Multiplikation keinen Überlauf verursachen würde. Auf anderen Plattformen oder bei Implementierungen, die einen vorzeichenbehafteten Ganzzahlüberlauf zuverlässig abfangen möchten, war das Verhalten möglicherweise nicht optimal. Die Autoren von C99 wollten wahrscheinlich Implementierungsflexibilität in Fällen zulassen, in denen das von C89 vorgeschriebene Verhalten weniger als ideal gewesen wäre, aber nichts in der Begründung legt die Absicht nahe, dass sich Qualitätsimplementierungen in Fällen, in denen dies der Fall war, nicht weiterhin auf die alte Weise verhalten sollten Kein zwingender Grund, etwas anderes zu tun.

Leider haben sich die Autoren von C11 geweigert, das Common-Case-Verhalten (Nicht-Überlauf-Verhalten) zu definieren, obwohl es noch nie Implementierungen von C99 gegeben hat, die keine Zweierkomplement-Mathematik verwenden. Laut IIRC würde dies die "Optimierung" behindern. Wenn der Linksschiebeoperator Undefiniertes Verhalten aufruft, wenn der linke Operand negativ ist, können Compiler davon ausgehen, dass die Verschiebung nur erreichbar ist, wenn der linke Operand nicht negativ ist. Dies ermöglicht Compilern, die Code erhalten wie:

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 somit der if-Test gelöscht und der launch_missiles()-Aufruf bedingungslos gemacht werden kann. Da bekannt ist, dass exit nicht zurückgibt, kann der Compiler auch die Berechnung von x<<4 weglassen. Wäre eine solche Regel nicht vorhanden, müsste ein Programmierer eine klobige __assume(x >= 0);-Direktive einfügen, um ein solches Verhalten anzufordern. Wenn jedoch negative Werte nach links verschoben werden, ist es nicht mehr erforderlich, einen Programmierer zu haben, der offensichtlich eine solche Semantik wünscht (aufgrund dessen) der Linksverschiebung), um den Code mit ihnen zu überladen.

Beachten Sie, dass der Aufruf von launch_missiles für den hypothetischen Fall, dass Code do_something(-1) aufruft, ein undefiniertes Verhalten zur Folge hat.

0
supercat

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

In Abschnitt 5p5 des Standards heißt es:

Wenn während der Auswertung eines Ausdrucks das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich der darstellbaren Werte für seinen Typ liegt, ist das Verhalten undefiniert

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

Tatsächlich dient der Satz über vorzeichenlose Typen mit modularer Arithmetik speziell dazu, zu vermeiden, dass Werte außerhalb des darstellbaren Bereichs generiert werden, was automatisch undefiniertes Verhalten wäre.

0
Ben Voigt