Dimensionamento delle enumerazioni
In generale, quando si ha il problema di rappresentare x oggetti tramite stringhe binarie, si deve prevedere un numero n di bit tale che:
2n = x
con n ∈ N.
Infatti, tramite n bit è possibile rappresentare 2n differenti combinazioni di valori binari, cui si possono far corrispondere i più svariati significati. Alcune di queste combinazioni possono anche non venire assegnate: è il caso tipico di quando i diversi valori da rappresentare non sono potenze di 2.
Si veda al riguardo il seguente esercizio.
ESERCIZIO
Testo
Si dimensionino correttamente le stringhe di bit atte a contenere le seguenti informazioni:
- i semi delle carte da gioco napoletane;
- i nomi delle note della scala musicale;
- i mesi dell'anno;
- i codici prodotto di un distributore automatico con 100 scomparti.
Soluzione
- Nel caso dei semi, x = 4 e dunque n = 2, in quanto 4 <= 22. Ad esempio: 00 = bastoni, 01 = denari, 10 = spade e 11 = coppe.
- Nel caso delle note, x = 7 e dunque n = 3, in quanto 7 < 23. Una delle 8 combinazioni risulterà inutilizzata.
- Nel caso dei mesi dell'anno, x = 12 e dunque n = 4, in quanto 12 <= 24. Quattro delle sedici combinazioni risulteranno inutilizzate.
- Infine, per identificare x = 100 prodotti servono almeno n = 7 bit, in quanto 100 <= 27.
Cenni matematici
Matematicamente, noto x, il calcolo di n si esprime come segue:
n = ⌈ log2(x) ⌉ = ⌈ log(x)/log(2) ⌉,
\[ n = \lceil \log_2 x \rceil = \left \lceil \frac{\log x}{\log 2} \right \rceil \]
dove la funzione "⌈x⌉" è l'intero superiore del numero x, la funzione log2(x) è il logaritmo in base 2, mentre la funzione log(x) è il logaritmo in una base qualunque.
In mancanza di tale operatore, è comunque possibile ottenere il valore desiderato grazie al seguente ragionamento: qual è la potenza del 2 che è maggiore o uguale al numero di oggetti da codificare? Se tale potenza è 2n, allora il valore è (numero di bit necessari) proprio n. Il numero di configurazioni inutilizzate sarà pari a 2n-x.