Przesunięcie arytmetyczne - Arithmetic shift

Przesunięcie arytmetyczne w prawo liczby binarnej o 1. Pusta pozycja w najbardziej znaczącym bicie jest wypełniona kopią oryginalnego MSB.
Przesunięcie arytmetyczne w lewo liczby binarnej o 1. Pusta pozycja najmniej znaczącego bitu jest wypełniona zerem.
Operatory przesunięcia arytmetycznego w różnych językach programowania i procesorach
Język lub podmiot przetwarzający Lewo Dobrze
ActionScript 3, Java , JavaScript , Python , PHP , Ruby ;
C , C++ , D , C# , Go , Julia , Swift (tylko typy ze znakiem)		 << >>
Ada Shift_Left Shift_Right_Arithmetic
Kotlin shl shr
Standardowy ML << ~>>
Verilog <<< >>>
Język makr OpenVMS @
Schemat arithmetic-shift
Wspólne seplenienie ash
OCaml lsl asr
Haskell Data.Bits.shift
Montaż, 68k ASL ASR
Montaż, x86 SAL SAR
VHDL sla sra
RISC-V sll, slli sra, srai
Z80 SLA SRA

W programowaniu komputerowym , arytmetyczne przesunięcie jest operatorem shift , czasami określany jako podpisaną zmianę (choć nie jest ograniczony do podpisanych argumentów). Dwa podstawowe typy to arytmetyczne przesunięcie w lewo i arytmetyczne przesunięcie w prawo . W przypadku liczb binarnych jest to operacja bitowa, która przesuwa wszystkie bity swojego operandu; każdy bit w operandzie jest po prostu przesuwany o określoną liczbę pozycji bitowych, a puste pozycje bitowe są wypełniane. Zamiast wypełniania wszystkimi zerami, jak w przypadku przesunięcia logicznego , podczas przesuwania w prawo, najbardziej lewy bit (zazwyczaj bit znaku w reprezentacjach liczb całkowitych ze znakiem ) jest replikowany w celu wypełnienia wszystkich wolnych miejsc (jest to rodzaj rozszerzenia znaku ).

Niektórzy autorzy preferują terminy sticky right-shift i zero-fill right-shift odpowiednio dla przesunięć arytmetycznych i logicznych.

Przesunięcia arytmetyczne mogą być przydatne jako skuteczne sposoby mnożenia lub dzielenia liczb całkowitych ze znakiem przez potęgi dwójki. Przesunięcie w lewo o n bitów na liczbie binarnej ze znakiem lub bez znaku powoduje pomnożenie jej przez 2 n . Przesunięcie w prawo o n bitów na A uzupełnienie dwójkowe podpisany liczba binarna ma wpływ dzieląc ją przez 2 n , ale zawsze zaokrągla w dół (w kierunku ujemnym nieskończoność). Różni się to od sposobu, w jaki zwykle wykonuje się zaokrąglanie przy dzieleniu liczb całkowitych ze znakiem (które zaokrągla się do 0). Ta rozbieżność doprowadziła do błędów w wielu kompilatorach.

Na przykład w zestawie instrukcji x86 instrukcja SAR (arytmetyczne przesunięcie w prawo) dzieli liczbę ze znakiem przez potęgę dwójki, zaokrąglając w kierunku ujemnej nieskończoności. Jednak instrukcja IDIV (dzielenie ze znakiem) dzieli liczbę ze znakiem, zaokrąglając do zera. Tak więc instrukcja SAR nie może być zastąpiona instrukcją IDIV mocą dwóch instrukcji ani odwrotnie.

Formalna definicja

Formalna definicja przesunięcia arytmetycznego z Federalnego Standardu 1037C brzmi:

Przesunięcie, zastosowano do reprezentacji liczby w stałej radix systemu numeracji oraz w stałym punkcie systemu reprezentację, w którym tylko znaki stanowiące część stałoprzecinkowych liczby zostały przeniesione. Przesunięcie arytmetyczne jest zwykle równoważne pomnożeniu liczby przez dodatnią lub ujemną całkowitą potęgę podstawy, z wyjątkiem efektu zaokrąglenia; porównaj przesunięcie logiczne z przesunięciem arytmetycznym, szczególnie w przypadku reprezentacji zmiennoprzecinkowej .

Ważnym słowem w definicji FS 1073C jest „zazwyczaj”.

Równoważność arytmetycznych i logicznych przesunięć w lewo i mnożenia

Arytmetyczne przesunięcia w lewo są równoważne mnożeniu przez (dodatnią, całkową) potęgę podstawy (np. mnożenie przez potęgę 2 dla liczb binarnych). Logiczne przesunięcia w lewo są również równoważne, z wyjątkiem tego, że mnożenie i przesunięcia arytmetyczne mogą wywołać przepełnienie arytmetyczne, podczas gdy przesunięcia logiczne nie.

Nierównoważność arytmetycznego przesunięcia w prawo i dzielenia

Jednak arytmetyczne przesunięcia w prawo są główną pułapką dla nieostrożnych, szczególnie w przypadku zaokrąglania ujemnych liczb całkowitych. Na przykład w zwykłej reprezentacji ujemnej liczby całkowitej przez uzupełnienie do dwóch , -1 jest reprezentowane jako same jedynki. Dla 8-bitowej liczby całkowitej ze znakiem jest to 1111 1111. Arytmetyczne przesunięcie w prawo o 1 (lub 2, 3, ..., 7) daje ponownie 1111 1111, co nadal wynosi -1. Odpowiada to zaokrąglaniu w dół (w kierunku ujemnej nieskończoności), ale nie jest to zwykła konwencja dzielenia.

Często mówi się, że arytmetyczne przesunięcia w prawo są równoważne dzieleniu przez (dodatnią, całkową) potęgę podstawy (np. dzielenie przez potęgę 2 dla liczb binarnych), a zatem dzielenie przez potęgę podstawy może być zoptymalizowany poprzez wdrożenie go jako arytmetycznego przesunięcia w prawo. (Przesuwnik jest znacznie prostszy niż dzielnik. Na większości procesorów instrukcje przesunięcia działają szybciej niż instrukcje dzielenia.) Duża liczba podręczników programowania, podręczników i innych specyfikacji z lat 60. i 70. z firm i instytucji, takich jak DEC , IBM , Data General , a ANSI składa takie niepoprawne oświadczenia .

Logiczne przesunięcia w prawo są równoważne dzieleniu przez potęgę podstawy (zwykle 2) tylko dla liczb dodatnich lub bez znaku. Arytmetyczne przesunięcia w prawo są równoważne logicznym przesunięciom w prawo dla dodatnich liczb ze znakiem. Arytmetyczne przesunięcie w prawo dla liczb ujemnych w uzupełnieniu N−1 (zazwyczaj dopełnienie do dwóch ) jest z grubsza równoważne dzieleniu przez potęgę podstawy (zwykle 2), gdzie dla liczb nieparzystych stosuje się zaokrąglanie w dół (nie w kierunku 0, jak zwykle oczekiwano).

Arytmetyczne przesunięcia w prawo dla liczb ujemnych są równoważne dzieleniu przy użyciu zaokrąglania do 0 w reprezentacji uzupełnienia liczb ze znakiem, jak to było używane w niektórych historycznych komputerach, ale nie jest to już powszechne.

Obsługa problemu w językach programowania

Norma ISO (1999) dla języka programowania C definiuje operator przesunięcia w prawo w kategoriach dzielenia przez potęgi 2. Ze względu na powyższą nierównoważność, norma wyraźnie wyłącza z tej definicji przesunięcia w prawo liczb ze znakiem, które mają wartości ujemne. Nie określa zachowania operatora przesunięcia w prawo w takich okolicznościach, ale zamiast tego wymaga, aby każdy indywidualny kompilator C zdefiniował zachowanie przesunięcia wartości ujemnych w prawo.

Aplikacje

W zastosowaniach, w których pożądane jest spójne zaokrąglanie w dół, przydatne są arytmetyczne przesunięcia w prawo dla wartości ze znakiem. Przykładem jest skalowanie w dół współrzędnych rastrowych o potęgę dwójki, co pozwala zachować równe odstępy. Na przykład przesunięcie w prawo o 1 powoduje wysłanie 0, 1, 2, 3, 4, 5, ... do 0, 0, 1, 1, 2, 2, ... i −1, −2, −3, -4, ... do -1, -1, -2, -2, ..., zachowując równe odstępy jako -2, -2, -1, -1, 0, 0, 1, 1, 2, 2 , ... W przeciwieństwie do tego, dzielenie liczb całkowitych z zaokrągleniem do zera wysyła -1, 0 i 1 wszystkie do 0 (3 punkty zamiast 2), dając -2, -1, -1, 0, 0, 0, 1, 1, 2, 2, ... zamiast tego, co jest nieregularne przy 0.

Uwagi

  1. ^ Operator C i C ++, niekoniecznie jest arytmetyka przesunięcie. Zwykle jest to tylko przesunięcie arytmetyczne, jeśli jest używane z typem liczby całkowitej ze znakiem po lewej stronie. Jeśli zamiast tego zostanie użyty na typie liczby całkowitej bez znaku, będzie toprzesunięcie logiczne . >>
  2. ^ Operator arytmetycznego przesunięcia w prawo Verilog w rzeczywistości wykonuje arytmetyczne przesunięcie tylko wtedy, gdy pierwszy operand jest podpisany. Jeśli pierwszy operand nie ma znaku, operator faktycznie wykonuje logiczne przesunięcie w prawo.
  3. ^ Wjęzyku makr OpenVMS , czy przesunięcie arytmetyczne jest w lewo czy w prawo jest określane przez to, czy drugi argument jest dodatni czy ujemny. To niezwykłe. W większości języków programowania oba kierunki mają różne operatory, z operatorem określającym kierunek, a drugi operand jest niejawnie dodatni. (Niektóre języki, takie jak Verilog, wymagają konwersji wartości ujemnych na wartości dodatnie bez znaku. Niektóre języki, takie jak C i C++, nie mają zdefiniowanego zachowania, jeśli używane są wartości ujemne.)
  4. ^ W Schemearithmetic-shiftmoże być przesunięcie zarówno w lewo jak iw prawo, w zależności od drugiego operandu, bardzo podobne do języka makr OpenVMS, chociaż Schemat R6RS dodaje oba-righti-leftwarianty.
  5. ^ Klasa od Haskell jestmoduł definiuje zarównobiorąc podpisaną argument i/biorąc niepodpisanych argumenty. Są to izomorficzne ; w przypadku nowych definicji programista musi podać tylko jeden z dwóch formularzy, a drugi formularz zostanie automatycznie zdefiniowany zgodnie z podanym.BitsData.BitsshiftshiftLshiftR
  6. ^ Operator arytmetyczny lewej zmiany VHDL jest nietypowy. Zamiast wypełniać LSB wyniku zerem, kopiuje oryginalną LSB do nowej LSB. Chociaż jest to dokładne lustrzane odbicie arytmetycznego przesunięcia w prawo, nie jest to konwencjonalna definicja operatora i nie jest tożsama z mnożeniem przez potęgę 2. W standardzie VHDL 2008 to dziwne zachowanie pozostawiono bez zmian (dla kompatybilności wstecznej ) dla typów argumentów, które nie zostały zmuszone interpretację numerycznej (np BIT_VECTOR), ale „” SLA dla niepodpisane i podpisane typy argumentów zachowuje się w oczekiwanym sposób (czyli pozycji skrajnie prawe są wypełnione zerami). Funkcja logiczna shift w lewo (SLL) VHDL implementuje wyżej wspomniane "standardowe" przesunięcie arytmetyczne.
  7. ^ Standard C miał nie ograniczać języka C do architektur dopełnienia jednego lub dwóch. W przypadkach, w których zachowania dopełnienia jedynki i reprezentacje dopełnienia do dwóch różnią się, na przykład, standard wymaga, aby poszczególne kompilatory C dokumentowały zachowanie ich architektur docelowych. Na przykład dokumentacja GNU Compiler Collection (GCC) dokumentuje jego zachowanie jako stosujące rozszerzenie znaku.

Bibliografia

Odsyłacz

Użyte źródła

Domena publiczna Ten artykuł zawiera  materiał z domeny publicznej z dokumentu General Services Administration : „Federal Standard 1037C” .