Sind die Verschiebungsoperatoren ( <<
, >>
) in C arithmetisch oder logisch?
c
binary
bit-manipulation
bit-shift
kleines Byte
quelle
quelle
Antworten:
Laut K & R 2nd Edition sind die Ergebnisse implementierungsabhängig für die Verschiebung der vorzeichenbehafteten Werte nach rechts.
Wikipedia sagt, dass C / C ++ "normalerweise" eine arithmetische Verschiebung für vorzeichenbehaftete Werte implementiert.
Grundsätzlich müssen Sie entweder Ihren Compiler testen oder sich nicht darauf verlassen. Meine VS2008-Hilfe für den aktuellen MS C ++ - Compiler besagt, dass der Compiler eine arithmetische Verschiebung durchführt.
quelle
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 Werts ab.
(Als Hintergrund für diejenigen Leser, die mit dem Unterschied nicht vertraut sind, verschiebt eine "logische" Rechtsverschiebung um 1 Bit alle Bits nach rechts und füllt das Bit ganz links mit einer 0. Eine "arithmetische" Verschiebung belässt den ursprünglichen 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.
Angenommen, eine 32-Bit-Maschine:
quelle
TL; DR
Betrachten
i
undn
als linker bzw. rechter Operand eines Schichtoperators; die Art voni
, nach ganzzahliger Heraufstufung, seinT
. Untern
der Annahme , dass[0, sizeof(i) * CHAR_BIT)
wir nicht definiert sind, haben wir folgende Fälle:† Die meisten Compiler implementieren dies als arithmetische Verschiebung.
‡ undefiniert, wenn der Wert den Ergebnistyp T überschreitet. geförderte Art von i
Verschiebung
Erstens ist der Unterschied zwischen logischen und arithmetischen Verschiebungen aus mathematischer Sicht, ohne sich um die Größe des Datentyps zu kümmern. Logische Verschiebungen füllen verworfene Bits immer mit Nullen, während die arithmetische Verschiebung sie nur für die Linksverschiebung mit Nullen füllt, aber für die Rechtsverschiebung kopiert sie das MSB, wodurch das Vorzeichen des Operanden erhalten bleibt (unter der Annahme einer Zweierkomplementcodierung für negative Werte).
Mit anderen Worten, die logische Verschiebung betrachtet den verschobenen Operanden nur als einen Strom von Bits und verschiebt sie, 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 linksarithmetische Verschiebung einer Zahl X mit n entspricht der Multiplikation von X mit 2 n und entspricht somit der logischen Linksverschiebung; Eine logische Verschiebung würde auch das gleiche Ergebnis liefern, da MSB sowieso vom Ende fällt und es nichts zu bewahren gibt.
Eine rechtsarithmetische Verschiebung einer Zahl X durch n entspricht der ganzzahligen Division von X durch 2 n NUR, wenn X nicht negativ ist! Ganzzahlige Division ist nichts anderes als mathematische Division und rund auf 0 ( abgeschnitten ).
Bei negativen Zahlen, die durch die Zweierkomplementcodierung dargestellt werden, hat die Verschiebung nach rechts um n Bits den Effekt, dass sie mathematisch durch 2 n geteilt und in Richtung −∞ ( Etage ) gerundet wird . Daher ist die Rechtsverschiebung für nicht negative und negative Werte unterschiedlich.
Wo
÷
ist mathematische Division,/
ist ganzzahlige Division. Schauen wir uns ein Beispiel an:Wie Guy Steele betonte, hat diese Diskrepanz zu Fehlern in mehr als einem Compiler geführt . Hier können nicht negative (mathematische) nicht vorzeichenbehaftete und vorzeichenlose nicht negative Werte (C) zugeordnet werden; beide werden gleich behandelt und die Verschiebung nach rechts erfolgt durch ganzzahlige Division.
Logisch und arithmetisch sind also bei der Linksverschiebung gleichwertig und bei der Negativverschiebung für nicht negative Werte. Bei der Verschiebung der negativen Werte nach rechts unterscheiden sie sich.
Operanden- und Ergebnistypen
Standard C99 §6.5.7 :
Im obigen Snippet werden beide Operanden
int
(aufgrund einer ganzzahligen Heraufstufung); WennE2
negativ oderE2 ≥ 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. WurdeR
als deklariertshort
, würde dasint
Ergebnis der Schichtoperation implizit in konvertiert werdenshort
; Eine verengte Konvertierung, die zu einem implementierungsdefinierten Verhalten führen kann, wenn der Wert im Zieltyp nicht darstellbar ist.Linksverschiebung
Da die Linksverschiebungen für beide gleich sind, werden die frei gewordenen Bits einfach mit Nullen gefüllt. Es heißt dann, 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 nur als einen Strom von Bits betrachtet werden. Der Standard spricht jedoch nicht von Bits, sondern von dem Wert, den das Produkt von E1 mit 2 E2 erhält .
Die Einschränkung hierbei ist, dass für vorzeichenbehaftete Typen der Wert nicht negativ sein sollte und der resultierende Wert im Ergebnistyp darstellbar sein sollte. Andernfalls ist die Operation undefiniert. Der Ergebnistyp ist der Typ des 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, 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
Die Rechtsverschiebung für vorzeichenlose und vorzeichenlose nicht negative Werte ist ziemlich einfach. Die freien Bits werden mit Nullen gefüllt. Für vorzeichenbehaftete negative Werte ist das Ergebnis der Rechtsverschiebung implementierungsdefiniert. Die meisten Implementierungen wie GCC und Visual C ++ implementieren jedoch die Rechtsverschiebung als arithmetische Verschiebung, indem das Vorzeichenbit beibehalten wird.
Fazit
Im Gegensatz zu Java, die einen besonderen Betreiber hat
>>>
für logische Verschiebung abgesehen von den üblichen>>
und<<
, C und C ++ nur arithmetische Verschiebung haben mit einigen Bereichen und die Implementierung definierte nicht definiert. Der Grund, warum ich sie als arithmetisch betrachte, liegt in der Standardformulierung der Operation mathematisch, anstatt den verschobenen Operanden als einen Strom von Bits zu behandeln; Dies ist vielleicht der Grund, warum diese Bereiche nicht / implementierungsdefiniert bleiben, anstatt nur alle Fälle als logische Verschiebungen zu definieren.quelle
-Inf
sowohl für negative als auch für positive Zahlen. Das Runden einer positiven Zahl auf 0 ist ein privater Fall des Rundens auf 0-Inf
. Beim Abschneiden lassen Sie immer positiv gewichtete Werte fallen, daher subtrahieren Sie vom ansonsten präzisen Ergebnis.In Bezug auf die Art der Verschiebung, die Sie erhalten, ist die Art des Werts, den Sie verschieben, wichtig. Eine klassische Fehlerquelle ist, wenn Sie ein Literal verschieben, um beispielsweise Bits zu maskieren. Wenn Sie beispielsweise das am weitesten links stehende Bit einer Ganzzahl ohne Vorzeichen löschen möchten, können Sie dies als Maske versuchen:
Leider werden Sie dadurch in Schwierigkeiten geraten, da für die Maske alle Bits gesetzt sind, weil 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:
quelle
Hier sind Funktionen, die eine logische Rechtsverschiebung und eine arithmetische Rechtsverschiebung eines int in C gewährleisten:
quelle
Wenn Sie dies tun - Linksverschiebung mit 1 multiplizieren Sie mit 2 - Rechtsverschiebung mit 1 dividieren Sie durch 2
quelle
Nun, ich habe es auf Wikipedia nachgeschlagen und sie haben folgendes zu sagen:
Es klingt also so, als ob es von Ihrem Compiler abhängt. Beachten Sie auch in diesem Artikel, dass die Linksverschiebung für arithmetisch und logisch gleich ist. Ich würde empfehlen, einen einfachen Test mit einigen vorzeichenbehafteten und vorzeichenlosen Zahlen im Grenzfall durchzuführen (High-Bit-Satz natürlich) und zu sehen, was das Ergebnis auf Ihrem Compiler ist. Ich würde auch empfehlen, es zu vermeiden, je nachdem, ob es das eine oder das andere ist, da C anscheinend keinen Standard hat, zumindest wenn es vernünftig und möglich ist, eine solche Abhängigkeit zu vermeiden.
quelle
Linksverschiebung
<<
Dies ist irgendwie einfach und wenn Sie den Schaltoperator verwenden, ist dies immer eine bitweise Operation, sodass wir ihn nicht mit einer Doppel- und einer Float-Operation verwenden können. Immer wenn wir eine Null verschieben, wird sie zum niedrigstwertigen Bit (
LSB
) addiert .Bei der Rechtsverschiebung müssen
>>
wir jedoch eine zusätzliche Regel befolgen, die als "Vorzeichenbitkopie" bezeichnet wird. Die Bedeutung von "Vorzeichenbitkopie" ist, wenn das höchstwertige Bit (MSB
) gesetzt ist, dann nach einer erneuten Verschiebung nach rechtsMSB
gesetzt wird, wenn es zurückgesetzt wurde, dann wird es erneut zurückgesetzt, bedeutet, wenn der vorherige Wert Null war, dann nach erneutem Verschieben, das Bit ist Null, wenn das vorherige Bit Eins war, dann ist es nach der Verschiebung wieder Eins. Diese Regel gilt nicht für eine Linksverschiebung.Das wichtigste Beispiel für die Rechtsverschiebung, wenn Sie eine negative Zahl in die Rechtsverschiebung verschieben. Nach einer gewissen Verschiebung erreicht der Wert schließlich Null und danach, wenn Sie diese -1 verschieben, bleibt der Wert beliebig oft gleich. Bitte prüfen.
quelle
gccVerwendet normalerweise logische Verschiebungen für vorzeichenlose Variablen und für Linksverschiebungen für vorzeichenbehaftete Variablen. Die arithmetische Rechtsverschiebung ist wirklich wichtig, da sie die Variable vorzeichenweise erweitert.
gcc wird dies gegebenenfalls verwenden, wie es andere Compiler wahrscheinlich tun.
quelle
GCC tut es
für -ve -> Arithmetische Verschiebung
Für + ve -> Logische Verschiebung
quelle
Nach Meinung vieler c Compiler:
<<
ist eine arithmetische Linksverschiebung oder eine bitweise Linksverschiebung.>>
ist eine arithmetische Rechtsverschiebung oder eine bitweise Rechtsverschiebung.quelle
>>
arithmetisch oder bitweise (logisch)?" Sie antworteten ">>
ist arithmetisch oder bitweise." Das beantwortet die Frage nicht.<<
und>>
Operatoren sind logisch und nicht arithmetisch