Aritmetický posun - Arithmetic shift - Wikipedia

Pravý 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ý bit je vyplněna nulou.
Operátory aritmetického posunu v různých programovacích jazycích a procesorech
Jazyk nebo procesorVlevo, odjetŽe jo
ActionScript 3, Jáva, JavaScript, Krajta, PHP, Rubín;
C, C ++,[1]D, C#, Jít, Julie, Rychlý (pouze podepsané typy)[poznámka 1]		 << >>
Ada Shift_Left [2] Shift_Right_Arithmetic
Kotlin shl shr
Standardní ML << ~>>
Verilog <<< >>> [poznámka 2]
OpenVMS makro jazyk@[Poznámka 3]
Systémaritmetický posun[poznámka 4]
Společný Lisppopel
OCamllslasr
HaskellData.Bits.shift[poznámka 5]
Shromáždění, 68 tisASLASR
Sestava, x86SALSAR
VHDLsla[poznámka 6]sra
Z80SLA[4]SRA

v programování, an aritmetický posun je operátor směny, někdy nazývané a podepsaná směna (i když to není omezeno na podepsané operandy). Dva základní typy jsou aritmetický posun vlevo a aritmetický posun doprava. Pro binární čísla to je bitový provoz který posune všechny bity svého operandu; každý bit v operandu se jednoduše přesune o daný počet bitových pozic a volné bitové pozice se vyplní. Místo vyplnění všemi 0s, jako v logický posun, při řazení doprava, nejvíce vlevo bit (obvykle znamení bit v podepsaných celočíselných reprezentacích) se replikuje, aby vyplnil všechna volná místa (jedná se o druh značka rozšíření ).

Někteří autoři dávají přednost termínům lepkavý pravý posun a nulový výplň doprava pro aritmetické a logické posuny.[5]

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énky mocninami dvou. Řazení doleva n bity na podepsané nebo nepodepsané binární číslo mají za následek vynásobení číslem 2n. Řazení přímo o n bity na a doplněk dvou podepsaný binární číslo má za následek vydělení 2n, ale vždy se to zaokrouhlí dolů (směrem k negativnímu nekonečnu). To se liší od způsobu zaokrouhlování obvykle v děleném celočíselném dělení (které se zaokrouhlí na 0). Tato nesrovnalost vedla k chybám v řadě překladačů.[6]

Například v sada instrukcí x86, instrukce SAR (aritmetický posun doprava) vydělí podepsané číslo mocninou dvou, zaokrouhlením směrem k zápornému nekonečnu.[7] Instrukce IDIV (rozdělené znaménko) však rozdělí podepsané číslo zaokrouhleno na nulu. Takže instrukci SAR nelze nahradit IDIV silou dvou instrukcí ani naopak.

Formální definice

Formální definice aritmetického posunu od Federální norma 1037C je to, že je:

Posun, aplikovaný na reprezentaci čísla v pevné základ systém číslování a v pevný bod reprezentační systém, 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 účinku jakéhokoli zaokrouhlování; porovnat logický posun s aritmetickým posunem, zejména v případě plovoucí bod zastoupení.

Důležité slovo v definici FS 1073C je „obvykle“.

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

Aritmetický vlevo, odjet posuny jsou ekvivalentní násobení (kladným, integrálním) výkonem radixu (např. násobení výkonem 2 pro binární čísla). Logické posuny doleva jsou také ekvivalentní, kromě toho, že se může aktivovat násobení a aritmetické posuny aritmetické přetečení zatímco logické posuny ne.

Nerovnocennost aritmetického posunu doprava a dělení

Nicméně aritmetické že jo posuny jsou hlavní pasti pro neopatrné, konkrétně při zaokrouhlování záporných celých čísel. Například obvyklým způsobem doplněk dvou reprezentace záporných celých čísel, −1 je 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á zaokrouhlování dolů (směrem k zápornému nekonečnu), ale není to obvyklá konvence pro dělení.

Často se uvádí, že aritmetické posuny doprava jsou ekvivalentní divize (kladnou, integrální) silou radixu (např. dělením mocninou 2 pro binární čísla), a proto toto dělení mocí radixu lze optimalizovat implementací jako aritmetický posun doprava. (Řazení je mnohem jednodušší než rozdělovač. U většiny procesorů se instrukce posunu provedou rychleji než pokyny k dělení.) Velký počet příruček, příruček a dalších specifikací od 60. a 70. let od společností a institucí, jako jsou DEC, IBM, Obecné údaje, a ANSI dělat taková nesprávná prohlášení [8][stránka potřebná ].

Logické posuny doprava jsou ekvivalentní dělení výkonem radixu (obvykle 2) pouze pro kladná nebo nepodepsaná čísla. Aritmetické posuny doprava jsou ekvivalentní logickým posunům vpravo pro kladná čísla se znaménkem. Aritmetické posuny doprava pro záporná čísla v doplňku N-1 (obvykle doplněk dvou ) je zhruba ekvivalent dělení výkonem radixu (obvykle 2), kde pro lichá čísla platí zaokrouhlování dolů (ne na 0, jak se obvykle očekávalo).

Aritmetické posuny doprava pro záporná čísla jsou ekvivalentní dělení pomocí zaokrouhlování na 0 palců něčí doplněk reprezentace podepsaných čísel, jak ji používali některé historické počítače, ale toto se již obecně nepoužívá.

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

Norma ISO pro programovací jazyk (1999) C definuje správného operátora směny, pokud jde o dělení o mocniny 2.[9] Kvůli výše uvedené nerovnocennosti standard výslovně vylučuje z této definice správné posuny podepsaných čísel, která mají záporné hodnoty. Nezadává chování operátoru správného posunu za takových okolností, ale místo toho vyžaduje, aby každý jednotlivý kompilátor jazyka C definoval chování posunu záporných hodnot doprava.[poznámka 7]

Aplikace

V aplikacích, kde je požadováno konzistentní zaokrouhlování dolů, jsou užitečné aritmetické posuny doprava pro podepsané hodnoty. Příklad je v downscaling rastrové souřadnice o síle dvou, která udržuje rovnoměrné rozestupy. Například posun doprava o 1 pošle 0, 1, 2, 3, 4, 5, ... na 0, 0, 1, 1, 2, 2, ... a −1, −2, −3, −4, ... až −1, −1, −2, −2, ..., 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 na nulu 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, který je nepravidelný v 0.

Poznámky

  1. ^ The >> operátor v C a C ++ nemusí být nutně aritmetický posun. Obvykle se jedná pouze o aritmetický posun, pokud je použit s celočíselným typem se znaménkem na jeho levé straně. Pokud se místo toho použije na celočíselný typ bez znaménka, bude to a logický posun.
  2. ^ Operátor aritmetického posunu doprava Verilog ve skutečnosti provede 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 a logický pravý posun.
  3. ^ V OpenVMS jazyk makra, zda je aritmetický posun vlevo nebo vpravo, je určen 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ě pozitivní. (Některé jazyky, například Verilog, vyžadují převod záporných hodnot na kladné hodnoty bez znaménka. Některé jazyky, například C a C ++, nemají definované chování, pokud se použijí záporné hodnoty.)[3][stránka potřebná ]
  4. ^ Ve schématu aritmetický posun může být levý i pravý posun, v závislosti na druhém operandu, velmi podobný jazyku maker OpenVMS, ačkoli schéma R6RS přidává -že jo a -vlevo, odjet varianty.
  5. ^ The Bity třídy od Haskella Data.Bits modul definuje obojí posun převzetí podepsaného argumentu a shiftL/shiftR převzetí nepodepsaných argumentů. Tyto jsou izomorfní; pro nové definice musí programátor poskytnout pouze jednu ze dvou forem a druhá forma bude automaticky definována z hlediska poskytnuté.
  6. ^ Operátor aritmetického řazení vlevo VHDL je neobvyklý. Namísto vyplnění LSB výsledku nulou zkopíruje původní LSB do nového LSB. I když se jedná o přesný zrcadlový obraz aritmetického posunu doprava, nejedná se o konvenční definici operátoru a není ekvivalentní násobení silou 2. Ve standardu VHDL 2008 bylo toto podivné chování ponecháno beze změny (pro zpětnou kompatibilitu) ) pro typy argumentů, které nemají vynucenou numerickou interpretaci (např. BIT_VECTOR), ale 'SLA' pro nepodepsaný a podepsaný typy argumentů se chovají očekávaným způsobem (tj. pozice zcela vpravo jsou vyplněny nulami). Logická funkce posunu vlevo od VHDL (SLL) implementuje výše uvedený 'standardní' aritmetický posun.
  7. ^ Účelem standardu C bylo neomezovat jazyk C na architekturu doplňku jednoho nebo dvou doplňků. V případech, kdy se chování reprezentace doplňku jedničky a reprezentace doplňku dvou liší, jako je tato, vyžaduje standard, aby jednotlivé kompilátory jazyka C dokumentovaly chování svých cílových architektur. Dokumentace pro Sbírka překladačů GNU (GCC) například dokumentuje své chování jako používání znakového rozšíření.[10]

Reference

Křížový odkaz

  1. ^ „Bit manipulation - Dlang Tour“. tour.dlang.org. Citováno 2019-06-23.
  2. ^ „Anotovaná referenční příručka Ada 2012“.
  3. ^ HP 2001.
  4. ^ "Syntaxe Assembleru Z80".
  5. ^ Thomas R. Cain a Alan T. Sherman.„Jak rozbít Giffordovu šifru“ Sekce 8.1: „Lepkavý versus nelepivý posun bitů“ .Cryptologia.1997.
  6. ^ Steele Jr., Guy. „Aritmetické posunutí považováno za škodlivé“ (PDF). Laboratoř MIT AI. Citováno 20. května 2013.
  7. ^ Hyde 1996, § 6.6.2.2 SAR.
  8. ^ Steele 1977.
  9. ^ ISOIEC9899 1999, § 6.5.7 Operátoři bitového posunu.
  10. ^ FSF 2008, § 4.5 Implementace celých čísel.

Použité zdroje

Tento článek zahrnujepublic domain materiál z Obecná správa služeb dokument: „Federální norma 1037C“.