Wikipedia

Deplasare aritmetică

operație la nivel de biți în informatică

În informatică, o deplasare aritmetică este o operație pe biți⁠(d) care schimbă toți biții operandului său. Cele două variante de bază sunt deplasarea aritmetică la stânga și deplasarea aritmetică la dreapta. Aceasta este comandată de numărul de poziții de biți pe care o anumită valoare va fi deplasată, cum ar fi deplasare la stânga cu 1 poziție sau deplasare la dreapta cu n poziții. Fiecare bit din operand este mutat un număr dat de poziții de biți, iar pozițiile de biți libere sunt completate cu zerouri la drepta, respectiv cu valoarea din primul bit (bitul semn⁠(d)) la stânga.

O deplasare aritmetică la dreapta a unui număr binar cu 1 poziție. Poziția goală din bitul cel mai semnificativ este completată cu o copie a bitului original.
Notă:
MSB = bitul cel mai semnificativ,
LSB = bitul cel mai puțin semnificativ.
O deplasare aritmetică la stânga a unui număr binar cu 1 poziție. Poziția goală din bitul cel mai puțin semnificativ este completată cu 0.
Operatori de deplasare aritmetică în diverse limbaje de programare și procesoare
Limbaj sau procesor Stânga Dreapta
ActionScript 3, Java, JavaScript, Python, PHP, Ruby;
C, C++,[1]D, C#, Go, Julia, Swift (doar tipuri fără semn)[a]		 << >>
Ada Shift_Left [2] Shift_Right_Arithmetic
Kotlin shl shr
Standard ML << ~>>
Verilog <<< >>> [b]
Limbajul macro OpenVMS @[c][3]
Scheme arithmetic-shift[d]
Common Lisp ash
OCaml lsl asr
Haskell Data.Bits.shift[e]
Asamblor, 68k ASL ASR
Asamblor, x86 SAL SAR
VHDL sla[f] sra
RISC-V sll, slli[4] sra, srai
Z80 SLA[5] SRA

Deplasările aritmetice pot fi utile ca modalități eficiente de a efectua înmulțirea sau împărțirea numerelor întregi cu semn cu puteri ale lui 2. Deplasarea la stânga cu n biți a unui număr binar cu semn sau fără semn are ca efect înmulțirea acestuia cu 2n. Deplasarea la dreapta cu n biți a unui complement față de doi cu semn are efectul de a-l împărți la 2n, dar se rotunjește întotdeauna în jos (spre infinitul negativ). Acest lucru este diferit de modul în care rotunjirea se face de obicei la împărțirea întregilor cu semn (care se rotunjește spre 0). Această discrepanță a dus la erori într-un număr de compilatoare.[6] De exemplu, în setul de instrucțiuni al x86, instrucțiunea SAR (deplasare aritmetică la dreapta) împarte un număr cu semn la o putere a lui 2, rotunjind spre infinitul negativ,[7] însă, instrucțiunea IDIV (împărțire cu semn) împarte un număr cu semn rotunjind spre zero. Deci o instrucțiune SAR nu poate fi înlocuită de un IDIV și nici invers.

Definiție formală

modificare

Definiția formală a unei deplasări aritmetice, din Standardul federal 1037C este:

O deplasare, aplicată reprezentării unui număr într-un sistem de numerație cu o bază de numerație fixă și într-un sistem de reprezentare în virgulă fixă, mută doar caracterele din partea reprezentată în virgulă fixă a numărului. O deplasare aritmetică este de obicei echivalentă cu înmulțirea numărului cu o putere întreagă pozitivă sau negativă a bazei de numerație, cu excepția efectului vreunei rotunjiri; a se compara deplasarea logică cu deplasarea aritmetică, mai ales în cazul reprezentării în virgulă mobilă.

O expresie importantă în definiția FS 1073C este „de obicei”.

Echivalența deplasărilor aritmetice și logice la stânga cu înmulțirea

modificare

Deplasările aritmetice la stânga sunt echivalente cu înmulțirea cu o putere (pozitivă, întreagă) a bazei de numerație (de exemplu, o înmulțire cu o putere a lui 2 pentru numerele binare). Deplasările logice la stânga sunt, de asemenea, echivalente, cu excepția faptului că înmulțirile și deplasările aritmetice pot declanșa depășirea aritmetică⁠(d) (întreagă), în timp ce deplasările logice nu.

Neechivalența deplasărilor aritmetice la dreapta cu împărțirea

modificare

Deplasările aritmetice dreapta sunt capcane majore pentru cei imprudenți, în special în tratarea rotunjirii numerelor întregi negative. De exemplu, în reprezentarea obișnuită în complement față de doi a numerelor întregi negative, −1 este reprezentat cu toate cifrele binare „1”. Pentru un număr întreg cu semn pe 8 biți, acesta este 1111 1111. O deplasare aritmetică la dreapta cu 1 (sau 2, 3, ..., 7) dă tot 1111 1111, care este tot −1. Aceasta corespunde rotunjirii în jos (spre infinit negativ), dar nu este convenția obișnuită la împărțire.

Se afirmă frecvent că deplasările aritmetice la dreapta sunt echivalente cu împărțirea la o putere (pozitivă, integrală) a bazei de numerație (de exemplu, o împărțire cu o putere a lui 2 pentru numere binare) și, prin urmare, că diviziunea cu o putere a bazei poate fi optimizată prin implementarea acesteia ca o deplasare aritmetică la dreapta. (O deplasare este mult mai simplă decât o împărțire. La majoritatea procesoarelor, instrucțiunile de deplasare se vor executa mai rapid decât instrucțiunile de împărțire.) Un mare număr de manuale de programare și alte specificații din anii 1960 și 1970 de la companii și instituții precum DEC, IBM, Data General și ANSI fac astfel de declarații incorecte.[8].

Deplasările logice la dreapta sunt echivalente cu împărțirea cu o putere a bazei (de obicei 2) numai pentru numerele pozitive sau fără semn. Deplasările aritmetice la dreapta sunt echivalente cu deplasările logice la dreapta pentru numerele cu semn pozitiv. Deplasările aritmetice la dreapta pentru numerele negative în complementul lui N−1 (de obicei complementul față de doi) sunt aproximativ echivalente cu împărțirea cu o putere a bazei (de obicei 2), unde pentru numerele impare se aplică rotunjirea în jos (nu spre 0, ca de obicei).

Deplasările aritmetice la dreapta pentru numerele negative sunt echivalente cu împărțirea folosind rotunjirea spre 0 în reprezentarea numerelor cu semn în complement față de unu⁠(d), așa cum a fost folosit de unele calculatoare istorice, dar acest lucru nu mai este de uz general.

Gestionarea problemei în limbajele de programare

modificare

Standardul ISO (1999) pentru limbajul de programare C definește operatorul de deplasare la dreapta în termenii împărțirii la puteri ale lui 2.[9] Din cauza neechivalenței menționate mai sus, standardul exclude în mod explicit din această definiție deplasările la dreapta ale numerelor cu semn care au valori negative. Nu specifică comportamentul operatorului de deplasare la dreapta în astfel de circumstanțe, ci solicită ca pentru fiecare compilator C să de definească individual comportamentul deplasării la dreapta a valorilor negative.[11]

Aplicații

modificare

În aplicațiile în care se dorește o rotunjire consecventă în jos, sunt utile deplasările aritmetice la dreapta pentru valorile cu semn. Un exemplu este în scalarea în jos a coordonatelor de tip raster cu o putere a lui doi, care menține spațierea uniformă. De exemplu, deplasarea la dreapta cu 1 trimite 0, 1, 2, 3, 4, 5, ... la 0, 0, 1, 1, 2, 2, ... și −1, −2, −3, −4, ... la −1, −1, −2, −2, ..., menținând spațierea pară ca −2, −2, −1, −1, 0, 0, 1, 1, 2, 2 , ... Prin contrast, împărțirea întregilor cu rotunjire spre zero trimite pe toate −1, 0 și 1 la 0 (3 puncte în loc de 2), rezultând −2, −1, −1, 0, 0, 0, 1, 1, 2, 2, ... , care este neregulat în 0.

Note explicative

modificare
  1. ^ Operatorul >> în C și C++ nu este neapărat o deplasare aritmetică. De obicei, este o deplasare aritmetică dacă primul operand este un întreg cu semn. Dacă primul operand este un întreg fără semn, va fi o deplasare logică.
  2. ^ Operatorul de deplasare aritmetică dreapta Verilog efectuează de fapt o deplasare aritmetică numai dacă primul operand este un întreg cu semn. Dacă primul operand este un întreg fără semn, operatorul efectuează de fapt o deplasare logică la dreapta.
  3. ^ În limbajul macro OpenVMS, faptul că o deplasare aritmetică este la stânga sau la dreapta este determinat de faptul dacă al doilea operand este pozitiv sau negativ. Acest lucru este neobișnuit. În majoritatea limbajelor de programare cele două direcții au operatori diferiți, operatorul specificând direcția, iar al doilea operand este implicit pozitiv. (Unele limbaje, cum ar fi Verilog, necesită ca valorile negative să fie convertite în valori pozitive fără semn. Unele limbaje, cum ar fi C și C++, nu au un comportament definit dacă sunt utilizate valori negative.)
  4. ^ În Scheme arithmetic-shift poate fi atât deplasare la stânga cât și la dreapta, în funcție de al doilea operand, foarte asemănătoare cu limbajul macro OpenVMS, deși R6RS Scheme le adaugă pe ambele variante -right și -left.
  5. ^ Clasa Bits a Data.Bits din modulul Haskell definește atât shift pentru un argument cu semn, cât și shiftL/shiftR pentru argumente fără semn. Acestea sunt izomorfe; pentru definiții noi, programatorul trebuie să furnizeze doar una dintre cele două forme, iar cealaltă formă va fi definită automat în funcție de cea furnizată.
  6. ^ Operatorul de deplasare stânga aritmetică VHDL este neobișnuit. În loc să umple bitul cel mai puțin semnificativ cu 0, acesta copiază acolo bitul original. În timp ce aceasta este o imagine exactă în oglindă a deplasării aritmetice la dreapta, nu este definiția convențională a operatorului și nu este echivalentă cu înmulțirea cu o putere a lui 2. În standardul VHDL 2008, acest comportament ciudat a fost lăsat neschimbat (pentru compatibilitate „în jos”) pentru tipurile de argumente care nu au interpretare numerică forțată (de exemplu, BIT_VECTOR), dar „SLA” pentru tipurile de argument su semn (în engleză unsigned) și fără semn (în engleză signed) se comportă în modul așteptat (adică, pozițiile din dreapta sunt umplute cu zerouri). Funcția logică de deplasare stânga (SLL) a lui VHDL implementează schimbarea aritmetică „standard” menționată mai sus.

Note

modificare
  1. ^ en „Bit manipulation - Dlang Tour”. tour.dlang.org. Accesat în . 
  2. ^ en „Annotated Ada 2012 Reference Manual”. 
  3. ^ HP 2001.
  4. ^ en „The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA” (PDF). GitHub. . pp. 18–20. Arhivat din original (PDF) la . Accesat în . 
  5. ^ en „Z80 Assembler Syntax”. 
  6. ^ en Steele Jr, Guy. „Arithmetic Shifting Considered Harmful” (PDF). MIT AI Lab. Arhivat din original (PDF) la . Accesat în . 
  7. ^ Hyde 1996, § 6.6.2.2 SAR.
  8. ^ Steele 1977.
  9. ^ ISOIEC9899 1999, § 6.5.7 Bitwise shift operators (în română § 6.5.7 Operatori de deplasare pe biți).
  10. ^ FSF 2008, § 4.5 Integers implementation.
  11. ^ Standardul C a fost menit să nu restrângă limbajul C fie la arhitecturile în complement față de unu, fie la cele în complement față de doi. În cazurile în care comportamentele reprezentărilor în complement față de unu și în complement față de doi diferă, standardul cere documentarea individuală a comportării compilatoarelor C în arhitecturile respective. Documentația pentru GNU Compiler Collection (GCC), de exemplu, documentează comportamentul său ca utilizând extensia semnului.[10]

Bibliografie

modificare
  Portal Informatică
  Portal Matematică
Adus de la https://ro.wikipedia.org/w/index.php?title=Deplasare_aritmetică&oldid=15285983