In questo articolo vediamo come rappresentare un numero in una base numerica a scelta; daremo uno sguardo a cosa ci offre la libreria standard del linguaggio C e affronteremo un semplice esercizio.
PREMESSA
Partiamo da alcuni chiarimenti.
E' vero che i valori interi sono rappresentati internamente in base 2, ovvero in binario, ma è ragionevole, e più comodo per noi umani, pensare che siano valori in base 10. In realtà si dovrebbe pensare che sono semplicemente dei valori, senza una specifica base numerica: convertire un valore intero da o verso una base è solo una questione di rappresentazione, ovvero la formattazione di un output o l'interpretazione di un input.
Ci possiamo trovare davanti a due situazioni:
a) abbiamo un intero e lo dobbiamo visualizzare in output in una base di numerazione specificata
b) riceviamo in input una stringa contenente un valore espresso in una specifica base e lo dobbiamo caricare in un intero.
Nel primo caso possiamo sfruttare la sprintf(), vedi http://www.cplusplus.com/reference/cstdio/sprintf/ , con opportuni specificatori di formato, per "stampare" l'intero in basi diverse da 10; questo però può andare bene solo per quelle basi per le quali è stato previsto uno specificatore, ovvero base 8 (specificatore %o) e base 16 (specificatori %x o %X).
In realtà alcuni compilatori forniscono la funzione itoa() http://www.cplusplus.com/reference/cstdlib/itoa/ che lavora con basi diverse ma si tratta di una funzione che non è presente nello standard ANSI-C.
Nel secondo caso possiamo utilizzare la funzione strtol(), vedi http://www.cplusplus.com/reference/cstdlib/strtol/ , che ci permette di specificare qualsiasi base.
PROBLEMA
Affrontiamo ora un esercizio che ho trovato all'interno di un forum di programmazione.
Tabella di equivalenza tra decimali, binari, ottali ed esadecimali.
Scrivete un programma che stampi una tabella dei valori equivalenti ottali, esadecimali e binari dei numeri decimali nell'intervallo da 0 a 255.
SOLUZIONE
L'esercizio ci richiede di stampare una tabella con i numeri da 0 a 255 rappresentati in diverse basi numeriche.
Se si dovessero stampare solo i valori in base 10, base 8 e base 16 la questione si risolverebbe con poche righe di codice:
#include <stdio.h>
void main()
{
int i;
for (i = 0; i < 255; i++)
printf("%d %o %X\n", i, i, i);
}
Purtroppo, però, dobbiamo anche stampare il valore in base 2, per la quale non vi è uno specificato di formato.
Dobbiamo quindi rimboccarci le maniche e predisporre una funzione che converta un valore da base 10 a base 2, o più in generale in una base specificata.
L'algoritmo è molto semplice.
Dato un valore in input lo si divide progressivamente per la base desiderata, tenendoci traccia del resto della divisione, finchè il valore è maggiore di 0: i resti, letti in senso inverso, forniscono la rappresentazione nella base richiesta.
Ad esempio, per esprimere 11 in base 2:
11 / 2 = 5 RESTO 1
5 / 2 = 2 RESTO 1
2 / 2 = 1 RESTO 0
1 / 2 = 0 RESTO 1
quindi in base 2 leggiamo, dal basso verso l'alto, 1011.
Un'implementazione molto semplice è presente qui sotto; sostanzialmente i vari resti vengono salvati nella stringa che poi viene invertita prima dell'uscita dalla funzione.
int IntToStr(int valin, int base, char *strout, int dimstr)
{
int i;
int len;
char c;
short idx;
char *digit = "0123456789ABCDEF";
/* verifica dei parametri, stringa lunga almeno 2 caratteri e base compresa fra 2 e 16 */
if (dimstr < 2)
return 0;
if ((base < 2) || (base > 16))
{
strcpy(strout, "");
return 0;
}
/* esegue la conversione delle cifre */
i = 0;
do
{
idx = valin % base;
strout[i] = digit[idx];
valin = valin / base;
i++;
if (i == (dimstr - 1)) /* verifichiamo di non sforare */
break;
} while (valin > 0);
if (valin > 0) /* se siamo usciti senza poter esprimere tutti i bit */
{
strcpy(strout, "");
return 0;
}
len = i;
strout[len] = '\0';
/* inversione della stringa */
for (i = 0; i < len / 2; i++)
{
c = strout[i];
strout[i] = strout[len-i-1];
strout[len-i-1] = c;
}
return 1;
}
Alcune note:
- la funzione è generica ed è pensata per basi tra 2 e 16
- le possibili cifre, definite nella stringa digit, sono 16; qualora si voglia attivare la conversione a basi maggiori di 16 bisogna naturalmente modificare tale stringa aggiungendo le cifre maggiori di 15
- l'argomento dimstr permette di specificare la dimensione massima della stringa, per evitare sforamenti; in realtà si poteva considerare una dimensione minima della stringa, corrispondente al numero di bit per un intero (se ho interi a 32 bit la stringa più lunga che posso rappresentare sarà di 32 cifre in binario).
Il nuovo main può quindi essere scritto così:
void main()
{
int i;
char binstr[40];
for (i = 0; i < 255; i++)
{
IntToStr(i, 2, binstr, 40);
printf("%d %o %X %s\n", i, i, i, binstr);
}
}
Qui vedete l'esecuzione del programma in Linux:
La funzione IntToStr() fa il suo mestiere ma l'inversione della stringa finale è proprio necessaria?
Non si può fare senza?
Certo che si può! Bisogna però scrivere una funzione ricorsiva, seguendo questo schema (à la Python):
converti(valin, base)
se valin < base
stampo valin /* è una cifra */
altrimenti
converti(valin/base,base)
stampo valin%base
in questo modo ottengo l'ordinamento delle cifre voluto (se ci pensate, non facciamo altro che sfruttare lo stack per quello che è, una pila!).
Qui sotto il codice completo:
int IntToStrRec2(int valin, int base, char *strout, int dimstr, int *currlen);
int IntToStr(int valin, int base, char *strout, int dimstr)
{
int currlen = 0;
int ret;
if (dimstr < 2)
return 0;
if ((base < 2) || (base > 16))
{
strcpy(strout, "");
return 0;
}
ret = IntToStrRec(valin, base, strout, dimstr, &currlen);
if (ret == 0)
strout[0] = '\0';
return ret;
}
int IntToStrRec(int valin, int base, char *strout, int dimstr,int *currlen)
{
int ret;
char *digit = "0123456789ABCDEF";
if (valin < base)
{
strout[0] = digit[valin];
strout[1] = '\0';
*currlen = 1;
}
else
{
ret = IntToStrRec(valin / base, base, strout, dimstr, currlen);
if (ret == 0)
return ret;
if (*currlen >= (dimstr - 1))
return 0;
strout[*currlen] = digit[valin%base];
strout[(*currlen)+1] = '\0';
(*currlen)++;
}
return 1;
}
Come si può notare ho preferito creare due funzioni: la IntToStr() con gli stessi argomenti della versione non ricorsiva e la IntToStrRec() che è la vera e propria funzione ricorsiva.
Ho fatto questo per mantenere lo stesso prototipo della versione non ricorsiva: in questo modo non dobbiamo modificare il ciclo che avevamo scritto nel main().
Evitiamo così che l'utilizzatore della nostra funzione ci debba passare il puntatore ad un intero (currlen) inizializzato a 0; inoltre, abbiamo anche il vantaggio di poter eseguire una serie di controlli (validità della base e dimensione minima della stringa) una volta sola, prima di iniziare la ricorsione.
CONCLUSIONI
Abbiamo visto quello che offre la libreria standard del linguaggio C in quanto a conversioni di base e abbiamo predisposto una funzione per sopperire ad alcune sue mancanze, per la soluzione di un semplice esercizio.
C'è da dire, comunque, che la rappresentazione in base 2 è piuttosto inusuale: anche nel caso si vogliano verificare delle cifre binarie è sempre molto più comodo passare tramite la rappresentazione esadecimale.
Chi ad esempio lavora su progetti embeeded per "stampare" lo stato di una porta di I/O utilizzerà sempre base 16 per poi convertire "mentalmente" in binario.
Come si fa? Semplice: basta considerare che ad ogni cifra esadecimale corrispondono 4 bit, secondo questa tabella:
0x0 0000
0x1 0001
0x2 0010
0x3 0011
0x4 0100
0x5 0101
0x6 0110
0x7 0111
0x8 1000
0x9 1001
0xA 1010
0xB 1011
0xC 1100
0xD 1101
0xE 1110
0xF 1111
Quindi 0xA5 si converte velocemente in 1010 0101.
Come memorizzare tali valori? Io uso queste regole:
- 0x0 e 0xF sono facili, tutti i bit a 0 o tutti i bit a 1
- le potenze di 2 (1,2,4 e 8) hanno un solo 1 che "shifta" verso sinistra
- 0xA e 0x5 hanno i valori 1 e 0 alternati
e poi, a forza di convertire, rimarranno in mente come tabelline!
Buon lavoro e buon divertimento!!!
