Aritmetický posun - Arithmetic shift

Správný aritmetický posun binárního čísla o 1. Prázdná pozice v nejvýznamnějším bitu je vyplněna kopií původního MSB.
Levý aritmetický posun binárního čísla o 1. Prázdná pozice v nejméně významném bitu je vyplněna nulou.
Operátory aritmetického posunu v různých programovacích jazycích a procesorech
Jazyk nebo procesor Vlevo, odjet Že jo
ActionScript 3, Java , JavaScript , Python , PHP , Ruby ;
C , C ++ , D , C# , Go , Julia , Swift (pouze podepsané typy)
<< >>
Ada Shift_Left Shift_Right_Arithmetic
Kotlin shl shr
Standardní ML << ~>>
Verilog <<< >>>
Jazyk makra OpenVMS @
Systém arithmetic-shift
Lisp ash
OCaml lsl asr
Haskell Data.Bits.shift
Montáž, 68 tis ASL ASR
Sestava, x86 SAL SAR
VHDL sla sra
RISC-V sll, slli sra, srai
Z80 SLA SRA

V programování počítače , An aritmetický posun je operátor posun , někdy nazývaný podepsanou posun (i když to není omezen jen na podepsaných operandy). Dva základní typy jsou aritmetický posun doleva a aritmetický posun doprava . U binárních čísel je to bitová operace, která přesouvá všechny bity svého operandu; každý bit v operandu je jednoduše přesunut o daný počet bitových pozic a prázdné bitové pozice jsou vyplněny. Místo toho, aby byly vyplněny všemi 0 s, jako v logickém posunu , při posunu doprava, bit úplně vlevo (obvykle sign bit v podepsaných celočíselných reprezentacích) se replikuje, aby se vyplnily všechny volné pozice (jedná se o jakési rozšíření znaménka ).

Někteří autoři pro aritmetické a logické posuny upřednostňují výrazy sticky right-shift a zero-fill right-shift .

Aritmetické posuny mohou být užitečné jako efektivní způsoby provádění násobení nebo dělení celých čísel se znaménkem mocninami dvou. Posun vlevo o n bitů na binárním čísle se znaménkem nebo bez znaménka má za následek jeho vynásobení 2 n . Posun doprava o n bitů na dvojkové binární číslo se znaménkem komplementu má za následek jeho rozdělení na 2 n , ale vždy se zaokrouhlí dolů (směrem k zápornému nekonečnu). To se liší od způsobu, jakým se zaokrouhlování obvykle provádí v děleném celočíselném dělení (které se zaokrouhluje směrem k 0). Tato nesrovnalost vedla k chybám v řadě překladačů.

Například v instrukční sadě x86 instrukce SAR (aritmetický posun doprava) rozdělí podepsané číslo o mocninu dvě a zaokrouhlí se směrem k zápornému nekonečnu. Instrukce IDIV (podepsaná předěl) však rozdělí podepsané číslo a zaokrouhlí se směrem k nule. Instrukci SAR tedy nelze nahradit IDIV mocninou dvou instrukcí, ani naopak.

Formální definice

Formální definice aritmetického posunu z federální normy 1037C zní, že je:

Posun, aplikovaný na reprezentaci čísla v pevném radixovém číslovacím systému a v reprezentačním systému s pevným bodem , a ve kterém jsou přesunuty pouze znaky představující část čísla s pevným bodem. Aritmetický posun je obvykle ekvivalentní vynásobení čísla kladnou nebo zápornou integrální silou radixu, s výjimkou vlivu jakéhokoli zaokrouhlení; porovnat logický posun s aritmetickým posunem, zejména v případě reprezentace s plovoucí desetinnou čárkou .

Důležitým slovem v definici FS 1073C je „obvykle“.

Ekvivalence aritmetických a logických posunů doleva a násobení

Aritmetické posuny doleva jsou ekvivalentní násobení (kladným, integrálním) výkonem radixu (např. Násobení mocninou 2 pro binární čísla). Logické posuny doleva jsou také ekvivalentní, kromě násobení a aritmetických posunů může spouštět aritmetické přetečení, zatímco logické posuny nikoli.

Nekompatibilita aritmetického posunu a dělení vpravo

Aritmetické posuny doprava jsou však hlavní pastí pro neopatrné, konkrétně při léčbě zaokrouhlování záporných celých čísel. Například v obvyklé dvojkové komplementární reprezentaci záporných celých čísel je −1 reprezentováno jako všechna 1. Pro 8bitové celé číslo se znaménkem je to 1111 1111. Aritmetický posun doprava o 1 (nebo 2, 3, ..., 7) získá znovu 1111 1111, což je stále -1. To odpovídá zaokrouhlení dolů (směrem k zápornému nekonečnu), ale není to obvyklá konvence pro dělení.

Často se uvádí, že aritmetické posuny vpravo jsou ekvivalentní dělení (kladnou, integrální) mocninou radixu (např. Dělení mocninou 2 pro binární čísla), a proto toto dělení mocninou radixu může být optimalizováno implementací jako aritmetický posun doprava. (Řadič je mnohem jednodušší než dělič. U většiny procesorů se pokyny k řazení budou provádět rychleji než pokyny k dělení.) Velké množství programovacích příruček, příruček a dalších specifikací z 60. a 70. let od společností a institucí, jako jsou DEC , IBM , Data General a ANSI dělají taková nesprávná prohlášení.

Logické posuny doprava jsou ekvivalentní dělení mocninou radixu (obvykle 2) pouze pro kladná nebo nepodepsaná čísla. Aritmetické posuny doprava jsou ekvivalentní logickým posunům doprava pro kladná znaménková čísla. Aritmetické posuny doprava pro záporná čísla v doplňku N − 1 (obvykle dvojkový doplněk ) je zhruba ekvivalentní dělení mocninou radixu (obvykle 2), kde pro lichá čísla se používá zaokrouhlování dolů (ne směrem k 0, jak se obvykle očekává).

Aritmetické posuny doprava pro záporná čísla jsou ekvivalentní dělení pomocí zaokrouhlování směrem k 0 v něčí komplementární reprezentaci podepsaných čísel, jak používaly některé historické počítače, ale toto se již běžně nepoužívá.

Řešení problému v programovacích jazycích

Norma ISO (1999) pro programovací jazyk C definuje operátora správného posunu, pokud jde o dělení mocninami 2. Z důvodu výše uvedené neekvivalence norma z této definice výslovně vylučuje správné posuny podepsaných čísel, která mají záporné hodnoty. Neurčuje chování operátoru správného posunu za takových okolností, ale místo toho vyžaduje, aby každý jednotlivý kompilátor C definoval chování při posunu záporných hodnot doprava.

Aplikace

V aplikacích, kde je požadováno konzistentní zaokrouhlování dolů, jsou aritmetické posuny doprava pro podepsané hodnoty užitečné. Příkladem je zmenšování rastrových souřadnic o mocninu dvou, které udržuje rovnoměrné mezery. Například posun doprava o 1 posílá 0, 1, 2, 3, 4, 5, ... na 0, 0, 1, 1, 2, 2, ... a −1, −2, −3, −4, ... až −1, −1, −2, −2, ... při zachování rovnoměrných mezer jako −2, −2, −1, −1, 0, 0, 1, 1, 2, 2 , ... Naproti tomu celočíselné dělení se zaokrouhlováním směrem k nule posílá −1, 0 a 1 vše na 0 (3 body místo 2), čímž se získá −2, −1, −1, 0, 0, 0, 1, 1, 2, 2, ... místo toho, což je při 0 nepravidelné.

Poznámky

  1. ^ Operátor v C a C ++ není nutně aritmetický posun. Obvykle se jedná pouze o aritmetický posun, pokud je použit s typem celého čísla se znaménkem na levé straně. Pokud se místo toho použije na celočíselném typu bez znaménka, bude to logický posun. >>
  2. ^ Operátor aritmetického pravého posunu Verilog ve skutečnosti provádí aritmetický posun pouze v případě, že je podepsán první operand. Pokud je první operand bez znaménka, operátor ve skutečnosti provede logický posun doprava.
  3. ^ Vjazyce makra OpenVMS je to , zda je aritmetický posun doleva nebo doprava, určeno tím, zda je druhý operand kladný nebo záporný. To je neobvyklé. Ve většině programovacích jazyků mají dva směry odlišné operátory, přičemž operátor určuje směr, a druhý operand je implicitně kladný. (Některé jazyky, například Verilog, vyžadují převedení záporných hodnot na kladné hodnoty bez znaménka. Některé jazyky, například C a C ++, nemají žádné definované chování, pokud jsou použity záporné hodnoty.)
  4. ^ Ve schématuarithmetic-shiftmůže být posun vlevo i vpravo, v závislosti na druhém operandu, velmi podobný jazyku makra OpenVMS, ačkoli schéma R6RS přidává obojí-righta-leftvarianty.
  5. ^ Třída z Haskellumodulu se definujepři podepsanou řízení a/při nepodepsané argumenty. Ty jsou izomorfní ; pro nové definice musí programátor poskytnout pouze jednu ze dvou formulářů a druhá forma bude automaticky definována z hlediska poskytnuté.BitsData.BitsshiftshiftLshiftR
  6. ^ Aritmetický levý řadič VHDL je neobvyklý. Namísto naplnění LSB výsledku nulou zkopíruje původní LSB do nového LSB. Přestože se jedná o přesný zrcadlový obraz aritmetického posunu doprava, nejedná se o konvenční definici operátora a není ekvivalentní násobení mocninou 2. Ve standardu VHDL 2008 zůstalo toto podivné chování nezměněno (kvůli zpětné kompatibilitě) ) pro typy argumentů, které nemají vynucenou numerickou interpretaci (např. BIT_VECTOR), ale „SLA“ pro nepodepsané a podepsané typy argumentů se chová očekávaným způsobem (tj. poziceúplněvpravo jsou vyplněny nulami). Funkce VHDL posun vlevo logická (SLL) implementuje výše uvedený „standardní“ aritmetický posun.
  7. ^ Standard C byl zamýšlel neomezovat jazyk C buď komplementu nebo architektury komplementu dvou. V případech, kdy se chování reprezentací komplementu jedničky a komplementu dvojice liší, jako je tento, standard vyžaduje, aby jednotlivé kompilátory C dokumentovaly chování jejich cílových architektur. Dokumentace pro GNU Compiler Collection (GCC) například dokumentuje jeho chování jako použití prodloužení znaku.

Reference

Křížový odkaz

Použité zdroje

Veřejná doména Tento článek včlení  materiál public domain z dokumentu General Services Administration : "Federal Standard 1037C" .