Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
ott, giorno?
in corso

Rappresentazione dell'informazione

Argomento di Programmazione 1. Fatto a lezione a ottobre, due deck che si leggono insieme. Deck 4.3: slide 2-11 (informazione, dato, codifica), slide 12-24 (interi positivi, modulo e segno, complemento a 2), slide 25-32 (virgola fissa e mobile), slide 33-36 (caratteri e ASCII). Deck 4.4: slide 3-12 (basi 10, 2, 8, 16), slide 13-47 (conversioni con l’algoritmo dei resti e con i pesi), slide 48-52 (esadecimale e ottale passando dal binario), slide 53-58 (somma, prodotto, shift), slide 59-67 (quiz di conversione). Il programma decimale-binario era già in Array; come il C usa queste codifiche nei tipi (int, unsigned, float) è in Tipi di dati e conversioni.

Il filo dei due deck:

informazione     il significato (154, +26, 9.625, una temperatura)
   |  codifica  ↓        ↑  decodifica
dato             i bit in memoria (10011010): senza contesto non vogliono dire niente
   |
tipi semplici    booleani, interi positivi, interi relativi, frazionari, caratteri
                 la codifica la fissa l'hardware
   |
interi >= 0      binario posizionale; con 8 bit da 0 a 255
interi relativi  modulo e segno (doppio zero), poi complemento a 2 (quello vero)
frazionari       virgola fissa, virgola mobile (IEEE-754)
caratteri        tabella ASCII
   |
basi 2, 8, 16    conversioni: resti per andare, pesi per tornare,
                 gruppi di 3 o 4 bit fra 2, 8 e 16
   |
aritmetica       somma con riporto, prodotto per spostamenti, shift

1Definizioni

Informazione, dato, rappresentazione (slide 2-3, 8-11). Le informazioni si memorizzano e si manipolano nel calcolatore sotto forma di dati, organizzati secondo opportune rappresentazioni (o codifiche). Andare dall’informazione al dato è la codifica; tornare dal dato all’informazione, usando la stessa rappresentazione, è la decodifica.

Il punto del prof: un dato da solo è “privo di senso”. La sequenza di 16 bit 0001000011001100 (in esadecimale 10CC) non vuol dire niente finché non si sa che rappresenta, per esempio, un numero frazionario con segno che indica la temperatura media su Marte. Lo stesso per un file ldc.mp3 di 3.841.481 byte: sono milioni di valori come 3f-aa-cd-02..., e diventano musica solo per un programma che conosce la codifica MP3. Esempio più vicino al C: il byte 01100001 è il numero 97 se lo leggi come intero, la lettera 'a' se lo leggi come carattere.

Tipi semplici e complessi (slide 9-10). I tipi che il calcolatore manipola direttamente (tipi di dato elementari) sono pochi: valori di verità, interi positivi o negativi, numeri frazionari, caratteri. La loro rappresentazione è fissata dall’hardware, e il programmatore può affidarsi al calcolatore per interpretarli. Le informazioni più complesse (un numero complesso, un testo, una rubrica, un albero genealogico, un disegno, un filmato, un suono) usano codifiche di livello software, costruite sopra i tipi semplici.

Sistema posizionale (slide 7-12). In un sistema posizionale in base bb:

In formula, il numero cn−1…c1c0c_{n-1} \ldots c_1 c_0 in base bb vale

cn−1⋅bn−1+…+c1⋅b1+c0⋅b0c_{n-1} \cdot b^{n-1} + \ldots + c_1 \cdot b^1 + c_0 \cdot b^0
basenomecifrepesi (da destra)
10decimale0-91, 10, 100, 1000
2binario0, 11, 2, 4, 8, 16, 32, 64, 128
8ottale0-71, 8, 64, 512
16esadecimale0-9, A=10, B=11, C=12, D=13, E=14, F=151, 16, 256, 4096

Gli esempi delle slide, con i passaggi:

194310=1⋅103+9⋅102+4⋅101+3⋅100=1000+900+40+31943_{10} = 1 \cdot 10^3 + 9 \cdot 10^2 + 4 \cdot 10^1 + 3 \cdot 10^0 = 1000 + 900 + 40 + 3 100110102=1⋅27+0⋅26+0⋅25+1⋅24+1⋅23+0⋅22+1⋅21+0⋅20=128+16+8+2=1541010011010_2 = 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 = 128 + 16 + 8 + 2 = 154_{10} 13728=1⋅512+3⋅64+7⋅8+2⋅1=512+192+56+2=762101372_8 = 1 \cdot 512 + 3 \cdot 64 + 7 \cdot 8 + 2 \cdot 1 = 512 + 192 + 56 + 2 = 762_{10} 3A1F16=3⋅4096+10⋅256+1⋅16+15⋅1=12288+2560+16+15=14879103A1F_{16} = 3 \cdot 4096 + 10 \cdot 256 + 1 \cdot 16 + 15 \cdot 1 = 12288 + 2560 + 16 + 15 = 14879_{10}

Un controesempio che esce all’esame: “301 può essere un numero in base 3?” No: in base 3 le cifre sono solo 0, 1 e 2, e la cifra 3 non esiste. Per lo stesso motivo 19 non è un numero ottale e G non è una cifra esadecimale.

Contare nelle diverse basi (slide 3-6). Si conta allo stesso modo in ogni base: si incrementa la cifra delle unità, e quando supera b−1b - 1 torna a 0 con un riporto sulla posizione dopo.

decesaottbindecesaottbin
000011B131011
111112C141100
2221013D151101
3331114E161110
44410015F171111
55510116102010000
66611017112110001
77711118122210010
8810100019132310011
9911100120142410100
10A121010

Conviene saper scrivere a memoria la colonna dei primi 16 valori in binario a 4 bit: è la tabella che serve per le conversioni esadecimale-binario.

Interi positivi (slide 12). Si rappresentano in binario con sequenze di bit, di solito multiple di 8: sequenze di byte. Con NN bit ci sono 2N2^N combinazioni, quindi si rappresentano i naturali da 00 a 2N−12^N - 1:

bitcombinazioniintervallo senza segno
8 (1 byte)28=2562^8 = 256da 0 (00000000) a 255 (11111111)
16216=655362^{16} = 65536da 0 a 65535
322322^{32}da 0 a 4.294.967.295

La frase sottolineata dal prof: gli interi come oggetti matematici non hanno un valore massimo, gli interi del calcolatore hanno sempre un valore massimo finito. Superarlo è l’overflow.

Modulo e segno (slide 16). Il modo più semplice per gli interi relativi: il bit più a sinistra è il bit di segno (0 positivo, 1 negativo), gli altri sono il modulo in binario. Con 8 bit: 00011010 è +26+26, 10011010 è −26-26. Due difetti: lo zero ha due codifiche (00000000 è +0+0, 10000000 è −0-0), e la somma richiede un circuito che guardi i segni, perché sommare i bit “così come sono” dà risultati sbagliati.

Con NN bit il modulo ha N−1N - 1 bit, quindi si rappresentano i valori da −(2N−1−1)-(2^{N-1} - 1) a +(2N−1−1)+(2^{N-1} - 1): con 8 bit da −127-127 a +127+127, cioè 255 valori con 256 codici, perché lo zero ne spreca uno. Il secondo difetto con un esempio su 4 bit: +2+2 è 0010, −2-2 è 1010; sommati in colonna danno 1100, che in modulo e segno è −4-4 invece di 0.

Complemento a 2 (CA2) (slide 17-21). Nei calcolatori il segno non si rappresenta esplicitamente: si usano le rappresentazioni in complemento (a uno e a due), meno intuitive ma con due vantaggi:

  1. lo zero ha una sola codifica;
  2. non serve un circuito apposta per il segno: le addizioni in complemento a due servono anche per le sottrazioni.

Le regole della slide 20-21:

La slide 20 dice “se il MSB è 1, si decodifica e poi si sottrae 2N−12^{N-1}”. Va letta bene, perché le versioni corrette sono due e mescolarle dà un errore:

Decodificare tutti gli NN bit e sottrarre 2N−12^{N-1} darebbe 15−8=715 - 8 = 7, sbagliato. La seconda versione si ricorda così: l’MSB pesa −2N−1-2^{N-1} invece di +2N−1+2^{N-1}, gli altri bit pesano come al solito. 1111 vale −8+4+2+1=−1-8 + 4 + 2 + 1 = -1.

L’intuizione, con 4 bit: i 16 codici si dispongono in cerchio, e aggiungere 1 è un passo in senso orario. Da 0000 andando avanti si contano i positivi fino a 0111 (+7+7); da 0000 andando indietro si contano i negativi: 1111 è −1-1, 1110 è −2-2, fino a 1000 (−8-8). Il CA2 è proprio questo: un numero negativo −x-x è il codice che si trova xx passi prima di zero, cioè il naturale 2N−x2^N - x.

decCA2 4 bitdecCA2 4 bit
70111-11111
60110-21110
50101-31101
40100-41100
30011-51011
20010-61010
10001-71001
00000-81000

La figura spiega anche i due vantaggi: lo zero è un punto solo del cerchio, e sommare è sempre “girare in avanti”, qualunque sia il segno. L’overflow è attraversare la linea fra +7+7 e −8-8: 7+17 + 1 in CA2 a 4 bit dà 1000, cioè −8-8. L’intervallo è asimmetrico (−8-8 c’è, +8+8 no) perché lo zero occupa uno dei codici con MSB 0.

Virgola fissa (slide 25-26). Per i numeri con una parte frazionaria (12,64) le tecniche sono due. In virgola fissa i bit si dividono, una volta per tutte, in quelli della parte intera e quelli della parte frazionaria: la virgola sta in una posizione fissa. Dopo la virgola i pesi continuano con gli esponenti negativi: 2−1=0.52^{-1} = 0.5, 2−2=0.252^{-2} = 0.25, 2−3=0.1252^{-3} = 0.125, 2−4=0.06252^{-4} = 0.0625. Con 4 bit per parte:

1001.10102=8+1+0.5+0.125=9.625100011.01002=2+1+0.25=3.25101001.1010_2 = 8 + 1 + 0.5 + 0.125 = 9.625_{10} \qquad 0011.0100_2 = 2 + 1 + 0.25 = 3.25_{10}

Virgola mobile (slide 27-32). Gran parte dei bit rappresenta le cifre significative del numero (la mantissa), indipendentemente da dove sta la virgola, e alcuni bit dicono dove va la virgola (l’esponente). È la notazione scientifica in base 2. Lo standard è IEEE-754; il prof lo presenta prima in una versione semplificata a 32 bit:

| s | eeeeeeee | mmmmmmmmmmmmmmmmmmmmmmm |
  1     8                23
segno   esponente e in CA2   mantissa m senza segno, letta come 0.mmm...
X = ± m · 2^e     con m < 1

La mantissa contiene tutte le cifre significative, l’esponente decide dove mettere la virgola: moltiplicare per 2e2^e sposta la virgola di ee posti a destra (a sinistra se e<0e < 0).

Lo standard vero (slide 32) differisce in tre punti: la mantissa sta in [1,2)[1, 2) (l’1 prima della virgola è sottinteso e i 23 bit sono solo la parte frazionaria); l’esponente non è in CA2 ma con bias, cioè si memorizza e+127e + 127; ci sono due zeri, +0+0 e −0-0. La slide dice “per NN bit il bias è 2N−12^{N-1}”: il valore dello standard è 2N−1−12^{N-1} - 1, cioè 127 per 8 bit. Gli intervalli rappresentabili sono circa (−2128,−2−126](-2^{128}, -2^{-126}] e [2−126,2128)[2^{-126}, 2^{128}).

Caratteri e tabella ASCII (slide 33-34). I caratteri si codificano con una tabella che associa un codice convenzionale a ogni carattere della tastiera: la tabella ASCII (American Standard Code for Information Interchange). Contiene cifre, lettere maiuscole e minuscole (con codici diversi), punteggiatura, simboli. Lo standard copre i primi 128 valori di un byte (da 00000000 a 01111111); i successivi, fino a 256, formano la ASCII estesa, con versioni nazionali (lettere accentate). I primi 32 valori non sono caratteri stampabili ma caratteri di controllo, come l’a capo. Esistono altri standard, come UNICODE, nato per evitare tabelle regionali incompatibili (la slide dice 2 byte per carattere: è la codifica UTF-16 di base; UTF-8 ne usa da 1 a 4).

I codici da ricordare:

caratterecodiceperché serve
'0' … '9'48 … 57consecutivi: c - '0' dà la cifra
'A' … 'Z'65 … 90consecutivi
'a' … 'z'97 … 122consecutivi, 32 dopo le maiuscole
spazio32
'\n'10carattere di controllo
'\0'0terminatore delle stringhe

2Concetti

2.1Perché ottale ed esadecimale

Il calcolatore lavora in binario, ma i numeri binari sono lunghi e illeggibili: 0001000011001100 è difficile da copiare senza errori. Siccome 8=238 = 2^3 e 16=2416 = 2^4, ogni cifra ottale corrisponde esattamente a 3 bit e ogni cifra esadecimale a 4 bit. L’esadecimale è quindi una scrittura compatta del binario: 0001 0000 1100 1100 diventa 10CC, quattro cifre invece di sedici. Per questo gli indirizzi di memoria si stampano in esadecimale (%p in Puntatori).

2.2Perché l’algoritmo dei resti funziona

(slide 21, dimostrazione a mano del prof su 1010=1010210_{10} = 1010_2) Si scrive il numero già scomposto in potenze di 2:

10=1⋅23+0⋅22+1⋅21+0⋅2010 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0

Tutti i termini tranne l’ultimo contengono almeno un fattore 2. Dividendo per 2:

Ripetendo su 5 si ottiene c1=1c_1 = 1 con quoziente 2, poi c2=0c_2 = 0 con quoziente 1, poi c3=1c_3 = 1 con quoziente 0. All’ultima divisione il resto è il bit più significativo. I resti escono quindi dal meno significativo al più significativo, e vanno letti dall’ultimo al primo. Lo stesso ragionamento vale per qualsiasi base bb, dividendo per bb.

2.3Quanti bit servono

Con NN bit si hanno 2N2^N configurazioni. Per rappresentare KK valori diversi serve il più piccolo NN con 2N≥K2^N \geq K. Per 300 valori: 28=256<3002^8 = 256 < 300, 29=512≥3002^9 = 512 \geq 300, quindi 9 bit. Per 654 valori: 29=512<6542^9 = 512 < 654, 210=1024≥6542^{10} = 1024 \geq 654, quindi 10 bit.

Per i naturali da 0 a MM i valori sono M+1M + 1: per arrivare a 255 bastano 8 bit (256 valori), per 256 ne servono 9.

2.4Una sequenza di bit, tre letture

Gli stessi 8 bit cambiano valore a seconda della codifica con cui li leggi. Due esempi agli estremi, che conviene sapere a memoria:

bitnaturalemodulo e segnoCA2
11111111128+64+…+1=255128 + 64 + \ldots + 1 = 255segno −, modulo 1111111 =127= 127: −127-127255−256=−1255 - 256 = -1
10000000128128segno −, modulo 0: −0-0128−256=−128128 - 256 = -128
01111111127127+127+127+127+127 (MSB 0: come il naturale)

L’ultima riga è la regola che fa risparmiare tempo: con MSB 0 le tre letture coincidono. Solo con MSB 1 bisogna fare conti diversi. La prima riga spiega perché 11111111 è “tutti 1” in tre sensi: il massimo senza segno, il negativo più grande in modulo e segno, e −1-1 in CA2 (sulla ruota, il codice subito prima di zero).

2.5Somma direttamente in base 8 e in base 16

Il deck somma solo in binario (slide 53-55), ma la regola della somma in colonna vale in ogni base, ed è più veloce di due conversioni quando i due addendi sono già nella stessa base. In base bb, per ogni colonna da destra:

  1. somma le due cifre e il riporto entrante (in decimale, è comodo);
  2. se la somma è minore di bb, scrivila e il riporto è 0;
  3. se è maggiore o uguale a bb, scrivi somma meno bb e porta 1.

È la stessa cosa che fai in base 10 con 7+5=127 + 5 = 12: scrivi 2 e porti 1, perché 12 supera 10. In base 8 il “giro” avviene a 8, in base 16 a 16.

Esempio 1, 478+35847_8 + 35_8:

posizione210
riporto entrante110
47847_8047
35835_8035
somma104

Risultato 1048104_8. Controllo in decimale: 478=3947_8 = 39, 358=2935_8 = 29, 39+29=6839 + 29 = 68, e 1048=64+0+4=68104_8 = 64 + 0 + 4 = 68.

Esempio 2, 9C16+7B169C_{16} + 7B_{16} (le lettere si convertono prima: C = 12, B = 11):

posizione210
riporto entrante110
9C169C_{16}09C
7B167B_{16}07B
somma117

Risultato 11716117_{16}. Controllo: 9C16=1569C_{16} = 156, 7B16=1237B_{16} = 123, 156+123=279156 + 123 = 279, e 11716=256+16+7=279117_{16} = 256 + 16 + 7 = 279 (verificati in Python).

Con basi diverse non si può sommare in colonna: una cifra in posizione 1 vale 8 da una parte e 16 dall’altra. Prima si porta tutto nella stessa base (vedi Metodo).

2.6Sottrazione e overflow in CA2: due esempi su 4 bit

Su 4 bit i numeri sono pochi e si controllano sulla ruota. La regola: a−ba - b si fa come a+(−b)a + (-b), e il riporto oltre l’ultimo bit si scarta.

Esempio 1, 5−35 - 3. +5+5 = 0101; +3+3 = 0011, invertito 1100, più 1 1101 =−3= -3 (controllo: −8+4+1=−3-8 + 4 + 1 = -3).

posizione3210
riporto entrante1010
+5+50101
−3-31101
somma0010

Dalla colonna 3 esce un riporto 1, che si scarta. Restano i 4 bit 0010 =+2= +2, ed è giusto. Il riporto in uscita qui c’è ma non è un errore: addendi di segno diverso non vanno mai in overflow.

Esempio 2, (−6)+(−5)(-6) + (-5). −6-6 = 1010 (slide 22), −5-5: 0101 invertito 1010, più 1 1011.

posizione3210
riporto entrante0100
−6-61010
−5-51011
somma0101

Scartato il riporto, 0101 =+5= +5. Due negativi hanno dato un positivo: overflow. Il valore vero, −11-11, è fuori da [−8,7][-8, 7]. Sulla ruota: partendo da −6-6 e facendo 5 passi indietro si scavalca −8-8 e si ricomincia da +7+7.

2.7Parte frazionaria: da decimale a binario

La slide 26 va solo da binario a decimale (pesi 2−1,2−2,…2^{-1}, 2^{-2}, \ldots). Per andare al contrario serve l’algoritmo “rovesciato”: moltiplicare per 2 la parte frazionaria e prendere la parte intera come bit, ripetendo sulla parte frazionaria che resta. Perché funziona: moltiplicare per 2 sposta la virgola di un posto a destra, e il bit che passa a sinistra della virgola è il primo dopo la virgola. A differenza dei resti, i bit si leggono dal primo all’ultimo.

Esempio 1, 0.3750.375:

passocalcolobitresta
10.375⋅2=0.750.375 \cdot 2 = 0.7500.75
20.75⋅2=1.50.75 \cdot 2 = 1.510.5
30.5⋅2=1.00.5 \cdot 2 = 1.010

0.375=0.01120.375 = 0.011_2. Controllo: 0.25+0.125=0.3750.25 + 0.125 = 0.375.

Esempio 2, 0.10.1:

passocalcolobitresta
10.1⋅2=0.20.1 \cdot 2 = 0.200.2
20.2⋅2=0.40.2 \cdot 2 = 0.400.4
30.4⋅2=0.80.4 \cdot 2 = 0.800.8
40.8⋅2=1.60.8 \cdot 2 = 1.610.6
50.6⋅2=1.20.6 \cdot 2 = 1.210.2
60.2⋅2=0.40.2 \cdot 2 = 0.400.4, come al passo 2

Al passo 6 il resto 0.2 è già comparso: da qui la sequenza si ripete per sempre. 0.1=0.00011‾20.1 = 0.0\overline{0011}_2, periodico, come 1/3=0.3‾1/3 = 0.\overline{3} in decimale (verificato con frazioni esatte in Python). Con un numero finito di bit 0.1 si può solo approssimare: è il motivo per cui in C 0.1 + 0.2 == 0.3 è falso, in Tipi di dati e conversioni.

2.8Codificare nella virgola mobile del prof

La slide fa solo la decodifica (bit → numero). La codifica si fa al contrario:

  1. scrivi il modulo in binario, parte intera e frazionaria;
  2. sposta la virgola finché il numero ha la forma 0.1…0.1\ldots (prima della virgola 0, subito dopo un 1): ogni posto a sinistra aumenta l’esponente di 1, ogni posto a destra lo diminuisce;
  3. segno in 1 bit, esponente in CA2 su 8 bit, mantissa = i bit dopo la virgola, completati con zeri fino a 23.

Esempio 1, −2.75-2.75. 2=1022 = 10_2, 0.75=0.1120.75 = 0.11_2, quindi 2.75=10.1122.75 = 10.11_2. Virgola 2 posti a sinistra: 0.1011⋅220.1011 \cdot 2^2. Segno 1, esponente +2+2 = 00000010, mantissa 1011 e 19 zeri:

1 00000010 10110000000000000000000

Controllo: 0.10112=0.5+0.125+0.0625=0.68750.1011_2 = 0.5 + 0.125 + 0.0625 = 0.6875, e −0.6875⋅4=−2.75-0.6875 \cdot 4 = -2.75.

Esempio 2, 0.1250.125, esponente negativo. 0.125=0.00120.125 = 0.001_2: la virgola va spostata 2 posti a destra per avere 0.10.1, quindi 0.1⋅2−20.1 \cdot 2^{-2}. Esponente −2-2 in CA2: 22 = 00000010, invertito 11111101, più 1 11111110.

0 11111110 10000000000000000000000

Controllo: 0.5⋅2−2=0.1250.5 \cdot 2^{-2} = 0.125. È lo stesso schema della slide 30 (−0.25-0.25 con esponente 11111111).

2.9Shift: moltiplicare e dividere per 2

(slide 57) Spostare tutti i bit di una posizione a sinistra (shift, in C l’operatore <<) moltiplica per 2, esattamente come aggiungere uno zero a destra in base 10 moltiplica per 10. Lo shift a destra (>>) divide per 2, scartando il resto.

00001101   13
00011010   26     13 << 1
00110100   52     13 << 2

3Metodo

Prima di ogni esercizio si riconosce la direzione: da una base qualsiasi verso 10 si usano i pesi; da 10 verso un’altra base si usa l’algoritmo dei resti; fra 2, 8 e 16 si passa per i gruppi di bit, senza toccare il decimale.

Da base bb a decimale (pesi).

  1. Numera le cifre da destra, a partire da 0.
  2. Moltiplica ogni cifra per bb elevato alla sua posizione (in esadecimale, prima converti le lettere: A=10 … F=15).
  3. Somma.

Da decimale a base bb (resti).

  1. Dividi il numero per bb: scrivi quoziente e resto.
  2. Ripeti sul quoziente finché il quoziente è 0.
  3. Leggi i resti dall’ultimo al primo. In base 16, i resti da 10 a 15 diventano A-F.
  4. Controllo: riconverti con i pesi.

Da binario a ottale o esadecimale. Dividi i bit in gruppi da 3 (ottale) o 4 (esadecimale) partendo da destra; se l’ultimo gruppo a sinistra è incompleto, aggiungi zeri a sinistra (padding). Ogni gruppo diventa una cifra.

Da ottale o esadecimale a binario. Ogni cifra diventa il suo gruppo di 3 o 4 bit, scritto sempre con tutti i bit (2 in esadecimale è 0010, non 10). Gli zeri iniziali del risultato si possono togliere.

Fra ottale ed esadecimale. Si passa per il binario: cifre in gruppi da 4, poi raggruppa da 3 (o il contrario). In alternativa, passando per il decimale come nella slide 58: prima pesi, poi resti.

Somma fra basi diverse (esercizio d’esame, nella provetta del 22/10/2024: «Calcolare la somma tra (16)8(16)_8 e (80)16(80)_{16} […] mostrando tutti i passaggi per la somma e le conversioni», con quattro risultati da marcare SI/NO). Si riconosce dai pedici diversi sugli addendi. Due strade, e all’esame conviene farle tutte e due, una come controllo dell’altra:

strada A, dal decimale              strada B, dal binario (solo basi 2, 8, 16)
  1. ogni addendo in base 10           1. ogni addendo in binario: 3 bit per cifra
     con i pesi                           ottale, 4 per cifra esadecimale
  2. somma in base 10                  2. somma in colonna con i riporti
  3. risultato nelle basi richieste    3. risultato in 8 e 16 con i gruppi
     con i resti (o in binario            da destra, in 10 con i pesi
     e poi a gruppi)

La serie graduata di esercizi è nella pagina esercizi, Esercizi 6-14.

Somma nella stessa base bb, in colonna. Come in base 10: per ogni colonna cifra più cifra più riporto; se arriva a bb o lo supera scrivi somma meno bb e porta 1. Le lettere esadecimali si convertono in numero prima di sommare e si riconvertono dopo.

Somma binaria in colonna. Da destra, con la tabella 0+0=00+0=0, 0+1=10+1=1, 1+0=11+0=1, 1+1=01+1=0 con riporto 1. Con il riporto entrante: 1+1+1=11+1+1 = 1 con riporto 1.

Leggere una sequenza di bit in tre modi (esempio con 8 bit):

Scrivere −x-x in CA2 su NN bit.

  1. Controlla che −x≥−2N−1-x \geq -2^{N-1}, altrimenti non è rappresentabile.
  2. Scrivi xx in binario su NN bit, con gli zeri a sinistra.
  3. Inverti tutti i bit.
  4. Aggiungi 1.
  5. Controllo: l’MSB deve essere 1, e decodificando devi ritrovare −x-x.

Scorciatoia per il passo 3-4: da destra copia i bit fino al primo 1 compreso, poi inverti tutti gli altri.

Sottrazione a−ba - b in CA2. Si calcola a+(−b)a + (-b): codifica aa e −b-b su NN bit, somma in colonna, scarta l’eventuale riporto oltre l’NN-esimo bit.

Overflow in CA2. C’è overflow se e solo se i due addendi hanno lo stesso segno e il risultato ha segno opposto. Due numeri di segno diverso non vanno mai in overflow. Il riporto in uscita da solo non dice niente (nella sottrazione si scarta sempre).

Decodificare un numero in virgola fissa. Pesi positivi a sinistra della virgola, 2−1,2−2,…2^{-1}, 2^{-2}, \ldots a destra.

Codificare un decimale con la virgola. Parte intera con i resti (letti dall’ultimo), parte frazionaria con le moltiplicazioni per 2 (lette dal primo). Se i bit a disposizione finiscono prima che la parte frazionaria arrivi a 0, il numero è approssimato: si troncano i bit in più e si dice di quanto si sbaglia.

Decodificare la virgola mobile semplificata del prof. Segno dal primo bit; esponente ee dagli 8 bit in CA2; mantissa mm letta come 0.bit0.{\rm bit}; X=±m⋅2eX = \pm m \cdot 2^e.

4Esempi svolti a lezione

4.1Da decimale a binario: 19 e 30

(slide 14-20) La tabella del prof ha divisione, resto, posizione e valore: la colonna “valore” è il controllo.

divisionequozienterestoposizionevalore
19 : 29101⋅20=11 \cdot 2^0 = 1
9 : 24111⋅21=21 \cdot 2^1 = 2
4 : 22020⋅22=00 \cdot 2^2 = 0
2 : 21030⋅23=00 \cdot 2^3 = 0
1 : 20141⋅24=161 \cdot 2^4 = 16

Resti dall’ultimo al primo: 1910=10011219_{10} = 10011_2. Controllo: 16+2+1=1916 + 2 + 1 = 19.

divisionequozienterestoposizionevalore
30 : 215000
15 : 27112
7 : 23124
3 : 21138
1 : 201416

3010=11110230_{10} = 11110_2. Controllo: 16+8+4+2=3016 + 8 + 4 + 2 = 30. Nota: 30=2⋅1530 = 2 \cdot 15, e infatti 1111011110 è 11111111 (=15= 15) con uno zero in fondo: moltiplicare per 2 aggiunge uno zero a destra.

4.2Algoritmo dei resti: linguaggio naturale, pseudocodice e codice

(slide 23-32) La descrizione in linguaggio naturale della slide 24: “Chiedi all’utente un numero d, poi dividilo per due ottenendo un quoziente ed un resto. Metti da parte il resto e dividi di nuovo il quoziente. Continua finché il quoziente è zero. Metti insieme i resti in ordine inverso, dall’ultimo verso il primo: è il numero binario.” Il pseudocodice, con l’errore della slide 29 (l’indice dopo il primo ciclo vale il numero di cifre, non l’ultima posizione) e la correzione della slide 30 (i ← i - 1 fra i due cicli), è spiegato riga per riga in Array, sezione “Da decimale a binario”.

Il codice della slide 31 usa un array di _Bool da 100 celle, legge senza controlli e stampa all’indietro con i-- prima della stampa (così l’errore dell’indice non c’è). La slide 32 chiede di tenere conto del limite dell’array e di segnalare quando il numero richiederebbe più cifre di quelle disponibili. Versione con 8 cifre al massimo, per vedere il limite all’opera:

#include <stdio.h>

#define MAX_CIFRE 8

int main(void)
{
    int numero_binario[MAX_CIFRE];
    int numero_d;
    int i = 0;

    printf("Numero decimale: ");
    if (scanf("%d", &numero_d) != 1 || numero_d < 0) {
        printf("input non valido\n");
        return 1;
    }
    if (numero_d == 0) {
        printf("0\n");
        return 0;
    }
    while (numero_d != 0 && i < MAX_CIFRE) {
        numero_binario[i] = numero_d % 2;
        numero_d = numero_d / 2;
        i++;
    }
    if (numero_d != 0) {
        printf("servono piu' di %d cifre binarie\n", MAX_CIFRE);
        return 1;
    }
    while (i > 0) {
        i--;
        printf("%d", numero_binario[i]);
    }
    printf("\n");
    return 0;
}
inputstampa dopo il prompt (verificato)
1910011
3011110
25511111111
256servono piu' di 8 cifre binarie
00

L’idea per il limite: il ciclo si ferma per due motivi, numero finito o array pieno. Dopo il ciclo si guarda quale dei due: se numero_d non è ancora 0, l’array era pieno prima di finire. 255 sta in 8 cifre, 256 (=28= 2^8) ne vuole 9.

Tracing del ciclo dei resti per 19 (le variabili alla fine di ogni giro):

gironumero_d % 2scrivenumero_d dopoi dopo
11numero_binario[0] = 191
21numero_binario[1] = 142
30numero_binario[2] = 023
40numero_binario[3] = 014
51numero_binario[4] = 105

Poi la stampa parte con i 5: decrementa a 4 e stampa numero_binario[4], poi 3, 2, 1, 0. Esce 10011.

4.3Da binario a decimale (e un errore del prof)

(slide 33-36) Il numero binario sta in un array, cifra più significativa nella cella 0. Il “trabocchetto” segnalato dalla slide 34: la cifra con peso minore (a0a_0) sta nella cella di indice maggiore (la 7 con 8 cifre). Quindi la cella i ha peso 2n−1−i2^{n-1-i}, oppure, equivalentemente, la cella n - 1 - i ha peso 2i2^i.

La soluzione della slide 36 calcola 2i2^i come exp(log(2)*i), cioè eiln⁡2e^{i \ln 2}, con la libreria matematica e i double. Eseguita su {1, 0, 0, 0, 0, 0, 1, 1} (che è 128+2+1=131128 + 2 + 1 = 131) stampa 130 (verificato). Il motivo: exp(log(2)*i) non dà potenze esatte, per esempio per i=7i = 7 dà 127.99999999999997127.99999999999997. La somma dec + bin[...] * exp(...) è un double e viene troncata quando si assegna all’int dec: 3+127.99999999999997=130.999999999999973 + 127.99999999999997 = 130.99999999999997 diventa 130. È la conversione implicita double→int di Tipi di dati e conversioni. Con gli interi non si usano funzioni a virgola mobile: il peso si tiene in una variabile e si raddoppia a ogni passo.

#include <stdio.h>

#define N 8

int main(void)
{
    int bin[N] = {1, 0, 0, 0, 0, 0, 1, 1};
    int i;
    int dec = 0;
    int peso = 1;

    for (i = N - 1; i >= 0; i--) {
        dec = dec + bin[i] * peso;
        peso = peso * 2;
    }
    printf("%d\n", dec);
    return 0;
}

Stampa 131 (verificato). Il ciclo parte dall’ultima cella (peso 1) e va verso la prima, raddoppiando il peso: 1⋅1+1⋅2+0⋅4+…+1⋅1281 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + \ldots + 1 \cdot 128.

4.4Ottale ed esadecimale con i resti

(slide 37-40, 43-45) Stesso algoritmo, dividendo per 8 o per 16. Nella slide 37 il prof avverte che l’array dei resti va riempito “a partire dalla posizione di indice maggiore” se lo si vuole poi leggere in avanti; il codice della slide 40 invece lo riempie da 0 e lo stampa all’indietro, che è equivalente.

691069_{10} in ottale:

divisionequozienterestoposizionevalore
69 : 88505⋅1=55 \cdot 1 = 5
8 : 81010⋅8=00 \cdot 8 = 0
1 : 80121⋅64=641 \cdot 64 = 64

6910=105869_{10} = 105_8. Controllo: 64+5=6964 + 5 = 69.

2501102501_{10} in esadecimale:

divisionequozienterestocifravalore
2501 : 16156555⋅1=55 \cdot 1 = 5
156 : 16912C12⋅16=19212 \cdot 16 = 192
9 : 160999⋅256=23049 \cdot 256 = 2304

250110=9C5162501_{10} = 9C5_{16}. Controllo: 2304+192+5=25012304 + 192 + 5 = 2501. (La slide scrive “C⋅161=12⋅161=0⋅8=192C \cdot 16^1 = 12 \cdot 16^1 = 0 \cdot 8 = 192”: il “0⋅80 \cdot 8” è un refuso copiato dall’esempio ottale.)

Il programma della slide 40 è quello binario con 8 al posto di 2. Una versione unica per ogni base da 2 a 16, che usa una stringa come tabella delle cifre (cifre[12] è 'C'):

#include <stdio.h>

#define MAX_CIFRE 16

int main(void)
{
    char cifre[] = "0123456789ABCDEF";
    char risultato[MAX_CIFRE];
    int numero_d;
    int base;
    int i = 0;

    if (scanf("%d %d", &numero_d, &base) != 2 || numero_d < 0 || base < 2 || base > 16) {
        printf("input non valido\n");
        return 1;
    }
    do {
        risultato[i] = cifre[numero_d % base];
        numero_d = numero_d / base;
        i++;
    } while (numero_d != 0 && i < MAX_CIFRE);
    while (i > 0) {
        i--;
        putchar(risultato[i]);
    }
    putchar('\n');
    return 0;
}

Con input 69 8 stampa 105, con 2501 16 stampa 9C5, con 0 2 stampa 0 (verificati). Il do-while fa almeno un giro, e così lo zero esce da solo senza il caso speciale. Con MAX_CIFRE 16 qualunque int non negativo ci sta anche in base 4 (16 cifre bastano per 416=2324^{16} = 2^{32}); in base 2 i numeri oltre 65535 verrebbero troncati, e servirebbe 32.

4.5Da ottale ed esadecimale a decimale (due errori nelle slide)

(slide 41-42, 46-47) Le cifre sono nell’array dalla più significativa (cella 0) alla meno significativa.

Ottale, array 7 1 2 0, cioè 712087120_8:

71208=0⋅80+2⋅81+1⋅82+7⋅83=0+16+64+3584=3664107120_8 = 0 \cdot 8^0 + 2 \cdot 8^1 + 1 \cdot 8^2 + 7 \cdot 8^3 = 0 + 16 + 64 + 3584 = 3664_{10}

La formula della slide è giusta, ma il risultato scritto, 2097161, è sbagliato: vale 3664 (verificato).

Esadecimale, array 1 A 2 C, cioè 1A2C161A2C_{16}:

1A2C16=12⋅160+2⋅161+10⋅162+1⋅163=12+32+2560+4096=6700101A2C_{16} = 12 \cdot 16^0 + 2 \cdot 16^1 + 10 \cdot 16^2 + 1 \cdot 16^3 = 12 + 32 + 2560 + 4096 = 6700_{10}

La slide scrive “DEC(C2A1) = 1⋅160+10⋅161+2⋅162+12⋅1631 \cdot 16^0 + 10 \cdot 16^1 + 2 \cdot 16^2 + 12 \cdot 16^3 = 6700”: il risultato 6700 è quello di 1A2C1A2C, ma la formula assegna peso 16016^0 alla cella 0, proprio l’errore contro cui avverte la stessa slide. Letta così, la formula calcola C2A116=49825C2A1_{16} = 49825. La regola giusta è quella del riquadro: la cella di indice maggiore ha il peso minore.

4.6Esadecimale e ottale passando dal binario

(slide 48-52)

A1F16A1F_{16} in ottale. Ogni cifra esadecimale in 4 bit, poi gruppi da 3 da destra:

A    1    F            esadecimale
1010 0001 1111         4 bit per cifra
101 000 011 111        rigruppati da 3, partendo da destra
5   0   3   7          ottale

A1F16=50378A1F_{16} = 5037_8. Controllo: A1F16=2560+16+15=2591A1F_{16} = 2560 + 16 + 15 = 2591 e 50378=2560+0+24+7=25915037_8 = 2560 + 0 + 24 + 7 = 2591.

123481234_8 in esadecimale, al contrario (slide 49):

1   2   3   4          ottale
001 010 011 100        3 bit per cifra
0010 1001 1100         rigruppati da 4, partendo da destra
2    9    C            esadecimale

12348=29C161234_8 = 29C_{16} (=66810= 668_{10}).

F16F_{16} in ottale (slide 50-51): 1111 ha 4 bit, e il gruppo a sinistra resta di un bit solo. Si aggiungono zeri a sinistra (padding): 001 111, quindi F16=178F_{16} = 17_8 (=1510= 15_{10}).

8F168F_{16} in ottale (slide 52): 1000 1111 sono 8 bit; da destra 111, 001, poi 10 che diventa 010. Quindi 010 001 111 cioè 2178217_8 (=14310= 143_{10}).

4.7Somma e prodotto in binario

(slide 53-56) 54+11654 + 116 su 8 bit, colonna per colonna da destra (bit 0) a sinistra (bit 7):

bit76543210
riporto entrante11101000
5400110110
11601110100
somma10101010

Risultato 10101010 =128+32+8+2=170= 128 + 32 + 8 + 2 = 170, e infatti 54+116=17054 + 116 = 170. Lettura di una colonna: al bit 5 si sommano 1+11 + 1 più il riporto 1, fa 3, cioè cifra 1 e riporto 1.

Esercizio della slide 55, 00011011+0011101000011011 + 00111010:

bit76543210
riporto entrante01110100
2700011011
5800111010
somma01010101

01010101 =64+16+4+1=85=27+58= 64 + 16 + 4 + 1 = 85 = 27 + 58.

Prodotto 0110⋅10100110 \cdot 1010 (6⋅106 \cdot 10, slide 56): come in colonna in base 10, ma ogni riga parziale è o zero o il primo fattore spostato.

      0110      6
    × 1010     10
    ------
      0000      bit 0 del secondo = 0
     0110       bit 1 = 1: 0110 spostato di 1
    0000        bit 2 = 0
   0110         bit 3 = 1: 0110 spostato di 3
   -------
   0111100     60

Controllo: 0110≪1=120110 \ll 1 = 12, 0110≪3=480110 \ll 3 = 48, 12+48=6012 + 48 = 60. Moltiplicare in binario è sommare copie spostate del primo fattore: per questo lo shift è l’operazione base.

4.8Ottale ed esadecimale passando dal decimale

(slide 58) Il prof compone due “funzioni”: OttaleToDecimale, poi DecimaleToEsadecimale sul risultato. È l’anticipo delle funzioni del deck 6.2.

23708=2⋅512+3⋅64+7⋅8+0=1024+192+56=1272102370_8 = 2 \cdot 512 + 3 \cdot 64 + 7 \cdot 8 + 0 = 1024 + 192 + 56 = 1272_{10}
divisionequozienteresto
1272 : 16798
79 : 16415 (F)
4 : 1604

127210=4F8161272_{10} = 4F8_{16}. Per il binario: 237082370_8 = 010 011 111 000 = 0100 1111 1000 = 4F8164F8_{16}, stesso risultato senza divisioni.

4.9Complemento a 2 e virgola mobile

(slide 22-24) Cambio di segno su 4 bit:

+6 = 0110    inverto: 1001    sommo 1: 1010 = -6
+4 = 0100    inverto: 1011    sommo 1: 1100 = -4

Controllo con il peso negativo dell’MSB: 1010 vale −8+2=−6-8 + 2 = -6, 1100 vale −8+4=−4-8 + 4 = -4.

Domande della slide 24 per una parola di 8 bit:

  1. Intervallo: da −27=−128-2^7 = -128 a 27−1=1272^7 - 1 = 127.
  2. Rappresentazioni: +1+1 è 00000001; 00 è 00000000; −1-1 si ottiene da 00000001 invertendo (11111110) e sommando 1: 11111111. Controllo: −128+127=−1-128 + 127 = -1.

Virgola mobile semplificata (slide 29-31), passo per passo:

bitsegnoesponente (CA2)mantissacalcoloXX
1 00000010 11011000...−102=210_2 = 20.110112=0.5+0.25+0.0625+0.03125=0.843750.11011_2 = 0.5 + 0.25 + 0.0625 + 0.03125 = 0.843750.84375⋅220.84375 \cdot 2^2−3.375-3.375
1 11111111 10000000...−11111111 in CA2 =−1= -10.12=0.50.1_2 = 0.50.5⋅2−10.5 \cdot 2^{-1}−0.25-0.25
0 00000011 10100000...+112=311_2 = 30.1012=0.6250.101_2 = 0.6250.625⋅230.625 \cdot 2^3+5+5

Leggendo l’esponente come spostamento della virgola: nel primo 0.110110.11011 con virgola 2 posti a destra è 11.0112=3.37511.011_2 = 3.375; nel secondo 0.10.1 con virgola 1 posto a sinistra è 0.012=0.250.01_2 = 0.25; nel terzo 0.1010.101 con virgola 3 posti a destra è 1012=5101_2 = 5.

4.10Caratteri e codice ASCII

(slide 35-36) Leggere caratteri fino a #, stampare il codice ASCII e, per le minuscole, la maiuscola corrispondente. L’idea: 'a' - 'A' è lo scarto fisso (32) fra minuscole e maiuscole, quindi la maiuscola di C è C - ('a' - 'A'). Il codice della slide legge con scanf("%c", &C), che legge anche gli a capo: dopo ogni Invio il ciclo stampa il codice 10 dell’a capo (il deck 5.1 lo segnala come “ATTENZIONE: comportamento di scanf con LF”). Con lo spazio prima di %c gli spazi bianchi vengono saltati:

#include <stdio.h>

int main(void)
{
    char c;

    printf("Inserire caratteri, # per terminare\n");
    while (scanf(" %c", &c) == 1 && c != '#') {
        printf("Il codice ASCII di %c e' %d\n", c, c);
        if (c >= 'a' && c <= 'z')
            printf("  maiuscola: %c, codice %d\n", c - ('a' - 'A'), c - ('a' - 'A'));
    }
    return 0;
}

Con input a Z a capo 3#q stampa (verificato):

Inserire caratteri, # per terminare
Il codice ASCII di a e' 97
  maiuscola: A, codice 65
Il codice ASCII di Z e' 90
Il codice ASCII di 3 e' 51

Il %c e il %d sullo stesso char sono la dimostrazione di “un dato, due interpretazioni”: stessi bit, stampati come carattere e come intero. La q dopo il # non viene letta.

4.11Quiz di conversione

(slide 59-67) Le risposte ufficiali sono giuste (verificate); i passaggi:

domandaresti (dal primo all’ultimo)risultatocontrollo
251025_{10} in base 825:8 = 3 r 1; 3:8 = 0 r 331831_824+124 + 1
12510125_{10} in base 8125:8 = 15 r 5; 15:8 = 1 r 7; 1:8 = 0 r 11758175_864+56+564 + 56 + 5
1024101024_{10} in base 81024:8 = 128 r 0; 128:8 = 16 r 0; 16:8 = 2 r 0; 2:8 = 0 r 2200082000_82⋅5122 \cdot 512
251025_{10} in base 1625:16 = 1 r 9; 1:16 = 0 r 1191619_{16}16+916 + 9
25510255_{10} in base 16255:16 = 15 r 15; 15:16 = 0 r 15FF16FF_{16}240+15240 + 15
10010100_{10} in base 16100:16 = 6 r 4; 6:16 = 0 r 6641664_{16}96+496 + 4
4095104095_{10} in base 164095:16 = 255 r 15; 255:16 = 15 r 15; 15:16 = 0 r 15FFF16FFF_{16}3840+240+153840 + 240 + 15

1024=210=83⋅21024 = 2^{10} = 8^{3} \cdot 2 spiega il 200082000_8; 4095=163−14095 = 16^3 - 1 spiega le tre F, come 999=103−1999 = 10^3 - 1 in decimale.

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Rappresentazione dell’informazione (esercizi).

6Errori tipici

7Domande