Numeri binari e complemento a due

Tutti i dati di un processore sono numeri binari: non solo le quantità numeriche, ma anche le istruzioni, i caratteri di un testo, i pixel di una figura. I circuiti che elaborano numeri binari sono semplicissimi ed economici. Questa nota raccoglie ciò che serve prima di parlare di virgola fissa (Virgola fissa - formati n.m e normalizzazioneIn virgola fissa il processore fa aritmetica sugli interi (con segno) e il fattore di scalacostante per cui si moltiplica un valore reale per ottenere l'intero memorizzato $2^{m}$ resta sottinteso: il formato n.m dice che dei bit disponibili $n$ sono la parte intera (compreso il segno se il numero è con segno, S; nessun segno se U) e $m$ la parte frazionaria. Il valore è $\text{codice}/2^m$. Passare dal formato n.m al decimale, o viceversa, è il calcolo più frequente dell'esame: su 16 bit $\text{valore}=\text{codice}/2^m$, l'intervallo è $[0,2^n)$ (U) oppure $[-2^{n-1},2^{n-1})$ (S), la risoluzione è $2^{-m}$.Virgola fissa - formati n.m e normalizzazione →).

Notazione posizionale e conversioni

Un numero $N$ in base $b$ si scrive $N=\sum_{i=-m}^{n-1}a_i\,b^i$, con cifrei simboli ammessi in una base: 0 e 1 in binario, da 0 a F in esadecimale $a_i$ ($0\le a_i<b$); si scrive $a_{n-1}\dots a_1a_0.a_{-1}\dots a_{-m}$. In binario $b=2$ e le cifre (bitbinary digit: una cifra binaria, 0 oppure 1) sono 0 e 1. Si usa molto anche la base 16 (esadecimalesistema in base 16: ogni cifra vale 4 bit), con cifre $0$-$9$ e $A$-$F$ ($A=10,\dots,F=15$): 4 bit corrispondono a una cifra esadecimale, quindi la conversione binario-esadecimale è immediata. Per rappresentare un numero decimale di $k$ cifre servono circa $3{,}3\,k$ bit (perché $\log_210\approx3{,}3$).

• Da decimale a binario (intero): si divide per 2 annotando i resti, e si leggono i resti dal basso. $57=28\cdot2+1$, $28=14\cdot2+0$, $14=7\cdot2+0$, $7=3\cdot2+1$, $3=1\cdot2+1$, $1=0\cdot2+1$: $57_{10}=111001_2$.
• Da binario a decimale: si raddoppia il risultato parziale e si somma il bit corrente (schema di Hornercalcolo di un polinomio con una moltiplicazione e una somma per ogni coefficiente): $11101_2$: $1\to2\cdot1+1=3\to2\cdot3+1=7\to2\cdot7+0=14\to2\cdot14+1=29$. Quindi $11101_2=29$.
• Frazione da decimale a binario: si raddoppia la parte frazionaria e si annota la parte intera: $0{,}6875\cdot2=1{,}375\to1$; $0{,}375\cdot2=0{,}75\to0$; $0{,}75\cdot2=1{,}5\to1$; $0{,}5\cdot2=1\to1$: $0{,}6875=0{,}1011_2$. Il numero di cifre dopo la virgola dipende dalla base: $0{,}1_{10}$ in binario ha infinite cifre.
• In esadecimale: $259{,}76_{10}$: $259=16\cdot16+3$, $16=1\cdot16+0$, $1=0\cdot16+1$, quindi $259=103_{16}$; per la frazione $0{,}76\cdot16=12{,}16\to C$, $0{,}16\cdot16=2{,}56\to2$, $0{,}56\cdot16=8{,}96\to8$: $259{,}76=103{,}C28\ldots_{16}$.

Le tabelline binarie sono banali: $0+0=0$, $0+1=1$, $1+1=0$ con riportobit che si trasferisce alla colonna successiva quando una somma supera la cifra massima 1; prodotto = AND. Addizione e sottrazione si fanno come a mano, colonna per colonna ($1101101+0100101=10010010$, cioè $109+37=146$).

Lunghezza di parola e accuratezza

Un processore usa un numero fissato $n$ di bit (4, 8, 16, 32 per i µC, fino a 256 per alcuni DSP). La lunghezza di parola non ha alcuna relazione con l'accuratezza dei calcoli: un processore a 4 bit può calcolare con la stessa accuratezza di uno a 128 bit, solo molto più lentamente (eseguendo i calcoli a pezzi) e con costo diverso. L'accuratezza dipende da come si rappresentano i numeri (Virgola fissa - formati n.m e normalizzazioneIn virgola fissa il processore fa aritmetica sugli interi (con segno) e il fattore di scalacostante per cui si moltiplica un valore reale per ottenere l'intero memorizzato $2^{m}$ resta sottinteso: il formato n.m dice che dei bit disponibili $n$ sono la parte intera (compreso il segno se il numero è con segno, S; nessun segno se U) e $m$ la parte frazionaria. Il valore è $\text{codice}/2^m$. Passare dal formato n.m al decimale, o viceversa, è il calcolo più frequente dell'esame: su 16 bit $\text{valore}=\text{codice}/2^m$, l'intervallo è $[0,2^n)$ (U) oppure $[-2^{n-1},2^{n-1})$ (S), la risoluzione è $2^{-m}$.Virgola fissa - formati n.m e normalizzazione →) e da quanti bit si usano nei risultati intermedi.

Rappresentazione dei numeri negativi

Con $n$ bit si rappresentano i naturali $0\dots2^n-1$. Per i negativi servono codifiche:

• modulo e segnocodifica con un bit di segno e il valore assoluto sugli altri bit: un bit di segnoil bit più significativo: vale 1 per i negativi e $n-1$ bit di modulo; $-(2^{n-1}-1)\le N\le2^{n-1}-1$, due rappresentazioni dello zero. Si usa solo per la mantissa dei numeri a virgola mobile (Virgola mobile - formato IEEE 754 e formato a 16 bitIn virgola mobile un numero è $(-1)^S,(1+F),2^{E-B}$: segno $S$, mantissa frazionaria $F$ (con l'$1$ iniziale implicito) ed esponente $E$ con offset $B$. La precisione relativa è costante ($\varepsilon=2^{-n_F}$) e cambia la spaziatura tra i valori; in $n$ bit si rappresentano gli stessi $2^n$ numeri della virgola fissa, ma distribuiti diversamente. Nello standard IEEE 754 a 32 bit: 1 bit di segno, 8 di esponente ($B=127$), 23 di mantissa. All'esame compare un formato a 16 bit (1+4+11, $B=7$): codifica, decodifica e somma con allineamento degli esponenti. Il campo esponente tutto a 0 con mantissa nulla è lo zero.Virgola mobile - formato IEEE 754 e formato a 16 bit →).
• complemento a 1codifica in cui il negativo si ottiene invertendo tutti i bit del positivo: i negativi si ottengono invertendo bit a bit i positivi; due zeri. Quasi abbandonato.
• complemento a 2codifica dei numeri con segno: il negativo di N su n bit è 2 elevato a n meno N: la codifica usata in tutti i processori.

Complemento a due

Il complemento a 2 di $N$ su $n$ bit è per definizione $$C_2(N)=2^n-N .$$ Proprietà: rappresenta tutti gli $N$ con $-2^{n-1}\le N\le2^{n-1}-1$; ha un solo zero ($00\dots0$); il bit più significativo è il bit di segno; unifica somma e sottrazione in un solo circuito, perché $A-B=A+C_2(B)$.

Calcolo pratico: si invertono tutti i bit (operatore $\mathrm{NEG}$) e si somma 1: $$C_2(N)=\mathrm{NEG}(N)+1 .$$ Esempio su 5 bit: $C_2(14)=32-14=18=10010_2$; oppure $\mathrm{NEG}(01110)+1=10001+1=10010$.

Dimostrazione. Si ha $C_2(N)=2^n-N=(2^n-1)-N+1$. Ma $2^n-1$ è la stringa $11\dots1$ ($n$ uni) e, bit per bit, $1-N_i=\overline{N_i}$ (sottrarre da 1 un bit lo nega). Quindi $(2^n-1)-N=\mathrm{NEG}(N)$ e $C_2(N)=\mathrm{NEG}(N)+1$. $\square$

Conseguenze. $N+C_2(N)=N+\mathrm{NEG}(N)+1=(2^n-1)+1=2^n\equiv0$ (modulo $2^n$): cioè $N-N=0$. Inoltre $C_2(C_2(N))=2^n-(2^n-N)=N$, cioè $-(-N)=N$.

Interpretazione del valore. Una stringa $a_{n-1}\dots a_0$ in complemento a 2 vale $$N=-a_{n-1}2^{n-1}+a_{n-2}2^{n-2}+\dots+a_02^0,$$ cioè è un normale numero binario con il peso del bit più significativo cambiato di segno. La stessa stringa può quindi avere più significati: $10100011_2$ è $163$ se interpretata come naturale, $-93$ in complemento a 2 su 8 bit; e, come frazione con segno, $-93/2^7=-0{,}7266$ (fattore di scala $2^7$) oppure $-93/2^6=-1{,}4531$ (fattore $2^6$). Senza conoscere la normalizzazione è impossibile decodificare un numero (nota Virgola fissa - formati n.m e normalizzazioneIn virgola fissa il processore fa aritmetica sugli interi (con segno) e il fattore di scalacostante per cui si moltiplica un valore reale per ottenere l'intero memorizzato $2^{m}$ resta sottinteso: il formato n.m dice che dei bit disponibili $n$ sono la parte intera (compreso il segno se il numero è con segno, S; nessun segno se U) e $m$ la parte frazionaria. Il valore è $\text{codice}/2^m$. Passare dal formato n.m al decimale, o viceversa, è il calcolo più frequente dell'esame: su 16 bit $\text{valore}=\text{codice}/2^m$, l'intervallo è $[0,2^n)$ (U) oppure $[-2^{n-1},2^{n-1})$ (S), la risoluzione è $2^{-m}$.Virgola fissa - formati n.m e normalizzazione →).

Il "diagramma circolare" aiuta: su 4 bit i codici $0000,0001,\dots,0111$ valgono $0\dots7$ e i codici $1000,\dots,1111$ valgono $-8\dots-1$; sommare 1 a $0111$ dà $1000$, cioè da $+7$ si passa a $-8$.

Overflow

Quando il risultato di una operazione esce dall'intervallo rappresentabile c'è overflow aritmeticocondizione in cui il risultato di un'operazione non è rappresentabile con i bit disponibili. Sommando due numeri positivi si può ottenere un negativo e viceversa. Su 5 bit ($-16\le N\le15$):

• $01000+01000=10000$: $8+8$ dà $-16$ (errato);
• $11000+10111=1\,01111$ (si scarta il riporto): $-8-9$ dà $+15$ (errato). Con segni opposti l'overflow non può mai verificarsi (il risultato è sempre compreso tra i due operandi).

Per la circolarità del complemento a 2, gli overflow intermedi si compensano: se il risultato finale è rappresentabile, è corretto anche se un passaggio intermedio è andato in overflow. Esempio su 8 bit ($-128\le N\le127$): $(55+121)-82$. Il primo passo dà $176\to-80$ (overflow: $55+121$ esce dall'intervallo), il secondo $-80-82=-162\to94$ (altro overflow, due negativi che diventano positivo): due volte il flag di overflow attivo, ma il risultato $94$ è corretto, come $176-82=94$. Cambiando l'ordine, $(121-82)+55$: $121-82=39$ e $39+55=94$, nessun overflow. Il risultato finale è lo stesso, ma nel secondo caso il flag non si accende mai.

Un overflow non compensato rende i risultati totalmente inattendibili: tutti i processori lo rilevano con un bit del registro di statoregistro della CPU i cui bit (flag) segnalano overflow, zero, riporto e altre condizioni. Nei calcoli numerici va evitato o gestito (aritmetica saturatamodalità in cui un risultato fuori intervallo viene sostituito dal massimo o dal minimo rappresentabile, riscalatura: Architettura del repertorio di istruzioni - RISC, CISC, VLIW e indirizzamentoL'architettura è l'insieme delle risorse visibili al programmatore (istruzioni, modi di indirizzamento). RISC: poche istruzioni semplici, di uguale lunghezza, decodifica cablata, quasi tutte a 1 ciclo; CISC: molte istruzioni complesse, decodifica microprogrammata, più cicli. I DSP sono RISC "potenziati" (MAC, saturazione, barrel shifter, arrotondamento, VLIW, SIMD); i modi di indirizzamento tipici sono immediato, a registro, diretto, indiretto, con auto-incremento, circolare e a bit rovesciati (per la FFT).Architettura del repertorio di istruzioni - RISC, CISC, VLIW e indirizzamento →). La condizione logica di rilevamento è nella nota ALU - sommatore, overflow, carry look-ahead e shiftL'ALU è un insieme di celle a 1 bit (full adder + selettori) collegate in parallelo: somma, sottrae ($A-B=A+\overline B+1$: si inverte $B$ e si porta il riporto iniziale a 1), fa AND/OR. Il ritardo è dominato dal riporto: nel ripple-carry cresce linearmente con i bit; col carry look-aheadtecnica che calcola in anticipo i riporti da generazione e propagazione, riducendo il ritardo i riporti si calcolano da generazione $g_i=A_iB_i$ e propagazione $p_i=A_i+B_i$ in pochi livelli di logica. L'overflow è $V=C_{in,n-1}\oplus C_{out,n-1}$. Gli shift logici inseriscono 0, gli aritmetici estendono il segno; il barrel shiftercircuito che sposta una parola di un numero qualsiasi di posizioni in un solo ciclo sposta di $m$ posti in un ciclo.ALU - sommatore, overflow, carry look-ahead e shift →.

Errori comuni

• Dimenticare di sommare 1 dopo l'inversione dei bit.
• Pensare che in complemento a 2 l'intervallo sia simmetrico: $-2^{n-1}$ non ha un opposto rappresentabile (su 8 bit $-128$ esiste, $+128$ no).
• Interpretare una stringa senza sapere se è un naturale, un intero con segno o una frazione.
• Credere che un overflow intermedio rovini sempre il risultato.