Deplasare aritmetică
![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Rotate_right_arithmetically.svg/230px-Rotate_right_arithmetically.svg.png)
Notă:
MSB = bitul cel mai semnificativ,
LSB = bitul cel mai puțin semnificativ.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Rotate_left_logically.svg/230px-Rotate_left_logically.svg.png)
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
|
Î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.
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 | modificare sursă]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 | modificare sursă]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 | modificare sursă]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 | modificare sursă]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 | modificare sursă]Î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 | modificare sursă]- ^ 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ă. - ^ 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.
- ^ Î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.)
- ^ Î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
. - ^ Clasa
Bits
aData.Bits
din modulul Haskell definește atâtshift
pentru un argument cu semn, cât șishiftL
/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ă. - ^ 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 | modificare sursă]- ^ en „Bit manipulation - Dlang Tour”. tour.dlang.org. Accesat în .
- ^ en „Annotated Ada 2012 Reference Manual”.
- ^ HP 2001.
- ^ en „The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA” (PDF). GitHub. . pp. 18–20. Arhivat din original (PDF) la . Accesat în .
- ^ en „Z80 Assembler Syntax”.
- ^ en Steele Jr, Guy. „Arithmetic Shifting Considered Harmful” (PDF). MIT AI Lab. Arhivat din original (PDF) la . Accesat în .
- ^ Hyde 1996, § 6.6.2.2 SAR.
- ^ Steele 1977.
- ^ ISOIEC9899 1999, § 6.5.7 Bitwise shift operators (în română § 6.5.7 Operatori de deplasare pe biți).
- ^ FSF 2008, § 4.5 Integers implementation.
- ^ 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 | modificare sursă]- en Federal Standard 1037C, General Services Administration, (arhivat la 2022-01-22)
- en Knuth, Donald (). The Art of Computer Programming, Volume 2 — Seminumerical algorithms. Reading, Mass.: Addison-Wesley. pp. 169–170.
- en Steele, Guy L. (noiembrie 1977). „Arithmetic shifting considered harmful”. ACM SIGPLAN Notices Archive. New York: ACM Press. 12 (11): 61–69. doi:10.1145/956641.956647. hdl:1721.1/6090
. Arhivat din original la .
- en „3.7.1 Arithmetic Shift Operator”. VAX MACRO and Instruction Set Reference Manual. HP OpenVMS Systems Documentation. Hewlett-Packard Development Company. aprilie 2001. Arhivat din original la .
- en „Programming languages — C”. ISO/IEC 9899:1999. International Organization for Standardization. .
- en Hyde, Randall (). „CHAPTER SIX: THE 80x86 INSTRUCTION SET (Part 3)”. The Art of ASSEMBLY LANGUAGE PROGRAMMING. Arhivat din original la . Accesat în .
- en „C Implementation”. GCC manual. Free Software Foundation. .
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.