7  Contare in base 2

Anche se in linea di principio questo non è l’unico approccio possibile, in pratica tutti i calcolatori moderni funzionano in logica binaria—cioè manipolano e conservano i dati al loro interno sotto forma di bit, o celle elementari di memoria che possono assumere uno due valori possibili (convenzionalmente \(0\) o \(1\)). Questo deriva essenzialmente dal fatto che i dispositivi di memorizzazione più diffusi si basano, a livello elementare, sul flip-flop, che è un circuito elettronico a due stati. La prima cosa che ci serve per andare un po’ più a fondo nella comprensione di come funziona un computer, allora, è imparare a contare in base \(2\).

7.1 La notazione posizionale

Quando scriviamo il numero \(127\) (nella consueta notazione posizionale in base \(10\)) quello che in effetti intendiamo è: \[ (127)_{10} = 1 \times 10^2 + 2 \times 10^1 + 7 \times 10^0. \] (Notate che in questo caso particolare abbiamo indicato esplicitamente la base per evitare ambiguità, ma ove essa dovesse essere omessa assumeremo sempre che il numero sia scritto in base \(10\)).

Più in generale possiamo contare in una base arbitraria \(b\), con il comune intendimento che \[ (c_m\ldots c_2c_1c_0)_b = c_m \times b^m + \cdots + c_2 \times b^2 + c_1 \times b + c_0 \quad\text{con}\quad c_0 \ldots c_m < b. \tag{7.1}\] Tipicamente \(b\) è un numero intero più grande di \(1\), ma in generale questa restrizione non è necessaria—e i sistemi di numerazione in base negativa, o addirittura immaginaria o complessa, possono avere proprietà interessanti. Per \(b = 2\), \(8\), \(16\) e \(60\) si hanno i sistemi di numerazione binario, ottale, esadecimale e sessagesimale, che sono largamente usati in alcuni contesti.

È facile convincersi che con \(m\) cifre (in base \(b\)) si possono esprimere \(b^m\) numeri interi diversi—ad esempio tutti quelli compresi tra \(0\) e \(b^m - 1\). Così con \(3\) cifre decimali si possono esprimere i \(1000\) numeri tra \(0\) e \(999\), mentre con \(8\) cifre binarie si possono esprimere solamente i \(2^8 = 256\) numeri tra \(0\) e \(255\).

Importante

Non fate mai confusione tra un numero e la sua rappresentazione. Senza addentrarci troppo nella semantica della cosa, i numeri sono un concetto astratto che indica una quantità, ed esistono prima della loro rappresentazione—le scritture \[ (11)_{10} = (14)_7 = (102)_{3} = \text{XI} \] corrispondono tutte allo stesso numero—quello che comunemente scriviamo semplicemente come \(11\). Rappresentare un numero con una particolare notazione, posizionale o no, è questione di convenienza e dipende dal contesto.

7.2 Il sistema di numerazione binario

Il sistema di numerazione binario è quello in cui si usa come base \(b = 2\) e, come abbiamo detto in avvio di sezione, il sistema binario riveste un ruolo peculiare perché è il linguaggio parlato dai calcolatori. Possiamo scrivere, ad esempio, \[ (1101)_2 \triangleq 0b1101 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 1 = 13. \] (Ricordate le nostre convenzioni: quando scriviamo \(13\) senza indicare la base intendiamo \((13)_{10}\). Abbiamo anche introdotto il prefisso \(0b\), che troverete usato in letteratura per indicare un numero nella sua rappresentazione in base 2.)

Convertire un numero intero dal sistema decimale a quello binario (e viceversa) è banale, seguendo l’Equazione 7.1. Qualsiasi linguaggio di programmazione degno di questo nome, inoltre, fornisce funzioni di conversione nei due sensi, e.g.,

# Binary representation of a decimal number...
print(bin(11))
print(bin(999))
# ...expressing a number in binary representation
print(0b1)
print(0b11111111)

0b1011
0b1111100111
1
255

Nota

Ricordatevi cosa abbiamo detto a proposito della differenza tra numeri e loro rappresentazione, e non lasciatevi confondere dalle apparenze. bin() è una funzione built-in di Python che restituisce la rappresentazione binaria di un numero intero nella forma di una stringa preceduta da 0b; 0b11111111, d’altra parte, non è nient’altro che un modo diverso, ma perfettamente equivalente, di scrivere il numero intero \(255\). L’interprete Python non fa nessuna differenza tra 0b11111111 e 255.

print(0b11111111 == 255)
print(bin(255) == 0b11111111)
print(bin(255) == "0b11111111")

True
False
True

Non andate avanti fino a che non avete capito la sottile differenza tra le tre espressioni 🙂

Per vostra comodità, i due elementi grafici che seguono permettono di passare in modo interattivo dalla rappresentazione binaria a quella decimale e viceversa. Prendetevi qualche minuto per convincervi di dominare il processo di conversione.

Non vi servirà molto tempo (e probabilmente la cosa non è sorprendente) per rendervi conto che servono molte più cifre per rappresentare un numero in base 2 rispetto a quelle che servono in base 10. Per il numero \(497\), e.g., sono sufficienti tre cifre decimali, mentre ne servono ben nove in base \(2\).

Se ci pensate un attimo il numero \(n_2\) (\(n_{10}\)) di cifre che servono per rappresentare un generico in numero \(m\) in base \(2\) (\(10\)) è approssimativamente \[ n_2 \approx \log_2(m) \quad\text{e}\quad n_{10} \approx \log_{10}(m) \] per cui asintoticamente abbiamo \[ \frac{n_2}{n_{10}} \approx \frac{\log_2(m)}{\log_{10}(m)} = \frac{1}{\log_{10} (2)} \approx 3.32 \] (Nel passaggio intermedio abbiamo sfruttato la formula per il cambiamento di base nei logaritmi.) In altre parole: per rappresentare un numero servono mediamente più di tra cifre binarie per ogni cifra decimale. Non che sia una limitazione fondamentale, ma non è difficile immaginare che scrivere numeri relativamente grandi in base \(2\) possa diventare una scocciatura molto velocemente. E, se avete la pazienza di passare alla sezione successiva, è qui che ci viene in aiuto la base \(16\).

7.2.1 Moltiplicazione e divisione in base \(2\)

Se ci pensate un attimo, nella normale rappresentazione dei numeri in base \(10\) è banale moltiplicare o dividere per \(10\)—basta aggiungere o togliere uno zero a destra (o, eventualmente, spostare il separatore decimale, i.e., la virgola se usciamo dal campo degli interi). Possiamo generalizzare banalmente dicendo che in base \(b\) è banale moltiplicare (o dividere) per \(b\), o una qualsiasi potenza di \(b\), aggiungendo (o togliendo) l’opportuno numero di zeri a sinistra.

Ora, in base \(10\) questo significa che è facile dividere e moltiplicare per \(10\), \(100\), \(1000\) e così via. Si tratta di una cosa utile che impariamo da piccole quando studiamo le equivalenze. Ma allora in base \(2\) è facile moltiplicare e dividere per un sacco di numeri: \(2\), \(4\), \(8\), \(16\) e così via. Wow! Potremmo quasi dire che una delle caratteristiche della rappresentazione in base \(2\) degli interi è la semplicità con cui essa permette di moltiplicare.

Questo è tanto vero che Python (come molti linguaggi di programmazione, del resto) offre due operatori binari dedicati per eseguire bit shift nelle due direzioni \[ \texttt{n << m} \quad\text{e}\quad \texttt{n >> m} \] che corrispondono, rispettivamente, alla moltiplicazione per \(2^m\) ed alla divisione (intera) per \(2^m\). Così

n = 7
print(n << 1) # Multiply by 2
print(n << 2) # Multiply by 4
print(n << 3) # Multiply by 8

14
28
56

7.3 Il sistema di numerazione esadecimale

Se scegliamo come base \(b = 16\) lavoriamo per definizione in quello che si chiama sistema esadecimale. Inutile dirlo, tutto quello che abbiamo detto per il sistema binario, mutatis mutandis, vale per quello esadecimale, e.g., \[ (24)_{16} \triangleq 0x24 = 2 \times 16 + 4 = 36. \] (Notiamo per inciso, il prefisso \(0x\), che svolge esattamente la stessa funzione che \(0b\) svolge per il sistema binario. Tenetelo a mente, perché si tratta di una convenzione molto utilizzata in letteratura e nella documentazione tecnica.)

L’unico dettaglio da mettere a fuoco è che adesso ci servono \(16\) cifre, e non più \(10\) (i.e., \(0\)–\(9\)) come nel sistema decimale. La convenzione standard è di aggiungere \(a\), \(b\), \(c\), \(d\), \(e\) ed \(f\) (maiuscole o minuscole, non fa differenza) dopo il \(9\), per indicare i numeri \(11 \ldots 15\). Con questo abbiamo una prescrizione completa, e analogamente a prima

# Hexadecimal representation of a decimal nmber...
print(hex(11))
print(hex(999))
# ...expressing a number in hexadecimal representation
print(0x15)
print(0x124)

0xb
0x3e7
21
292

E, esattamente come prima, ecco dei semplici widget per esercitarvi nella conversione. Ancora una volta, assicuratevi di aver capito prima di andare avanti.

A questo punto probabilmente vi state chiedendo: ok, ma perché tutta questa enfasi sul sistema esadecimale? Non abbiamo detto che i computer contano i binario?

Beh, per prima cosa, come si vede dagli esempi, il sistema esadecimale richiede mediamente un numero di cifre leggermente più basso di quello decimale. Ormai abbiamo capito come stimare il rapporto \[ \frac{n_{16}}{n_{10}} \approx \frac{1}{\log_{10} (16)} \approx 0.83 \] In altre parole: la rappresentazione esadecimale ci fa risparmiare quasi il 20% di cifre rispetto a quella decimale. Non male—la compattezza è sempre utile.

Un effetto collaterale curioso legato a questa proprietà, e dovuto in parte al fatto che il sistema esadecimale condivide con quello decimale dieci delle due sedici cifre, è che nella rappresentazione esadecimale i numeri tendono ad apparire più piccoli che in quella decimale. Il numero \(50\), ad esempio, si scrive nel sistema esadecimale come \(0x32\)—la cosa adesso vi lascia largamente indifferenti, ma quando arriverete a 50 anni di età vi assicuro che comincerete a rivalutare la questione, e 32 anni esadecimali suoneranno meglio di 50 anni normali 🙂

Scherzi a parte, la chiave di questa discussione è che \(16\) è una potenza di \(2\)—per la precisione \(16 = 2^4\). Se ci pensate un attimo, questo significa che passare da sistema binario ad esadecimale (o viceversa) è particolarmente semplice: si raggruppano le cifre binarie \(4\) a \(4\) iniziando da quella più a destra (eventualmente aggiungendo uno o più zeri a sinistra dell’ultimo gruppo fino ad arrivare a \(4\)), e si converte da binario ad esadecimale ciascun gruppo \[ 99 = 0b\overbrace{0110}^6\overbrace{0011}^3 = 0x63. \] In altre parole: il sistema esadecimale è una sorta di versione compatta del sistema binario, che permette di sfruttare tutti i vantaggi di quest’ultimo, e di evitare allo stesso tempo stringhe interminabili di zeri e uni. Non dovrebbe sorprendere, allora, che il sistema esadecimale sia quello più utilizzato nella programmazione vicina all’hardware, e.g., per indirizzare registri di dispositivi elettronici.

La Tabella 7.1 contiene la rappresentazione di primi \(16\) interi positivi nelle tre basi che ci interessano (\(10\), \(2\) e \(16\)) e dovrebbe essere tutto quello che vi serve per convertire da base \(2\) a base \(16\) e viceversa.

Tabella 7.1: rappresentazione dei primi \(16\) interi positivi in base \(10\), \(2\) e \(16\).

Decimale	Binario	Esadecimale
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
10	1010	a
11	1011	b
12	1100	c
13	1101	d
14	1110	e
15	1111	f

7.4 Tutto qua?

Si e no. Adesso sappiamo rappresentare e manipolare numeri interi in basi diverse da \(10\), ed abbiamo una certa dimestichezza con le basi \(2\) e \(16\). Questo ci basta per andare avanti e descrivere un pochino più in dettaglio il funzionamento interno di un calcolatore, ma abbiamo lasciato fuori una cosa importante: non abbiamo detto cosa succede quando passiamo dai numeri interi ai numeri in virgola mobile. Ci torneremo nel capitolo dedicato, appunto, all’aritmetica in virgola mobile—che, anticipiamo, sarà denso di sorprese. Ma se siete curiose e non volete perdere il filo della questione potete saltare direttamente a Capitolo 11.