Arithmetische Verschiebung - Arithmetic shift

Eine arithmetische Rechtsverschiebung einer Binärzahl um 1. Die leere Stelle im höchstwertigen Bit wird mit einer Kopie des ursprünglichen MSB gefüllt.
Eine arithmetische Linksverschiebung einer Binärzahl um 1. Die leere Stelle im niederwertigsten Bit wird mit einer Null aufgefüllt.
Arithmetische Verschiebungsoperatoren in verschiedenen Programmiersprachen und Prozessoren
Sprache oder Prozessor Links Richtig
ActionScript 3, Java , JavaScript , Python , PHP , Ruby ;
C , C++ , D , C# , Go , Julia , Swift (nur signierte Typen)		 << >>
Ada Shift_Left Shift_Right_Arithmetic
Kotlin shl shr
Standard-ML << ~>>
Verilog <<< >>>
OpenVMS- Makrosprache @
Planen arithmetic-shift
Gemeinsame Lisp ash
OCaml lsl asr
Haskell Data.Bits.shift
Montage, 68k ASL ASR
Montage, x86 SAL SAR
VHDL sla sra
RISC-V sll, slli sra, srai
Z80 SLA SRA

In Computer - Programmierung , eine arithmetische Verschiebung ist ein Verschiebungs - Operator , manchmal genannt unterzeichnet Verschiebung (obwohl es nicht unterzeichneten Operanden beschränkt ist). Die beiden Grundtypen sind die arithmetische Linksverschiebung und die arithmetische Rechtsverschiebung . Bei Binärzahlen ist es eine bitweise Operation , die alle Bits ihres Operanden verschiebt; jedes Bit im Operanden wird einfach um eine bestimmte Anzahl von Bitpositionen verschoben, und die freien Bitpositionen werden aufgefüllt. Anstatt wie bei der logischen Verschiebung mit allen Nullen aufgefüllt zu werden , wird beim Verschieben nach rechts das ganz linke Bit (normalerweise das Vorzeichenbit in ganzzahligen Darstellungen mit Vorzeichen) wird repliziert, um alle freien Stellen auszufüllen (dies ist eine Art Vorzeichenerweiterung ).

Einige Autoren bevorzugen die Begriffe Sticky Right-Shift und Zero-Fill-Rechtsverschiebung für arithmetische bzw. logische Verschiebungen.

Arithmetische Verschiebungen können als effiziente Wege nützlich sein, um eine Multiplikation oder Division von vorzeichenbehafteten ganzen Zahlen mit Zweierpotenzen durchzuführen. Das Verschieben nach links um n Bits bei einer vorzeichenbehafteten oder vorzeichenlosen Binärzahl hat den Effekt, dass sie mit 2 n multipliziert wird . Das Verschieben nach rechts um n Bits einer vorzeichenbehafteten Zweierkomplement- Binärzahl hat den Effekt, dass sie durch 2 n geteilt wird , aber es wird immer abgerundet (in Richtung negativer Unendlichkeit). Dies unterscheidet sich von der Art und Weise, wie das Runden normalerweise bei der Division von ganzen Zahlen mit Vorzeichen durchgeführt wird (die gegen 0 rundet). Diese Diskrepanz hat zu Fehlern in einer Reihe von Compilern geführt.

Zum Beispiel dividiert im x86-Befehlssatz der SAR-Befehl (arithmetische Rechtsverschiebung) eine vorzeichenbehaftete Zahl durch eine Zweierpotenz, wobei in Richtung negativer Unendlichkeit gerundet wird. Der IDIV-Befehl (Vorzeichendividende) teilt jedoch eine vorzeichenbehaftete Zahl und rundet gegen Null. Eine SAR-Anweisung kann also keine IDIV durch Zweierpotenz-Anweisung ersetzen oder umgekehrt.

Formale Definition

Die formale Definition einer arithmetischen Verschiebung aus dem Federal Standard 1037C lautet:

Eine Verschiebung, die auf die Darstellung einer Zahl in einem festen radix System numeration und in einer Festpunktdarstellung System und in dem nur die Zeichen , die den Festkommateil der Zahl , die bewegt werden. Eine arithmetische Verschiebung entspricht normalerweise der Multiplikation der Zahl mit einer positiven oder negativen ganzzahligen Potenz der Basis, mit Ausnahme des Effekts einer Rundung; Vergleichen Sie die logische Verschiebung mit der arithmetischen Verschiebung, insbesondere bei Gleitkommadarstellung .

Ein wichtiges Wort in der FS 1073C-Definition ist „normalerweise“.

Äquivalenz von arithmetischen und logischen Linksverschiebungen und Multiplikationen

Arithmetische Linksverschiebungen entsprechen einer Multiplikation mit einer (positiven, ganzzahligen) Potenz der Basis (zB einer Multiplikation mit einer Potenz von 2 für Binärzahlen). Logische Linksverschiebungen sind ebenfalls äquivalent, außer dass Multiplikation und arithmetische Verschiebungen einen arithmetischen Überlauf auslösen können, während logische Verschiebungen dies nicht tun.

Nicht-Äquivalenz von arithmetischer Rechtsverschiebung und Division

Allerdings sind arithmetische Rechtsverschiebungen große Fallen für die Unvorsichtigen, insbesondere bei der Behandlung des Rundens von negativen ganzen Zahlen. In der üblichen Zweier-Komplement- Darstellung von negativen ganzen Zahlen wird –1 beispielsweise als alle Einsen dargestellt. Für eine 8-Bit-Ganzzahl mit Vorzeichen ist dies 1111 1111. Eine arithmetische Rechtsverschiebung um 1 (oder 2, 3, ..., 7) ergibt wieder 1111 1111, was immer noch −1 ist. Dies entspricht dem Abrunden (in Richtung negativ unendlich), ist aber nicht die übliche Konvention für die Division.

Es wird häufig behauptet, dass arithmetische Rechtsverschiebungen einer Division durch eine (positive, ganzzahlige) Potenz der Basis entsprechen (z optimiert, indem es als arithmetische Rechtsverschiebung implementiert wird. (Ein Schieber ist viel einfacher als ein Teiler. Auf den meisten Prozessoren werden Schiebebefehle schneller ausgeführt als Divisionsbefehle.) Große Anzahl von Programmierhandbüchern, Handbüchern und anderen Spezifikationen aus den 1960er und 1970er Jahren von Unternehmen und Institutionen wie DEC , IBM , Data General und ANSI machen solche falschen Aussagen.

Logische Rechtsverschiebungen sind nur für positive oder vorzeichenlose Zahlen äquivalent zur Division durch eine Potenz der Basis (normalerweise 2). Arithmetische Rechtsverschiebungen sind äquivalent zu logischen Rechtsverschiebungen für Zahlen mit positivem Vorzeichen. Arithmetische Rechtsverschiebungen für negative Zahlen im N−1-Komplement (normalerweise Zweierkomplement ) sind ungefähr äquivalent zur Division durch eine Potenz der Basis (normalerweise 2), wobei für ungerade Zahlen nach unten gerundet wird (nicht auf 0, wie normalerweise erwartet).

Arithmetische Rechtsverschiebungen für negative Zahlen sind äquivalent zur Division durch Runden auf 0 in der Komplementdarstellung von Zahlen mit Vorzeichen, wie sie von einigen historischen Computern verwendet wurde, aber dies wird nicht mehr allgemein verwendet.

Umgang mit dem Problem in Programmiersprachen

Der (1999) ISO-Standard für die Programmiersprache C definiert den Rechtsverschiebungsoperator in Form von Divisionen durch Potenzen von 2. Wegen der oben genannten Nicht-Äquivalenz schließt der Standard ausdrücklich von dieser Definition die Rechtsverschiebungen von vorzeichenbehafteten Zahlen aus, die negative Werte. Es spezifiziert nicht das Verhalten des Rechtsverschiebungsoperators unter solchen Umständen, sondern erfordert stattdessen, dass jeder einzelne C-Compiler das Verhalten des Verschiebens negativer Werte nach rechts definiert.

Anwendungen

In Anwendungen, bei denen ein konsistentes Abrunden erwünscht ist, sind arithmetische Rechtsverschiebungen für vorzeichenbehaftete Werte nützlich. Ein Beispiel ist das Herunterskalieren von Rasterkoordinaten um eine Zweierpotenz, wodurch ein gleichmäßiger Abstand beibehalten wird. Zum Beispiel sendet eine Rechtsverschiebung um 1 0, 1, 2, 3, 4, 5, ... zu 0, 0, 1, 1, 2, 2, ... und −1, −2, −3, −4, ... bis −1, −1, −2, −2, ..., unter Beibehaltung eines gleichmäßigen Abstands als −2, −2, −1, −1, 0, 0, 1, 1, 2, 2 , ... Im Gegensatz dazu schickt eine ganzzahlige Division mit Rundung gegen Null −1, 0 und 1 alle auf 0 (3 Punkte statt 2), was −2, −1, −1, 0, 0, 0, 1 ergibt. 1, 2, 2, ... stattdessen, was bei 0 unregelmäßig ist.

Anmerkungen

  1. ^ Der >> Operator in C und C++ ist nicht unbedingt eine arithmetische Verschiebung. Normalerweise ist es nur eine arithmetische Verschiebung, wenn es mit einem vorzeichenbehafteten Integer-Typ auf der linken Seite verwendet wird. Wenn es stattdessen für einen vorzeichenlosen Integer-Typ verwendet wird, handelt es sich um eine logische Verschiebung.
  2. ^ Der arithmetische Rechtsverschiebungsoperator von Verilog führt nur dann tatsächlich eine arithmetische Verschiebung durch, wenn der erste Operand vorzeichenbehaftet ist. Wenn der erste Operand ohne Vorzeichen ist, führt der Operator tatsächlich eine logische Rechtsverschiebung durch.
  3. ^ Ob eine arithmetische Verschiebung nach links oder rechts erfolgt, hängtin der OpenVMS- Makrosprache davon ab, ob der zweite Operand positiv oder negativ ist. Dies ist ungewöhnlich. In den meisten Programmiersprachen haben die beiden Richtungen unterschiedliche Operatoren, wobei der Operator die Richtung angibt und der zweite Operand implizit positiv ist. (Einige Sprachen, z. B. Verilog, erfordern, dass negative Werte in positive Werte ohne Vorzeichen konvertiert werden. Einige Sprachen, z. B. C und C++, haben kein definiertes Verhalten, wenn negative Werte verwendet werden.)
  4. ^ In Schemearithmetic-shiftkann sowohl nach links als auch nach rechts verschoben werden, abhängig vom zweiten Operanden, sehr ähnlich der OpenVMS-Makrosprache, obwohl R6RS Scheme beide-rightund-leftVariantenhinzufügt.
  5. ^ DieBitsKlasse von HaskellsData.BitsModul definiert sowohlshiftein signiertes Argumentnehmen undshiftL/shiftRAufnahme unsigned Argumente. Diese sind isomorph ; für neue Definitionen braucht der Programmierer nur eines der beiden Formulare bereitzustellen und das andere Formular wird automatisch in Bezug auf das bereitgestellte definiert.
  6. ^ Der arithmetische VHDL-Linksverschiebungsoperator ist ungewöhnlich. Anstatt das LSB des Ergebnisses mit Null zu füllen, kopiert es das ursprüngliche LSB in das neue LSB. Dies ist zwar ein genaues Spiegelbild der arithmetischen Rechtsverschiebung, aber nicht die konventionelle Definition des Operators und entspricht nicht der Multiplikation mit einer Potenz von 2. Im VHDL 2008-Standard wurde dieses seltsame Verhalten unverändert belassen (aus Gründen der Abwärtskompatibilität ) für Argumenttypen, die keine erzwungene numerische Interpretation haben (zB BIT_VECTOR), aber 'SLA' für vorzeichenlose und vorzeichenbehaftete Argumenttypen verhält sich wie erwartet (dh die Positionen ganz rechts werden mit Nullen aufgefüllt). Die logische Verschiebung nach links (SLL) von VHDL implementiert die oben erwähnte arithmetische 'Standard'-Verschiebung.
  7. ^ Der C-Standard sollte die C-Sprache weder auf Einser-Komplement- noch auf Zweier-Komplement-Architekturen beschränken. In Fällen, in denen sich das Verhalten von Einser-Komplement- und Zweier-Komplement-Darstellungen wie diesem unterscheidet, verlangt der Standard, dass einzelne C-Compiler das Verhalten ihrer Zielarchitekturen dokumentieren. Die Dokumentation zur GNU Compiler Collection (GCC) beispielsweise dokumentiert ihr Verhalten als Verwendung von Sign-Extension.

Verweise

Querverweis

Verwendete Quellen

Gemeinfrei Dieser Artikel enthält  gemeinfreies Material aus dem Dokument General Services Administration : "Federal Standard 1037C" .