In C sind die Shift-Operatoren (<<, >>) arithmetisch oder logisch?

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 zu verschiebenden Wertes 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 äußerste linke Bit mit einer 0 aus. Eine “arithmetische” Verschiebung belässt den ursprünglichen Wert im äußersten linken Bit 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.

Angenommen, 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);

Laut K&R 2nd Edition sind die Ergebnisse implementierungsabhängig für Rechtsverschiebungen von vorzeichenbehafteten Werten.

Wikipedia sagt, dass C/C++ ‘normalerweise’ eine arithmetische Verschiebung auf vorzeichenbehafteten Werten implementiert.

Grundsätzlich müssen Sie Ihren Compiler entweder testen oder sich nicht darauf verlassen. Meine VS2008-Hilfe für den aktuellen MS C++-Compiler sagt, dass ihr Compiler eine arithmetische Verschiebung durchführt.

TL;DR

In Betracht ziehen i und n der linke bzw. rechte Operand eines Schiebeoperators sein; die Art von inach Integer-Promotion, sein T. Vorausgesetzt n in sein [0, sizeof(i) * CHAR_BIT) — undefined otherwise — we’ve these cases:

| 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                |

^{† most compilers implement this as arithmetic shift
‡ undefined if value overflows the result type T; promoted type of i}

Shifting

First is the difference between logical and arithmetic shifts from a mathematical viewpoint, without worrying about data type size. Logical shifts always fills discarded bits with zeros while arithmetic shift fills it with zeros only for left shift, but for right shift it copies the MSB thereby preserving the sign of the operand (assuming a two’s complement encoding for negative values).

In other words, logical shift looks at the shifted operand as just a stream of bits and move them, without bothering about the sign of the resulting value. Arithmetic shift looks at it as a (signed) number and preserves the sign as shifts are made.

A left arithmetic shift of a number X by n is equivalent to multiplying X by 2ⁿ and is thus equivalent to logical left shift; a logical shift would also give the same result since MSB anyway falls off the end and there’s nothing to preserve.

A right arithmetic shift of a number X by n is equivalent to integer division of X by 2ⁿ ONLY if X is non-negative! Integer division is nothing but mathematical division and round towards 0 (trunc).

For negative numbers, represented by two’s complement encoding, shifting right by n bits has the effect of mathematically dividing it by 2ⁿ and rounding towards −∞ (floor); thus right shifting is different for non-negative and negative values.

for X ≥ 0, X >> n = X / 2ⁿ = trunc(X ÷ 2ⁿ)

for X < 0, X >> n = floor(X ÷ 2ⁿ)

where ÷ is mathematical division, / is integer division. Let’s look at an example:

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37 / 2 = 18 (rounding 18.5 towards 0) = 10010)₂ [result of arithmetic right shift]

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

-37 ÷ 2 = -18,5

-37 / 2 = -18 (Rundung von 18,5 auf 0) = 11101110)₂ [NOT the result of arithmetic right shift]

-37 >> 1 = -19 (Runden von 18,5 in Richtung −∞) = 11101101)₂ [result of arithmetic right shift]

Wie Guy Steele wies darauf hinzu der diese Diskrepanz geführt hat Fehler in mehr als einem Compiler. Hier kann nicht-negativ (math) auf vorzeichenlose und vorzeichenbehaftete nicht-negative Werte (C) abgebildet werden; beide werden gleich behandelt und ihre Rechtsverschiebung erfolgt durch ganzzahlige Division.

Logisch und arithmetisch sind also beim Linksverschieben und für nicht negative Werte beim Rechtsverschieben äquivalent; Sie unterscheiden sich in der richtigen Verschiebung negativer Werte.

Operanden- und Ergebnistypen

Standard C99 §6.5.7:

Jeder der Operanden soll ganzzahlige Typen haben.

Die ganzzahligen Heraufstufungen werden an jedem der Operanden durchgeführt. Der Typ des Ergebnisses ist der des heraufgestuften linken Operanden. Wenn der Wert des rechten Operanden negativ oder größer oder gleich der Breite des heraufgestuften linken Operanden ist, ist das Verhalten nicht definiert.

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

Im obigen Ausschnitt werden beide Operanden zu int (aufgrund der Integer-Promotion); 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 sicherlich überlaufen wird. Hatte R als deklariert worden shortdas int Ergebnis der Verschiebungsoperation würde implizit konvertiert werden short; eine einschränkende Konvertierung, die zu implementierungsdefiniertem Verhalten führen kann, wenn der Wert im Zieltyp nicht darstellbar ist.

Linksverschiebung

Das Ergebnis von E1 << E2 sind E1 nach links verschobene E2 Bitpositionen; frei gewordene Bits werden mit Nullen aufgefüllt. Wenn E1 einen vorzeichenlosen Typ hat, ist der Wert des Ergebnisses E1×2^E2, reduziert Modulo eins mehr 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 Ergebniswert; andernfalls ist das Verhalten undefiniert.

Da Linksverschiebungen für beide gleich sind, werden die frei gewordenen Bits einfach mit Nullen aufgefüllt. Dann heißt es, dass es sowohl für vorzeichenlose als auch für vorzeichenbehaftete Typen eine arithmetische Verschiebung ist. Ich interpretiere es als arithmetische Verschiebung, da logische Verschiebungen sich nicht um den Wert kümmern, der durch die Bits dargestellt wird, es betrachtet es nur als einen Strom von Bits; aber der Standard spricht nicht von Bits, sondern definiert ihn als Wert, der durch das Produkt von E1 mit 2 erhalten wird^E2.

Die Einschränkung hier ist, 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 integralen Heraufstufung und nicht der Zieltyp (die Variable, die das Ergebnis enthalten wird). Der resultierende Wert wird implizit in den Zieltyp konvertiert; wenn es in diesem Typ nicht darstellbar ist, dann ist die Konvertierung implementierungsdefiniert (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.

Verschiebung nach rechts

Das Ergebnis von E1 >> E2 sind E1-E2-Bitpositionen nach rechts verschoben. 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 implementierungsdefiniert.

Die Rechtsverschiebung für vorzeichenlose und vorzeichenbehaftete nicht negative Werte ist ziemlich einfach; die freien Bits werden mit Nullen aufgefüllt. Bei vorzeichenbehafteten negativen Werten ist das Ergebnis der Rechtsverschiebung implementierungsdefiniert. Allerdings sind die meisten Implementierungen wie GCC und Visual C++ Implementieren einer Verschiebung nach rechts als arithmetische Verschiebung durch Bewahren des Vorzeichenbits.

Fazit

Im Gegensatz zu Java, das einen speziellen Operator hat >>> für logische Verschiebungen abseits des Gewohnten >> und <<, C und C++ haben nur arithmetische Verschiebung, wobei einige Bereiche undefiniert und implementierungsdefiniert bleiben. Der Grund, warum ich sie als arithmetisch betrachte, liegt an der Standardformulierung der Operation mathematisch, anstatt den verschobenen Operanden als einen Strom von Bits zu behandeln; Dies ist vielleicht der Grund, warum diese Bereiche un/implementierungsdefiniert bleiben, anstatt nur alle Fälle als logische Verschiebungen zu definieren.

In Bezug auf die Art der Verschiebung, die Sie erhalten, ist die Art des Werts, den Sie verschieben, entscheidend. Eine klassische Fehlerquelle ist, wenn Sie ein Literal verschieben, um beispielsweise Bits zu maskieren. Wenn Sie beispielsweise das linke Bit einer vorzeichenlosen Ganzzahl löschen möchten, können Sie dies als Ihre Maske versuchen:

~0 >> 1

Leider werden Sie dadurch in Schwierigkeiten geraten, 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, dh indem Sie Folgendes tun:

~0U >> 1;

Hier sind Funktionen, um eine logische Rechtsverschiebung und eine 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 – Linksverschiebung um 1 multiplizieren Sie mit 2 – Rechtsverschiebung um 1 dividieren Sie durch 2

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

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

Nun, ich habe geschaut es auf Wikipediaund sie haben Folgendes zu sagen:

C hat jedoch nur einen Rechtsverschiebungsoperator, >>. Viele C-Compiler entscheiden, welche Verschiebung nach rechts durchgeführt werden soll, je nachdem, welche Art von Ganzzahl verschoben wird. Oft werden vorzeichenbehaftete Ganzzahlen mit der arithmetischen Verschiebung verschoben, und vorzeichenlose Ganzzahlen werden mit 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 (natürlich mit hohem Bitsatz) durchzuführen und zu sehen, was das Ergebnis auf Ihrem Compiler ist. Ich würde auch empfehlen zu vermeiden, dass es das eine oder andere ist, da es scheint, dass C keinen Standard hat, zumindest wenn es vernünftig und möglich ist, eine solche Abhängigkeit zu vermeiden.