La rappresentazione posizionale in base 2

La rappresentazione dei numeri naturali in base $2$ è stata descritta da Lebniz all'inizio del '700. Leibniz gli attribuiva grande importanza filosofica, ma dal punto di vista matematico la cosa è rimasta poco più di una curiosità senza rilevanza pratica fino all'invenzione dei calcolatori elettronici, nei quali, invece, la rappresentazione in base $2$ è usata universalmente. La ragione sta nella sua massima semplicità di realizzazione mediante circuiti elettronici: poichè in base $2$ si usano solo due cifre, uno e zero, per realizzarla in un circuito elettrico sono necessari solo due stati diversi, ad esempio si può rappresentare lo zero con un valore negativo di corrente, l'uno con un valore positivo. In base $10$ occorrerebbero invece dieci stati diversi, ad esempio dieci livelli diversi di corrente, il che è decisamente poco pratico da realizzare e difficile da far funzionare.

Abbiamo visto che rappresentare un numero in base $10$ significa scriverlo come una somma di potenze di $10$, ciascuna moltiplicata per una cifra compresa tra $0$ e $9$. Ad esempio, abbiamo visto che il numero $1999$ viene rapresentato come

$$1\times10^{3}+9\times10^{2}+9\times10^{1}+9\times10^{0}.$$

In base $2$ le cose vanno in maniera analoga, con il$2$ al posto del $10$, e con due sole cifre,$0$ e $1$. Consideriamo ancora il numero $1999$. La sua rappresentazione in base $2$ è

$$11111001111$$

e questo significa che:

$$1999 = 1 \times 2^{10} + 1 \times 2^9 + 1 \times 2^8 + 1 \tim......2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$$

Qui potrebbero sorgere dei dubbi. Intanto, come si trova questa rappresentazione ? E poi, chi ci dice che tutti i numeri naturali si possono scrivere in questo modo⁴ ? In base $10$ questi problemi, di solito, non si pongono (a meno che uno sia matematico di professione), perchè abbiamo una tale familiarità con la rappresentazione in base $10$ da identificarla con i numeri stessi.

È possibile rispondere a entrambe le domande precedenti in una sola volta. Il modo consiste nel descrivere un procedimento generale (un algoritmo) che, dato un numero naturale $n$, ci restituisce sempre la sua rappresentazione in base $2$. L'algoritmo consiste semplicemente nel dividere il numero dato per $2$, ad esempio usando il metodo visto nel paragrafo precedente, ottendo un quoziente e un resto (che può essere solo $0$ oppure $1$), dividere ulteriormente il quoziente per $2$, e così via, fino a quando si trova quoziente $0$. I resti così trovati, elencati in ordine inverso, sono le cifre della rappresentazione in base $2$ del numero dato. Vediamo un esempio.
 
 
 
 
 
 
 

$$1999 = 999 \times 2 + 1$$
$$999 = 499 \times 2 + 1$$
$$499 = 2499 \times 2 + 1$$
$$249 = 124 \times 2 + 1$$
$$124 = 62 \times 2 + 0$$
$$62 = 31 \times 2 + 0$$
$$31 = 15 \times 2 + 1$$
$$15 = 7 \times 2 + 1$$
$$7 = 3 \times 2 + 1$$
$$3 = 1 \times 2 + 1$$ $$1 = 0 \times 2 + 1$$

 
 
 

I resti trovati, elencati a partire dall'ultimo, sono $1,1,1,1,1,0,0,1,1,1,1$. Perciò, la rappresentazione in base $2$ del numero $1999$ è:

$$1111100111$$

Come si vede già in questo esempio, il numero di cifre occorrenti per un dato numero è molto maggiore in base due che in base dieci. Già il numero $2$ richiede due cifre in base $2$, essendo rappresentato da $10$, mentre ne richiede una sola in base dieci. Questo fatto rende la base due poco pratica da utilizzare per i calcoli manuali, mentre non costituisce un problema per un calcolatore, che è in grado di manipolare stringhe di cifre anche molto lunghe.

Il problema inverso, ossia passare dalla rappresentazione in base $2$ a quella in base $10$, si risolve in maniera molto semplice moltiplicando ogni cifra binaria per la potenza di $2$ corrispondente alla sua posizione, e sommando i numeri così trovati. Ad esempio,

$$1011001010$$

corrisponde al numero

$$1 \times 2^{9} + 0 \times 2^{8} + 1 \times 2^{7} + 1 \times 2......\times 2^{3} + 0 \times 2^{2} + 1 \times 2^{1} + 0 \times 2^{0}$$

ossia:

$$512+128+64+8+2 = 714$$

Veniamo ora alle operazioni aritmetiche in base due. Gli algoritmi sono essenzialmente gli stessi noti per la base $10$, con la differenza che ora, avendo come uniche cifre $0$ e $1$, si ha riporto quando si supera $1$. Vediamo un esempio di somma:
 
 
 
 

$$\begin{array}{llllllr}&1&0&0&1&1&+\\&1&1&0&0&1&=\\ [1ex]\hline \\ [-1.6ex]1&0&1&1&0&0& \\\end{array}$$

 

e uno di moltiplicazione:
 
 
 

$$\begin{array}{lllllr}& &1&0&1&\times\\& &1&1&0&=\\ [1ex......&1&0&1\\1&0&1\\\hline \\ [-1.6ex]1&1&1&1&0&\end{array}$$

 

Come si può notare nell'esempio sopra, la tabellina del $2$ non richiede di essere memorizzata (è evidente che $0 \times 0 = 0, 0 \times 1 = 0, 1 \times 0 = 0$ e $1 \times 1 = 1$), mentre la tabellina del $10$ richiede di imparare a memoria $8 \times 8 = 64$ risultati.

La divisione utilizza ancora, in base $2$, lo stesso algoritmo visto per la base $10$, ma anche in questo caso con una semplificazione: non c'è più alcun bisogno di "indovinare" i quozienti parziali, dato che ogni quoziente parziale (che ha sempre una sola cifra) può essere solo $0$ oppure $1$, ed è uguale a $1$ quando il dividendo parziale è maggiore del divisore, uguale a $0$ altrimenti. Vediamo un esempio:
 
 
 
 

$$\begin{array}{lllllcrrrr}1&1&0&1& &:& &1&0&1\\1&0&1& & & ......1\\& &0&0\\ [1ex]\cline{2-4}\\ [-1.6ex]& &1&1\end{array}$$

 

Il primo gruppo di cifre selezionate, ossia il primo dividendo parziale, è $110$, che è maggiore del divisore $101$, dunque la prima cifra del quoziente è $1$. Al passo successivo, il dividendo parziale è $11$, minore di $101$, dunque la cifra successiva del quoziente è $0$. Perciò, mentre in base dieci l'algoritmo per la divisione utilizza la moltiplicazione, questo non accade in base due.

Abbiamo detto all'inizio del paragrafo che l'aritmetica in base $2$ è stata descritta da Leibniz all'inizio del XVIII secolo. Tuttavia, un uso implicito della base $2$ è stato fatto fin da tempi molto antichi, come si scopre analizzando, per esempio, un metodo per la moltiplicazione utilizzato in Egitto a partire almeno dal $2000$ A.C. (descritto nel papiro di Rhind). Il sistema di numerazione egiziano era in base $10$, ma non era posizionale, il che non lo rendeva direttamente utilizzabile per le operazioni aritmetiche. Per la moltiplicazione veniva invece utilizzato l'algoritmo descritto nell'esempio seguente.

Esempio Supponiamo di voler moltiplicare $83$ per $37$. Scriviamo su due colonne parallele i numeri $1$ e $37$, e sotto ciascuno di essi i numeri che si ottengono per successive moltiplicazioni per $2$, fino a quando nella colonna di sinistra non si eccede il numero $83$:
 
 
 
 

$$\begin{array}{lllr}-->& &1&37\\-->& &2&74\\& &4&128\\ ......296\\-->& &16&592\\& &32&1184\\-->& &64&2368\end{array}$$

 

a questo punto si cercano, nella colonna di sinistra, dei numeri che, sommati, danno $83$; si trovano (indicati con la freccia) $64$, $16$, $2$, $1$. I numeri corrispondenti nella colonna di destra, ossia $2368$, $592$, $74$, $37$, sommati, danno il prodotto richiesto.

Cosa c'entra l'aritmetica binaria ? C'entra, perchè i numeri che compaiono nella colonna di sinistra sono proprio le successive potenze di $2$, fino alla massima potenza di $2$ minore o uguale a $83$, che è appunto $64$. La ragione per cui si trovano sempre, in questa colonna, dei numeri che sommati danno $83$ è che $83$ (così come ogni altro numero) si rappresenta, in base $2$, proprio come somma di potenze di $2$ (quelle che hanno coefficiente $1$, le altre non compaiono), e ciò che si fa nella colonna di sinistra non è altro che un metodo (diverso da quello visto all'inizio del paragrafo) per trovare la rappresentazione in base $2$ del numero $83$. Si trova così che $83 = 64 + 16 +2 + 1$ , ossia $1 \times 2^6 + 1 \times 2^4 + 1 \times 2^1 + 1$ (e quindi$83$ si scrive in base $2$ come 1010011).

I numeri nella seconda colonna sono i prodotti di $37$ per le potenze di $2$ che si trovano in corrispondenza nella prima colonna, e sommando quelli selezionati con la freccia, si trova il prodotto $83 \times 37$, come si vede applicando la proprietà distributiva:

$$83 \times 37 = (1 \times 2^6 + 1\times 2^4 + 1 \times 2^1 + ......37 = 2^6 \times 37 + 2^4 \times 37 + 2^1\times 37 +1 \times 37$$

$= 2368 + 592 + 74 + 37.$

Si può notare che questo metodo per la moltiplicazione richiede solo di saper addizionare (per moltiplicare un numero per $2$ basta addizionarlo con se stesso), in altre parole, non richiede la conoscenza dei prodotti di tutti i numeri di una sola cifra (le tabelline).