Aritmetica  dei  computer - Interi

L' aritmetica dei computer, almeno quella implementata direttamente dall' hardware, a causa della necessità pratica di avere una rappresentazione standard dei numeri mediante un numero finito e prefissato di bit, gode di caratteristiche e proprietà  diverse da quelle degli usuali insiemi numerici della matematica.

Sugli interi la principale differenza proviene dal fatto che,  con  n bit disponibili, è possibile rappresentare solo  2ⁿ  numeri  diversi. Questo comporta l' esistenza di un minimo ed un massimo tra gli interi rappresentabili. La scelta attualmente implementata in moltissimi linguaggi di programmazione è di sfruttare le possibilità dell'hardware per rappresentare gli interi dell' aritmetica modulo  2ⁿ. Le proprietà di questi interi coincidono con quelle dell'aritmetica di Peano purché ci si tenga lontano dai valori limte.

La rappresentazione e l' aritmetica degli interi, sono oggetto di  accordi internazionali per la definizione di standards. I sistemi attualmente più diffusi sono l' aritmetica modulo 2 ⁿ con complemento a due accanto ad un'  aritmetica intera superiormente e inferiormente limitata, entrambe previste dallo standard IEC 10967. Le informazioni seguenti non riguardano un singolo linguaggio di programmazione ma sono comuni a tutti i linguaggi che recepiscono lo standard per i numeri interi.

Rappresentazione degli interi

Ricordiamo che la notazione decimale posizionale, cui siamo abituati, è quella in cui il significato di uno dei dieci simboli  di  base  (le cifre  0,1,2,3,4,5,6,7,8,9)  dipende dalla posizione di questo all' interno della sequenza di cifre.
P. es. il numero  361 va interpretato come: 3 centinaia + 6 decine + 1 unità . Ovvero:

3 10² + 6 10¹ + 1 10⁰

Se invece di usare le dieci cifre usuali ne usiamo solo due (0,1 rappresentabili in un circuito mediante due diversi stati di tensione di una componente elettronica) avremo la possibilità di una rappresentazione posizionale  in base due in cui un numero è costituito unicamente da una sequenza di 0 e 1.
P.es.

11010  va interpretato come

1   2⁴ + 1   2³ + 0   2² + 1   2¹ + 0   2⁰

Ovvero, indicando con un sottoscritto  ₁₀  oppure  ₂  la rappresentazione in base 10 o 2 rispettivamente,

11010₂ = 26₁₀

Se l' aritmetica (le operazioni tra interi) viene implementata in modo che esista il successivo del massimo intero (e questo sia il minimo intero) e, viceversa, esista il precedente del minimo (e questo sia il massimo)  l' aritmetica del computer riproduce l' aritmetica modulo 2 ⁿ come definita in algebra (classi di resto).

Questa possibilità è quella "naturale" per un computer perché le operazioni aritmetiche sono svolte su dati rappresentati in registri (speciali circuiti) del processore sotto  forma di un numero fisso di bit.

Facciamo l' esempio di un intero (senza segno) rappresentato in registri a 8 bit. Potrebbe essere:

pari a 254. Se adesso sommiamo 3 (11₂)  a questo numero  dovremmo ottenere 

cioè  257. Però la cella più a sinistra non esiste nel registro del nostro processore. Quindi il bit corrispondente non viene rappresentato lasciando come risultato  l' intero contenuto nelle sole otto celle più a destra: 1 che corrisponde a     257 mod 2⁸. Questo schema di base va lievemente modificato per tener conto di interi col segno.

Se abbiamo a disposizione n bit e vogliamo rappresentare interi negativi e positivi (in numero uguale), la soluzione più semplice sarebbe  quella di usare uno dei bit per indicare il segno e gli altri per la rappresentazione in base 2 usuale. In questo caso potremmo rappresentare 2^n-1 interi positivi (da +0 a 2^n-1 - 1 ) e 2^n-1 interi negativi ( da -0 a -2^n-1 + 1 ). Da notare che in tal modo esisterebbero due diverse rappresentazioni dello zero e il range dei positivi sarebbe lo stesso dei negativi.

Tuttavia, questo metodo di rappresentazione non è il più agevole per implementare l' aritmetica modulo 2ⁿ. A questo scopo esistono due diverse rappresentazioni degli interi con segno utilizzate in modo standard nell' aritmetica dei computer contemporanei.

La rappresentazione con bias (distorsione, forse meglio traducibile in questo caso con traslazione)  e quella a complemento a due. L' utilizzo della prima (con lievi modifiche) è limitato alla codifica degli esponenti (interi) dei numeri con virgola (numeri floating point). La seconda è oggi la codifica generalmente usata per la rappresentazione degli interi con segno sfruttando le capacità dell' hardware.
In entrambe, gli interi tra -2^n-1 e 2^n-1-1 hanno un' unica rappresentazione mediante sequenze di n bit consecutive nell' aritmetica modulo 2ⁿ . Quello che cambia tra le due rappresentazioni è solo l' associazione tra sequenze di 0 e 1 ed interi nell' intervallo in questione. Nella rappresentazione con complemento a due lo zero è associato alla sequenza di n zeri, mentre in quella con bias B = 2^n-1-1 il valore binario (senza segno) del bias B nella rappresentazione posizionale diviene la rappresentazione dello zero mentre il numero le cui cifre sono tutte zero rappresenta il valore -B  (vedi tabella più avanti).

La rappresentazione complemento a due è basata sull' utilizzo dell' aritmetica delle conguruenze. In tale aritmetica infatti metà degli elementi sono gli inversi additivi dell' altra metà e pertanto possono essere presi a rappresentanti di un insieme (limitato) di numeri negativi. Per esempio, con 8 bit, 11111111 rappresenterebbe 2⁸-1=255. Essendo però 11111111+00000001 = 00000000 (mod 2⁸), 11111111 può essere considerato rappresentativo di -1. E così via per circa metà degli interi rappresentabili. Ne restarà uno ( 2⁷ ) che, essendo inverso additivo di se stesso nell' aritmetica modulare, dovrà essere assegnato convenzionalmente o al massimo valore positivo o al minimo negativo.

In pratica, per ottenere la rappresentazione complemento a due di un numero negativo, basta invertire tutti i bit della rappresentazione binaria del numero positivo (gli zeri diventano uno e gli uno diventano zero) e poi sommare uno al risultato. La spiegazione di questo algoritmo è semplice: con la notazione complemento a due vogliamo sfruttare le proprietà dell' aritmetica modulare (e poter fare la somma tra numeri positivi e negativi esattamente con lo stesso algoritmo (circuiti) che manipola la somma tra numeri positivi). Questo implica che se sommiamo ad un numero positivo il corrispondente negativo dobbiamo trovare zero. Facendo riferimento alla discussione sopra accennata, si vede che se si somma ad un numero positivo la sequenza di bit invertiti si ottiene un numero fatto solo dalle cifre 1. Aggiungendo un ulteriore 1 si ottiene zero ( entro i bit disponibili). Da cui l' algoritmo del complemento a due.

Un modo complementare di considerare la notazione per i negativi del complemento a due è di interpretare il bit più significativo come coefficiente della corrispondente potenza di due ma cambiata di segno: 10101110 = -2⁷ + 2⁵+2³+2²+2¹.

Come esempio, la tabella seguente mostra quale è l' associazione tra sequenze di 8 bit ed valori interi con segno nelle  rappresentazioni qui descritte (complemento a 2 e con bias = 127 ).