Sind die Schiebeoperatoren (<<, >>) in C arithmetisch oder logisch?

https://stackoverflow.com/questions/7622

08-06-2019
|

Frage

In C sind die Verschiebungsoperatoren (<<, >>) arithmetisch oder logisch?

Lösung

Entsprechend K&R 2. Auflage Die Ergebnisse sind bei Rechtsverschiebungen vorzeichenbehafteter Werte von der Implementierung abhängig.

Wikipedia besagt, dass C/C++ „normalerweise“ eine arithmetische Verschiebung bei vorzeichenbehafteten Werten implementiert.

Grundsätzlich müssen Sie Ihren Compiler entweder testen oder sich nicht darauf verlassen.In meiner VS2008-Hilfe für den aktuellen MS C++-Compiler heißt es, dass der Compiler eine arithmetische Verschiebung durchführt.

Andere Tipps

Beim Verschieben nach links gibt es keinen Unterschied zwischen arithmetischer und logischer Verschiebung.Beim Verschieben nach rechts hängt die Art der Verschiebung von der Art des verschobenen Werts ab.

(Als Hintergrund für diejenigen Leser, die mit dem Unterschied nicht vertraut sind: Eine „logische“ Rechtsverschiebung um 1 Bit verschiebt alle Bits nach rechts und füllt das Bit ganz links mit einer 0 auf.Bei einer „arithmetischen“ Verschiebung verbleibt der ursprüngliche Wert im Bit ganz links.Der Unterschied wird wichtig, wenn es um negative Zahlen geht.)

Beim Verschieben eines vorzeichenlosen Werts ist der >>-Operator in C eine logische Verschiebung.Beim Verschieben eines vorzeichenbehafteten Werts ist der Operator >> eine arithmetische Verschiebung.

Nehmen wir zum Beispiel eine 32-Bit-Maschine:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

TL;DR

In Betracht ziehen i Und n der linke bzw. rechte Operand eines Schiebeoperators sein;die Art von i, nach ganzzahliger Förderung, sein T.Vorausgesetzt n angesagt sein [0, sizeof(i) * CHAR_BIT) – sonst undefiniert – wir haben diese Fälle:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

^{† Die meisten Compiler implementieren dies als arithmetische Verschiebung}
^{‡ undefiniert, wenn der Wert den Ergebnistyp T überläuft;geförderte Art von i}

Verschiebung

Erstens der Unterschied zwischen logischen und arithmetischen Verschiebungen aus mathematischer Sicht, ohne sich Gedanken über die Datentypgröße zu machen.Logische Verschiebungen füllen verworfene Bits immer mit Nullen, während arithmetische Verschiebungen sie nur bei Linksverschiebungen mit Nullen füllen, aber bei Rechtsverschiebungen das MSB kopieren und dabei das Vorzeichen des Operanden beibehalten (unter der Annahme, dass a Zweierkomplement Kodierung für negative Werte).

Mit anderen Worten betrachtet die logische Verschiebung den verschobenen Operanden nur als einen Bitstrom und verschiebt ihn, ohne sich um das Vorzeichen des resultierenden Werts zu kümmern.Die arithmetische Verschiebung betrachtet sie als (vorzeichenbehaftete) Zahl und behält das Vorzeichen bei, wenn Verschiebungen vorgenommen werden.

Eine arithmetische Verschiebung einer Zahl X um n nach links entspricht der Multiplikation von X mit 2^N und entspricht somit einer logischen Linksverschiebung;Eine logische Verschiebung würde ebenfalls zum gleichen Ergebnis führen, da MSB ohnehin am Ende abfällt und es nichts zu bewahren gibt.

Eine arithmetische Rechtsverschiebung einer Zahl X um n entspricht einer ganzzahligen Division von X durch 2^N NUR wenn X nicht negativ ist!Ganzzahldivision ist nichts anderes als mathematische Division und runden gegen 0 (abschneiden).

Bei negativen Zahlen, die durch die Zweierkomplement-Kodierung dargestellt werden, hat eine Verschiebung um n Bits nach rechts den Effekt, dass sie mathematisch durch 2 geteilt wird^N und Rundung in Richtung −∞ (Boden);Daher ist die Rechtsverschiebung für nichtnegative und negative Werte unterschiedlich.

für X ≥ 0, X >> n = X / 2^N = trunc(X ÷ 2^N)

für X < 0, X >> n = floor(X ÷ 2^N)

Wo ÷ ist mathematische Division, / ist eine ganzzahlige Division.Schauen wir uns ein Beispiel an:

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37 / 2 = 18 (18,5 auf 0 runden) = 10010)₂ [Ergebnis der arithmetischen Rechtsverschiebung]

-37)₁₀ = 11011011)₂ (unter Berücksichtigung eines Zweierkomplements, 8-Bit-Darstellung)

-37 ÷ 2 = -18.5

-37 / 2 = -18 (18,5 auf 0 runden) = 11101110)₂ [NICHT das Ergebnis einer arithmetischen Rechtsverschiebung]

-37 >> 1 = -19 (Rundung von 18,5 in Richtung −∞) = 11101101)₂ [Ergebnis der arithmetischen Rechtsverschiebung]

Als Guy Steele wies darauf hin, diese Diskrepanz hat dazu geführt Fehler in mehr als einem Compiler.Hier können nicht negative Werte (Mathematik) auf vorzeichenlose und vorzeichenbehaftete nicht negative Werte (C) abgebildet werden.beide werden gleich behandelt und ihre Rechtsverschiebung erfolgt durch Ganzzahldivision.

Logik und Arithmetik sind also bei der Linksverschiebung und für nichtnegative Werte bei der Rechtsverschiebung gleichwertig;Sie unterscheiden sich durch die Rechtsverschiebung negativer Werte.

Operanden- und Ergebnistypen

Standard C99 §6.5.7:

Jeder der Operanden muss ganzzahlige Typen haben.

Die ganzzahligen Heraufstufungen werden für jeden Operanden durchgeführt.Der Typ des Ergebnisses ist der des hochgestuften linken Operanden.Wenn der Wert des rechten Operanden negativ oder größer oder gleich der Breite des heraufgestuften linken Operanden ist, ist das Verhalten undefiniert.

short E1 = 1, E2 = 3;
int R = E1 << E2;

Im obigen Snippet werden beide Operanden int (aufgrund der Ganzzahlförderung);Wenn E2 war negativ bzw E2 ≥ sizeof(int) * CHAR_BIT dann ist die Operation undefiniert.Dies liegt daran, dass das Verschieben von mehr als den verfügbaren Bits mit Sicherheit zu einem Überlauf führt.Hatte R wurde deklariert als short, Die int Das Ergebnis der Verschiebungsoperation würde implizit in konvertiert short;eine einschränkende Konvertierung, die zu durch die Implementierung definiertem Verhalten führen kann, wenn der Wert im Zieltyp nicht darstellbar ist.

Linksverschiebung

Das Ergebnis von E1 << E2 sind E1 linksverschobene E2 Bitpositionen;Frei gewordene Bits werden mit Nullen aufgefüllt.Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1×2^E2, modulo um eins mehr reduziert als der im Ergebnistyp darstellbare Maximalwert.Wenn E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat und E1×2^E2 im Ergebnistyp darstellbar ist, dann ist das der resultierende Wert;Andernfalls ist das Verhalten undefiniert.

Da Linksverschiebungen bei beiden gleich sind, werden die frei gewordenen Bits einfach mit Nullen aufgefüllt.Anschließend heißt es, dass es sich sowohl für vorzeichenlose als auch für vorzeichenbehaftete Typen um eine arithmetische Verschiebung handelt.Ich interpretiere es als arithmetische Verschiebung, da sich logische Verschiebungen nicht um den durch die Bits dargestellten Wert kümmern, sondern ihn lediglich als einen Strom von Bits betrachten.aber der Standard spricht nicht von Bits, sondern definiert ihn anhand des Wertes, der durch das Produkt von E1 mit 2 erhalten wird^E2.

Die Einschränkung hierbei besteht darin, dass der Wert für vorzeichenbehaftete Typen nicht negativ sein sollte und der resultierende Wert im Ergebnistyp darstellbar sein sollte.Andernfalls ist die Operation undefiniert. Der Ergebnistyp wäre der Typ von E1 nach Anwendung der Integralheraufstufung und nicht der Zieltyp (die Variable, die das Ergebnis speichern wird).Der resultierende Wert wird implizit in den Zieltyp konvertiert;Wenn es in diesem Typ nicht darstellbar ist, ist die Konvertierung durch die Implementierung definiert (C99 §6.3.1.3/3).

Wenn E1 ein vorzeichenbehafteter Typ mit einem negativen Wert ist, ist das Verhalten der Linksverschiebung undefiniert. Dies ist ein einfacher Weg zu undefiniertem Verhalten, das leicht übersehen werden kann.

Rechte Shifttaste

Das Ergebnis von E1 >> E2 sind E1 nach rechts verschobene E2 Bitpositionen.Wenn E1 einen vorzeichenlosen Typ hat oder wenn E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat, ist der Wert des Ergebnisses der ganzzahlige Teil des Quotienten von E1/2^E2.Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert durch die Implementierung definiert.

Die Rechtsverschiebung für vorzeichenlose und nicht negative Werte mit Vorzeichen ist ziemlich einfach;die freien Bits werden mit Nullen aufgefüllt. Für vorzeichenbehaftete negative Werte ist das Ergebnis der Rechtsverschiebung durch die Implementierung definiert. Allerdings sind die meisten Implementierungen wie GCC und Visuelles C++ Implementieren Sie die Rechtsverschiebung als arithmetische Verschiebung, indem Sie das Vorzeichenbit beibehalten.

Abschluss

Im Gegensatz zu Java, das einen speziellen Operator hat >>> für die logische Abkehr vom Üblichen >> Und <<, C und C++ verfügen nur über arithmetische Verschiebungen, wobei einige Bereiche undefiniert und durch die Implementierung definiert bleiben.Der Grund, warum ich sie als Arithmetik betrachte, liegt darin, dass die Operation standardmäßig mathematisch formuliert wird, anstatt den verschobenen Operanden als Bitstrom zu behandeln.Dies ist möglicherweise der Grund, warum diese Bereiche un-/implementierungsdefiniert bleiben, anstatt nur alle Fälle als logische Verschiebungen zu definieren.

Im Hinblick auf die Art der Verschiebung, die Sie erhalten, kommt es vor allem auf die Art des Werts an, den Sie verschieben.Eine klassische Fehlerquelle ist das Verschieben eines Literals, um beispielsweise Bits zu maskieren.Wenn Sie beispielsweise das Bit ganz links einer vorzeichenlosen Ganzzahl löschen möchten, können Sie dies als Maske versuchen:

~0 >> 1

Leider führt dies zu Problemen, da alle Bits der Maske gesetzt sind, da der zu verschiebende Wert (~0) vorzeichenbehaftet ist und somit eine arithmetische Verschiebung durchgeführt wird.Stattdessen möchten Sie eine logische Verschiebung erzwingen, indem Sie den Wert explizit als vorzeichenlos deklarieren, d. h.indem Sie so etwas tun:

~0U >> 1;

Hier sind Funktionen, um die logische Rechtsverschiebung und die arithmetische Rechtsverschiebung eines int in C zu gewährleisten:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}

Wenn Sie dies tun - Verschiebung mit 1, multiplizieren Sie sich mit 2 - Rechtsumschicht mit 1 Sie dividieren Sie um 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)

Nun, ich habe nachgeschaut es auf Wikipedia, und sie haben folgendes zu sagen:

C hat jedoch nur einen ordnungsgemäßen Operator, >>.Viele C -Compiler wählen, welche rechte Verschiebung abhängig von der Art von Ganzzahl verschoben wird.Oft werden signierte Ganzzahlen unter Verwendung der arithmetischen Verschiebung verschoben, und unsignierte Ganzzahlen werden unter Verwendung der logischen Verschiebung verschoben.

Es hört sich also so an, als ob es von Ihrem Compiler abhängt.Beachten Sie auch in diesem Artikel, dass die Linksverschiebung für Arithmetik und Logik gleich ist.Ich würde empfehlen, einen einfachen Test mit einigen vorzeichenbehafteten und vorzeichenlosen Zahlen im Grenzfall durchzuführen (natürlich mit hohem Bitsatz) und zu sehen, was das Ergebnis auf Ihrem Compiler ist.Ich würde auch empfehlen, die Abhängigkeit vom einen oder anderen zu vermeiden, da C offenbar keinen Standard hat, zumindest wenn es vernünftig und möglich ist, eine solche Abhängigkeit zu vermeiden.

Linksverschiebung <<

Das ist irgendwie einfach und wenn Sie den Shift-Operator verwenden, handelt es sich immer um eine bitweise Operation, sodass wir sie nicht mit einer Double- und Float-Operation verwenden können.Immer wenn wir eine Null verschieben, wird sie immer zum niedrigstwertigen Bit addiert (LSB).

Aber im Rechtsgang >> Wir müssen eine zusätzliche Regel befolgen und diese Regel heißt „Vorzeichenbitkopie“.Die Bedeutung von „Vorzeichenbitkopie“ liegt darin, dass das höchstwertige Bit (MSB) wird dann nach einer Rechtsverschiebung wieder eingestellt MSB wird gesetzt, wenn es zurückgesetzt wurde, dann wird es erneut zurückgesetzt, d. h. wenn der vorherige Wert Null war, dann ist das Bit nach einer erneuten Verschiebung Null. Wenn das vorherige Bit eins war, ist es nach der Verschiebung wieder eins.Diese Regel gilt nicht für eine Linksverschiebung.

Das wichtigste Beispiel zur Rechtsverschiebung: Wenn Sie eine beliebige negative Zahl nach rechts verschieben, erreicht der Wert nach einiger Verschiebung schließlich den Wert Null und wenn Sie ihn anschließend beliebig oft um -1 verschieben, bleibt der Wert gleich.Überprüfen Sie bitte.

gcc verwendet typischerweise logische Verschiebungen bei vorzeichenlosen Variablen und Linksverschiebungen bei vorzeichenbehafteten Variablen.Die arithmetische Rechtsverschiebung ist wirklich wichtig, da sie die Variable vorzeichenerweitert.

gcc wird dies gegebenenfalls verwenden, wie es auch andere Compiler wahrscheinlich tun werden.

GCC tut es

für -ve -> Arithmetische Verschiebung
Für +ve -> Logische Verschiebung

Nach Meinung vieler C Compiler:

<< ist eine arithmetische Linksverschiebung oder bitweise Linksverschiebung.
>> ist eine arithmetische Rechtsverschiebung oder eine bitweise Rechtsverschiebung.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow