Basi di numerazione e conversioni - binario, ottale ed esadecimale

Un calcolatore lavora in binario, ma i numeri si scrivono più comodamente in ottale o in esadecimale. Questa nota spiega come passare da una base all'altra e come fare le quattro operazioni elementari in binario. Le versioni "da corso di architettura" sono in Sistemi di numerazione posizionaliNotazione posizionale in base b; conversioni tra base 10, 2, 8 e 16 per interi (divisioni successive) e per parti frazionarie (moltiplicazioni successive); numeri periodici in binario.Sistemi di numerazione posizionali → e Aritmetica binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.Aritmetica binaria →; qui l'accento è sul metodo, con ogni passaggio scritto.

Notazione posizionale

In base $r$ si usano le $r$ cifre $0,1,\dots,r-1$. Il valore di una cifra dipende dalla posizione: è il coefficiente di una potenza di $r$. Un numero con cifre $a_na_{n-1}\dots a_1a_0.a_{-1}a_{-2}\dots a_{m}$ vale $$N=\sum_{i=m}^{n}a_i\,r^i .$$ La cifra $a_n$ è la più significativa (MSB, most significant bit in binario), la $a_m$ la meno significativa (LSB). La virgola separa la parte intera (esponenti $\ge0$) da quella frazionaria (esponenti negativi).

Decimale ($r=10$): $2719{,}53_{10}=2\cdot10^3+7\cdot10^2+1\cdot10^1+9\cdot10^0+5\cdot10^{-1}+3\cdot10^{-2}$.

Binario ($r=2$, cifre 0 e 1). Esempi:

• $10011_2=1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=16+2+1=19_{10}$;
• $110101{,}11_2=32+16+4+1+\frac12+\frac14=53{,}75_{10}$.

Per leggere un binario si sommano le potenze di 2 delle posizioni in cui c'è un 1. Conviene sapere a memoria:

$2^{10}=1024\approx10^3$ (kilo), $2^{20}\approx10^6$ (mega), $2^{30}\approx10^9$ (giga), $2^{40}\approx10^{12}$ (tera).

Nota sulle capacità. Il costruttore di un disco usa i prefissi decimali ($1\,\mathrm{GB}=10^9$ byte), molti sistemi operativi i prefissi binari ($1\,\mathrm{GB}=2^{30}=1\,073\,741\,824$ byte). Un disco da $500\,\mathrm{GB}$ decimali vale $500/1{,}073741824\approx465{,}7$ GB binari.

Ottale ed esadecimale

Poiché $8=2^3$ e $16=2^4$, una cifra ottale corrisponde esattamente a 3 bit e una esadecimale a 4 bit: sono scritture compatte del binario, lunghe un terzo o un quarto.

• Ottale (base 8): cifre $0$–$7$; esempio $127{,}4_8=1\cdot64+2\cdot8+7+4\cdot8^{-1}=87{,}5_{10}$.
• Esadecimale (base 16): cifre $0$–$9$ e $A,B,C,D,E,F$ per $10,\dots,15$; esempio $B65F_{16}=11\cdot16^3+6\cdot16^2+5\cdot16+15=45056+1536+80+15=46687_{10}$.

Binario $\to$ esadecimale. Si formano gruppi di 4 bit partendo dalla virgola (verso sinistra per la parte intera, verso destra per la frazionaria), completando con zeri i gruppi estremi, e si sostituisce ogni gruppo con la sua cifra. Esempio: $0010\,1100\,0110\,1011{,}1111\,0000\,0110_2=2C6B{,}F06_{16}$.

Esadecimale $\to$ binario. Si sostituisce ogni cifra con i suoi 4 bit: $3A6{,}C_{16}=0011\,1010\,0110{,}1100_2=1110100110{,}11_2$ (si eliminano gli zeri inutili agli estremi). Per l'ottale si fa lo stesso con gruppi di 3 bit.

Da decimale a binario (e ad altre basi)

Parte intera, primo metodo: sottrarre potenze di 2

Si cerca la più grande potenza di 2 che non supera il numero, la si sottrae, e si ripete sul resto fino a ottenere 0. Le posizioni usate sono gli 1.

Esempio: $625$. $625-512=113$ ($2^9$); $113-64=49$ ($2^6$); $49-32=17$ ($2^5$); $17-16=1$ ($2^4$); $1-1=0$ ($2^0$). Quindi $625=2^9+2^6+2^5+2^4+2^0$ e il binario ha un 1 nelle posizioni $9,6,5,4,0$: $625_{10}=1001110001_2$.

Parte intera, secondo metodo: divisioni per $r$

Si divide il numero per la base, si annota il resto, si divide il quoziente, e così via fino al quoziente $0$. Il primo resto è la cifra meno significativa: i resti si leggono dal basso verso l'alto. Perché funziona: ogni divisione per $r$ stacca la cifra $a_0$ (il resto) e sposta tutte le altre di una posizione, come cancellare l'ultima cifra in decimale.

Esempio: $625$ in binario. $625\to312$ r $1$; $312\to156$ r $0$; $156\to78$ r $0$; $78\to39$ r $0$; $39\to19$ r $1$; $19\to9$ r $1$; $9\to4$ r $1$; $4\to2$ r $0$; $2\to1$ r $0$; $1\to0$ r $1$. Letti dal basso: $1001110001$ ✓ (stesso risultato).

Esempio: $2471$ in ottale. $2471\to308$ r $7$; $308\to38$ r $4$; $38\to4$ r $6$; $4\to0$ r $4$. Dal basso: $2471_{10}=4647_8$. Verifica: $4\cdot512+6\cdot64+4\cdot8+7=2048+384+32+7=2471$ ✓.

Parte frazionaria: moltiplicazioni per $r$

Si moltiplica la parte frazionaria per 2; la parte intera del prodotto (0 o 1) è la prossima cifra dopo la virgola, a partire dalla più significativa; si ripete sulla nuova parte frazionaria finché si ottiene $0$ o si hanno abbastanza cifre.

Esempio: $41{,}125$. La parte intera: $41=32+8+1\to101001$. Frazione: $0{,}125\cdot2=0{,}25$ (cifra $0$); $0{,}25\cdot2=0{,}5$ (cifra $0$); $0{,}5\cdot2=1{,}0$ (cifra $1$), residuo $0$, stop. Quindi $41{,}125_{10}=101001{,}001_2$.

Esempio: $0{,}4$. $0{,}4\cdot2=0{,}8$ (0); $0{,}8\cdot2=1{,}6$ (1); $0{,}6\cdot2=1{,}2$ (1); $0{,}2\cdot2=0{,}4$ (0): si è tornati a $0{,}4$, quindi la sequenza si ripete. $0{,}4_{10}=0{,}\overline{0110}_2$ è periodico: non si può scrivere esattamente con un numero finito di bit, solo approssimare. È la ragione per cui un calcolatore non rappresenta esattamente $0{,}1$ o $0{,}4$.

Aritmetica binaria elementare

Le operazioni seguono le stesse regole decimali; cambia il valore della base.

Somma

Tabella: $0+0=0$, $0+1=1$, $1+0=1$, $1+1=0$ con riporto 1. Il riporto va sommato alla colonna successiva, dove si possono sommare tre 1 ($1+1+1=1$ con riporto $1$).

Esempio: $01100_2+10001_2$ ($12+17$). Colonne da destra: $0+1=1$; $0+0=0$; $1+0=1$; $1+0=1$; $0+1=1$. Risultato $11101_2=29$ ✓.

Esempio con riporti: $10110_2+10111_2$ ($22+23$). Da destra: $0+1=1$; $1+1=0$ r1; $1+1+1=1$ r1; $0+0+1=1$; $1+1=0$ r1; riporto finale $1$. Risultato $101101_2=45$ ✓.

Differenza

Tabella: $0-0=0$, $1-0=1$, $1-1=0$, $0-1=1$ con prestito: si prende un 1 dalla cifra a sinistra del minuendo, che aggiunge $2$ alla cifra su cui si lavora (in decimale aggiungerebbe 10).

Esempio: $10110_2-10010_2=00100_2$ ($22-18=4$): le colonne a destra danno $0,1,0$ e le altre $0,0$ senza prestiti.

Esempio con prestito: $10110_2-10011_2$ ($22-19=3$). Si procede per colonne da destra, portandosi dietro il prestito $p$ (che vale 1 se la colonna precedente ha chiesto un 1 in prestito):

Risultato (dal bit 4 al bit 0) $00011_2=3$ ✓. Come controllo si può sempre ripetere l'operazione in decimale e riconvertire.

Se il minuendo è minore del sottraendo si scambiano gli operandi e si mette il segno meno davanti: $10011_2-11110_2=-(11110_2-10011_2)=-01011_2=-11_{10}$. Il calcolatore non fa così: usa il complemento a 2 (Numeri con segno, complemento a 2, sottrazione e overflowSottrazione senza segno: se $M\ge N$ nessun prestito in uscita, altrimenti il risultato $M-N+2^n$ è scorretto. Complemento a 1: $2^n-1-N$ (inversione bit a bit); complemento a 2: $2^n-N=$ complemento a 1 $+1$. Numeri con segno: segno e modulo (due zeri, intervallo simmetrico) oppure complemento a 2 (un solo zero, da $-2^{n-1}$ a $2^{n-1}-1$, MSB di peso $-2^{n-1}$). In complemento a 2 somma e sottrazione sono la stessa addizione: $A-B=A+\overline B+1$, riporto in uscita scartato. Overflow: senza segno $\Leftrightarrow C_{out}=1$ nella somma; con segno $\Leftrightarrow C_{in,MSB}\ne C_{out,MSB}$ (due operandi dello stesso segno con risultato di segno opposto).Numeri con segno, complemento a 2, sottrazione e overflow →).

Prodotto

Le cifre da moltiplicare sono solo 0 e 1, quindi ogni prodotto parziale è uguale al moltiplicando (se la cifra del moltiplicatore è 1) o a zero (se è 0). I prodotti parziali si traslano a sinistra di una posizione ciascuno e si sommano. In hardware il prodotto di due bit è una porta AND.

Esempio: $1011_2\times101_2$ ($11\times5$): prodotti parziali $1011$ (bit 0), $0000$ (bit 1, traslato di 1), $1011$ (bit 2, traslato di 2): $$\begin{array}{r}1011\\0000\phantom{0}\\1011\phantom{00}\\\hline110111\end{array}\qquad\text{cioè }110111_2=55_{10}\ ✓$$

Altre basi

In generale, per operare in base $r$ si può passare per il decimale: si convertono gli operandi, si calcola, si riconverte il risultato.

Esempi svolti (esercizi del corso)

Errori comuni

• Leggere i resti delle divisioni dall'alto: vanno letti dal basso.
• Leggere le cifre frazionarie dal basso: vanno lette dall'alto.
• Raggruppare i bit da sinistra anziché dalla virgola (nei numeri con parte frazionaria o con numero di bit non multiplo di 3/4).
• Dimenticare di completare con zeri i gruppi estremi ($1110100110{,}11\to0011\,1010\,0110{,}1100$).
• Scambiare "1 GB decimale" e "1 GB binario".