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 :
- si usano cifre, da a ;
- il valore di una cifra dipende dalla posizione: la cifra in posizione (contando da destra, da 0) vale cifra per ;
- le cifre diventano più significative andando verso sinistra.
In formula, il numero in base vale
| base | nome | cifre | pesi (da destra) |
|---|---|---|---|
| 10 | decimale | 0-9 | 1, 10, 100, 1000 |
| 2 | binario | 0, 1 | 1, 2, 4, 8, 16, 32, 64, 128 |
| 8 | ottale | 0-7 | 1, 8, 64, 512 |
| 16 | esadecimale | 0-9, A=10, B=11, C=12, D=13, E=14, F=15 | 1, 16, 256, 4096 |
Gli esempi delle slide, con i passaggi:
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 torna a 0 con un riporto sulla posizione dopo.
| dec | esa | ott | bin | dec | esa | ott | bin | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 11 | B | 13 | 1011 | |
| 1 | 1 | 1 | 1 | 12 | C | 14 | 1100 | |
| 2 | 2 | 2 | 10 | 13 | D | 15 | 1101 | |
| 3 | 3 | 3 | 11 | 14 | E | 16 | 1110 | |
| 4 | 4 | 4 | 100 | 15 | F | 17 | 1111 | |
| 5 | 5 | 5 | 101 | 16 | 10 | 20 | 10000 | |
| 6 | 6 | 6 | 110 | 17 | 11 | 21 | 10001 | |
| 7 | 7 | 7 | 111 | 18 | 12 | 22 | 10010 | |
| 8 | 8 | 10 | 1000 | 19 | 13 | 23 | 10011 | |
| 9 | 9 | 11 | 1001 | 20 | 14 | 24 | 10100 | |
| 10 | A | 12 | 1010 |
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 bit ci sono combinazioni, quindi si rappresentano i naturali da a :
| bit | combinazioni | intervallo senza segno |
|---|---|---|
| 8 (1 byte) | da 0 (00000000) a 255 (11111111) | |
| 16 | da 0 a 65535 | |
| 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 è , 10011010 è . Due difetti: lo zero ha due codifiche (00000000 è , 10000000 è ), e la somma richiede un circuito che guardi i segni, perché sommare i bit “così come sono” dà risultati sbagliati.
Con bit il modulo ha bit, quindi si rappresentano i valori da a : con 8 bit da a , cioè 255 valori con 256 codici, perché lo zero ne spreca uno. Il secondo difetto con un esempio su 4 bit: è 0010, è 1010; sommati in colonna danno 1100, che in modulo e segno è 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:
- lo zero ha una sola codifica;
- 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:
- con bit si codificano i valori da a ;
- il bit più significativo (MSB) rappresenta il segno;
- per decodificare: se l’MSB è 0 si procede come per un naturale; se l’MSB è 1 si decodifica come naturale e poi si sottrae ;
- per invertire un numero (cambiargli segno) si invertono le singole cifre e poi si aggiunge uno.
La slide 20 dice “se il MSB è 1, si decodifica e poi si sottrae ”. Va letta bene, perché le versioni corrette sono due e mescolarle dà un errore:
- si decodificano tutti gli bit come naturale e si sottrae :
1111vale 15, e ; - si decodificano solo gli altri bit e si sottrae :
111vale 7, e .
Decodificare tutti gli bit e sottrarre darebbe , sbagliato. La seconda versione si ricorda così: l’MSB pesa invece di , gli altri bit pesano come al solito. 1111 vale .
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 (); da 0000 andando indietro si contano i negativi: 1111 è , 1110 è , fino a 1000 (). Il CA2 è proprio questo: un numero negativo è il codice che si trova passi prima di zero, cioè il naturale .
| dec | CA2 4 bit | dec | CA2 4 bit | |
|---|---|---|---|---|
| 7 | 0111 | -1 | 1111 | |
| 6 | 0110 | -2 | 1110 | |
| 5 | 0101 | -3 | 1101 | |
| 4 | 0100 | -4 | 1100 | |
| 3 | 0011 | -5 | 1011 | |
| 2 | 0010 | -6 | 1010 | |
| 1 | 0001 | -7 | 1001 | |
| 0 | 0000 | -8 | 1000 |
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 e : in CA2 a 4 bit dà 1000, cioè . L’intervallo è asimmetrico ( c’è, 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: , , , . Con 4 bit per parte:
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 sposta la virgola di posti a destra (a sinistra se ).
Lo standard vero (slide 32) differisce in tre punti: la mantissa sta in (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 ; ci sono due zeri, e . La slide dice “per bit il bias è ”: il valore dello standard è , cioè 127 per 8 bit. Gli intervalli rappresentabili sono circa e .
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:
| carattere | codice | perché serve |
|---|---|---|
'0' … '9' | 48 … 57 | consecutivi: c - '0' dà la cifra |
'A' … 'Z' | 65 … 90 | consecutivi |
'a' … 'z' | 97 … 122 | consecutivi, 32 dopo le maiuscole |
| spazio | 32 | |
'\n' | 10 | carattere di controllo |
'\0' | 0 | terminatore 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 e , 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 ) Si scrive il numero già scomposto in potenze di 2:
Tutti i termini tranne l’ultimo contengono almeno un fattore 2. Dividendo per 2:
- il resto è l’ultimo termine, cioè il bit (qui 0): ogni resto della divisione per due dà il bit meno significativo del dividendo;
- il quoziente è il numero con tutti gli altri bit spostati di una posizione a destra: .
Ripetendo su 5 si ottiene con quoziente 2, poi con quoziente 1, poi 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 , dividendo per .
2.3Quanti bit servono
Con bit si hanno configurazioni. Per rappresentare valori diversi serve il più piccolo con . Per 300 valori: , , quindi 9 bit. Per 654 valori: , , quindi 10 bit.
Per i naturali da 0 a i valori sono : 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:
| bit | naturale | modulo e segno | CA2 |
|---|---|---|---|
11111111 | segno −, modulo 1111111 : | ||
10000000 | segno −, modulo 0: | ||
01111111 | (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 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 , per ogni colonna da destra:
- somma le due cifre e il riporto entrante (in decimale, è comodo);
- se la somma è minore di , scrivila e il riporto è 0;
- se è maggiore o uguale a , scrivi somma meno e porta 1.
È la stessa cosa che fai in base 10 con : scrivi 2 e porti 1, perché 12 supera 10. In base 8 il “giro” avviene a 8, in base 16 a 16.
Esempio 1, :
| posizione | 2 | 1 | 0 |
|---|---|---|---|
| riporto entrante | 1 | 1 | 0 |
| 0 | 4 | 7 | |
| 0 | 3 | 5 | |
| somma | 1 | 0 | 4 |
- colonna 0: , scrivo , porto 1;
- colonna 1: , scrivo , porto 1;
- colonna 2: , scrivo 1.
Risultato . Controllo in decimale: , , , e .
Esempio 2, (le lettere si convertono prima: C = 12, B = 11):
| posizione | 2 | 1 | 0 |
|---|---|---|---|
| riporto entrante | 1 | 1 | 0 |
| 0 | 9 | C | |
| 0 | 7 | B | |
| somma | 1 | 1 | 7 |
- colonna 0: , scrivo , porto 1;
- colonna 1: , scrivo , porto 1;
- colonna 2: .
Risultato . Controllo: , , , e (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: si fa come , e il riporto oltre l’ultimo bit si scarta.
Esempio 1, . = 0101; = 0011, invertito 1100, più 1 1101 (controllo: ).
| posizione | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| riporto entrante | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 1 | |
| somma | 0 | 0 | 1 | 0 |
Dalla colonna 3 esce un riporto 1, che si scarta. Restano i 4 bit 0010 , ed è giusto. Il riporto in uscita qui c’è ma non è un errore: addendi di segno diverso non vanno mai in overflow.
Esempio 2, . = 1010 (slide 22), : 0101 invertito 1010, più 1 1011.
| posizione | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| riporto entrante | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 1 | |
| somma | 0 | 1 | 0 | 1 |
Scartato il riporto, 0101 . Due negativi hanno dato un positivo: overflow. Il valore vero, , è fuori da . Sulla ruota: partendo da e facendo 5 passi indietro si scavalca e si ricomincia da .
2.7Parte frazionaria: da decimale a binario
La slide 26 va solo da binario a decimale (pesi ). 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, :
| passo | calcolo | bit | resta |
|---|---|---|---|
| 1 | 0 | 0.75 | |
| 2 | 1 | 0.5 | |
| 3 | 1 | 0 |
. Controllo: .
Esempio 2, :
| passo | calcolo | bit | resta |
|---|---|---|---|
| 1 | 0 | 0.2 | |
| 2 | 0 | 0.4 | |
| 3 | 0 | 0.8 | |
| 4 | 1 | 0.6 | |
| 5 | 1 | 0.2 | |
| 6 | 0 | 0.4, come al passo 2 |
Al passo 6 il resto 0.2 è già comparso: da qui la sequenza si ripete per sempre. , periodico, come 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:
- scrivi il modulo in binario, parte intera e frazionaria;
- sposta la virgola finché il numero ha la forma (prima della virgola 0, subito dopo un 1): ogni posto a sinistra aumenta l’esponente di 1, ogni posto a destra lo diminuisce;
- segno in 1 bit, esponente in CA2 su 8 bit, mantissa = i bit dopo la virgola, completati con zeri fino a 23.
Esempio 1, . , , quindi . Virgola 2 posti a sinistra: . Segno 1, esponente = 00000010, mantissa 1011 e 19 zeri:
1 00000010 10110000000000000000000
Controllo: , e .
Esempio 2, , esponente negativo. : la virgola va spostata 2 posti a destra per avere , quindi . Esponente in CA2: = 00000010, invertito 11111101, più 1 11111110.
0 11111110 10000000000000000000000
Controllo: . È lo stesso schema della slide 30 ( 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 a decimale (pesi).
- Numera le cifre da destra, a partire da 0.
- Moltiplica ogni cifra per elevato alla sua posizione (in esadecimale, prima converti le lettere: A=10 … F=15).
- Somma.
Da decimale a base (resti).
- Dividi il numero per : scrivi quoziente e resto.
- Ripeti sul quoziente finché il quoziente è 0.
- Leggi i resti dall’ultimo al primo. In base 16, i resti da 10 a 15 diventano A-F.
- 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 e […] 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)
- Se il testo non dice la base del risultato, dalla in decimale e anche nelle basi di partenza.
- Se ci sono risultati da marcare SI/NO, converti il tuo risultato in tutte le basi delle opzioni e confronta cifra per cifra: le opzioni sbagliate sono quasi sempre il risultato con un riporto dimenticato.
- La strada B evita le divisioni ed è quella che il prof usa nella slide 58 per collegare ottale ed esadecimale. La strada A funziona con qualsiasi base (anche 3 o 5).
- Scrivi tutto: le tabelle dei resti, le colonne della somma con la riga dei riporti, il controllo. Il testo chiede “tutti i passaggi” e il punteggio va a quelli.
La serie graduata di esercizi è nella pagina esercizi, Esercizi 6-14.
Somma nella stessa base , in colonna. Come in base 10: per ogni colonna cifra più cifra più riporto; se arriva a o lo supera scrivi somma meno 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 , , , con riporto 1. Con il riporto entrante: con riporto 1.
Leggere una sequenza di bit in tre modi (esempio con 8 bit):
- naturale: somma dei pesi;
- modulo e segno: MSB è il segno, gli altri 7 bit il modulo;
- CA2: se MSB è 0 è come il naturale; se è 1, naturale meno (oppure MSB con peso ).
Scrivere in CA2 su bit.
- Controlla che , altrimenti non è rappresentabile.
- Scrivi in binario su bit, con gli zeri a sinistra.
- Inverti tutti i bit.
- Aggiungi 1.
- Controllo: l’MSB deve essere 1, e decodificando devi ritrovare .
Scorciatoia per il passo 3-4: da destra copia i bit fino al primo 1 compreso, poi inverti tutti gli altri.
Sottrazione in CA2. Si calcola : codifica e su bit, somma in colonna, scarta l’eventuale riporto oltre l’-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, 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 dagli 8 bit in CA2; mantissa letta come ; .
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.
| divisione | quoziente | resto | posizione | valore |
|---|---|---|---|---|
| 19 : 2 | 9 | 1 | 0 | |
| 9 : 2 | 4 | 1 | 1 | |
| 4 : 2 | 2 | 0 | 2 | |
| 2 : 2 | 1 | 0 | 3 | |
| 1 : 2 | 0 | 1 | 4 |
Resti dall’ultimo al primo: . Controllo: .
| divisione | quoziente | resto | posizione | valore |
|---|---|---|---|---|
| 30 : 2 | 15 | 0 | 0 | 0 |
| 15 : 2 | 7 | 1 | 1 | 2 |
| 7 : 2 | 3 | 1 | 2 | 4 |
| 3 : 2 | 1 | 1 | 3 | 8 |
| 1 : 2 | 0 | 1 | 4 | 16 |
. Controllo: . Nota: , e infatti è () 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;
}
| input | stampa dopo il prompt (verificato) |
|---|---|
| 19 | 10011 |
| 30 | 11110 |
| 255 | 11111111 |
| 256 | servono piu' di 8 cifre binarie |
| 0 | 0 |
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 () ne vuole 9.
Tracing del ciclo dei resti per 19 (le variabili alla fine di ogni giro):
| giro | numero_d % 2 | scrive | numero_d dopo | i dopo |
|---|---|---|---|---|
| 1 | 1 | numero_binario[0] = 1 | 9 | 1 |
| 2 | 1 | numero_binario[1] = 1 | 4 | 2 |
| 3 | 0 | numero_binario[2] = 0 | 2 | 3 |
| 4 | 0 | numero_binario[3] = 0 | 1 | 4 |
| 5 | 1 | numero_binario[4] = 1 | 0 | 5 |
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 () sta nella cella di indice maggiore (la 7 con 8 cifre). Quindi la cella i ha peso , oppure, equivalentemente, la cella n - 1 - i ha peso .
La soluzione della slide 36 calcola come exp(log(2)*i), cioè , con la libreria matematica e i double. Eseguita su {1, 0, 0, 0, 0, 0, 1, 1} (che è ) stampa 130 (verificato). Il motivo: exp(log(2)*i) non dà potenze esatte, per esempio per dà . La somma dec + bin[...] * exp(...) è un double e viene troncata quando si assegna all’int dec: 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: .
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.
in ottale:
| divisione | quoziente | resto | posizione | valore |
|---|---|---|---|---|
| 69 : 8 | 8 | 5 | 0 | |
| 8 : 8 | 1 | 0 | 1 | |
| 1 : 8 | 0 | 1 | 2 |
. Controllo: .
in esadecimale:
| divisione | quoziente | resto | cifra | valore |
|---|---|---|---|---|
| 2501 : 16 | 156 | 5 | 5 | |
| 156 : 16 | 9 | 12 | C | |
| 9 : 16 | 0 | 9 | 9 |
. Controllo: . (La slide scrive “”: il “” è 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 ); 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è :
La formula della slide è giusta, ma il risultato scritto, 2097161, è sbagliato: vale 3664 (verificato).
Esadecimale, array 1 A 2 C, cioè :
La slide scrive “DEC(C2A1) = = 6700”: il risultato 6700 è quello di , ma la formula assegna peso alla cella 0, proprio l’errore contro cui avverte la stessa slide. Letta così, la formula calcola . 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)
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
. Controllo: e .
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
().
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 ().
in ottale (slide 52): 1000 1111 sono 8 bit; da destra 111, 001, poi 10 che diventa 010. Quindi 010 001 111 cioè ().
4.7Somma e prodotto in binario
(slide 53-56) su 8 bit, colonna per colonna da destra (bit 0) a sinistra (bit 7):
| bit | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| riporto entrante | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 54 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 116 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| somma | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Risultato 10101010 , e infatti . Lettura di una colonna: al bit 5 si sommano più il riporto 1, fa 3, cioè cifra 1 e riporto 1.
Esercizio della slide 55, :
| bit | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| riporto entrante | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 27 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 58 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| somma | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
01010101 .
Prodotto (, 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: , , . 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.
| divisione | quoziente | resto |
|---|---|---|
| 1272 : 16 | 79 | 8 |
| 79 : 16 | 4 | 15 (F) |
| 4 : 16 | 0 | 4 |
. Per il binario: = 010 011 111 000 = 0100 1111 1000 = , 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 , 1100 vale .
Domande della slide 24 per una parola di 8 bit:
- Intervallo: da a .
- Rappresentazioni: è
00000001; è00000000; si ottiene da00000001invertendo (11111110) e sommando 1:11111111. Controllo: .
Virgola mobile semplificata (slide 29-31), passo per passo:
| bit | segno | esponente (CA2) | mantissa | calcolo | |
|---|---|---|---|---|---|
1 00000010 11011000... | − | ||||
1 11111111 10000000... | − | 11111111 in CA2 | |||
0 00000011 10100000... | + |
Leggendo l’esponente come spostamento della virgola: nel primo con virgola 2 posti a destra è ; nel secondo con virgola 1 posto a sinistra è ; nel terzo con virgola 3 posti a destra è .
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:
| domanda | resti (dal primo all’ultimo) | risultato | controllo |
|---|---|---|---|
| in base 8 | 25:8 = 3 r 1; 3:8 = 0 r 3 | ||
| in base 8 | 125:8 = 15 r 5; 15:8 = 1 r 7; 1:8 = 0 r 1 | ||
| in base 8 | 1024:8 = 128 r 0; 128:8 = 16 r 0; 16:8 = 2 r 0; 2:8 = 0 r 2 | ||
| in base 16 | 25:16 = 1 r 9; 1:16 = 0 r 1 | ||
| in base 16 | 255:16 = 15 r 15; 15:16 = 0 r 15 | ||
| in base 16 | 100:16 = 6 r 4; 6:16 = 0 r 6 | ||
| in base 16 | 4095:16 = 255 r 15; 255:16 = 15 r 15; 15:16 = 0 r 15 |
spiega il ; spiega le tre F, come in decimale.
5Esercizi tipo esame
In una pagina a parte, dal più facile al livello del 30: Rappresentazione dell’informazione (esercizi).
6Errori tipici
- Leggere i resti dal primo all’ultimo: il primo resto è la cifra meno significativa.
- Dimenticare l’ultima divisione (quella con quoziente 0) e perdere la cifra più significativa.
- Nelle conversioni con i gruppi, raggruppare partendo da sinistra invece che da destra, o scrivere una cifra esadecimale con meno di 4 bit (2 come
10invece di0010). - In esadecimale usare 10-15 come due cifre invece di A-F, o viceversa dimenticare di convertire le lettere nei pesi.
- Con il numero in un array, dare peso alla cella 0: la cella 0 contiene la cifra più significativa (slide 34, ed errore della slide 47).
- CA2: invertire i bit e dimenticare il ; oppure scrivere il positivo con meno bit di prima di invertire (gli zeri a sinistra diventano gli 1 del segno).
- CA2: decodificare tutti gli bit di un negativo e poi sottrarre invece di (la slide 20 sottrae , ma dai soli bit restanti).
- Dire che c’è overflow perché “c’è un riporto in uscita”: in CA2 conta solo il segno del risultato rispetto agli addendi.
- Confondere modulo e segno con CA2:
10000001è nel primo e nel secondo. - “Quanti bit per 256 valori”: 8, non 9. Per i valori da 0 a 256: 9.
- Calcolare potenze intere con
expelogo conpowe assegnare a unint: il risultatodoublepuò essere 127.99999 e viene troncato (slide 36). - Leggere caratteri con
scanf("%c")e stupirsi degli a capo: lo spazio in" %c"li salta. - Sommare in colonna due numeri scritti in basi diverse, per esempio cifra per cifra: le posizioni pesano in modo diverso, prima si porta tutto in una base.
- In una somma in base 16 scrivere la somma di colonna così com’è (
17invece di 1 con riporto), o in base 8 dimenticare che 8 non è una cifra. - Dimenticare la riga dei riporti nella somma binaria: le opzioni sbagliate delle domande SI/NO sono costruite proprio così.
- Parte frazionaria: leggere i bit delle moltiplicazioni per 2 dall’ultimo al primo (quello vale per i resti, qui è il contrario).
7Domande
-
Che differenza c’è fra informazione, dato e rappresentazione? Fai l’esempio del byte
01100001. -
Cos’è un sistema posizionale in base ? Come si calcola il valore di un numero?
-
Quali naturali si rappresentano con bit? Perché un intero del calcolatore ha sempre un massimo?
-
Perché l’algoritmo dei resti dà le cifre dalla meno significativa alla più significativa?
-
Perché un’unica cifra ottale corrisponde a 3 bit e una esadecimale a 4? Come si converte fra queste basi senza passare dal decimale?
-
Cos’è la rappresentazione in modulo e segno e quali sono i suoi due difetti?
-
Quale intervallo si rappresenta in CA2 con bit? Perché è asimmetrico?
-
Come si cambia segno a un numero in CA2? Come si decodifica un numero con MSB uguale a 1?
-
Quali sono i due vantaggi del CA2 rispetto al modulo e segno?
-
Quando c’è overflow in una somma in CA2?
-
Che differenza c’è fra virgola fissa e virgola mobile? Cosa rappresentano mantissa ed esponente?
-
Cos’è la tabella ASCII? Quanti valori copre lo standard e cosa sono i primi 32?
-
Perché il programma della slide 36 converte
10000011in 130 invece di 131? -
Quale intervallo si rappresenta in modulo e segno con bit? Perché un valore in meno del CA2?
-
Come si somma in colonna in base 8 o 16? Cosa fai quando la somma di una colonna arriva a ?
-
Come imposti una somma fra due numeri in basi diverse? Quali sono le due strade e quando si può usare quella dal binario?
-
Come si converte in binario la parte frazionaria di un numero decimale? In che ordine si leggono i bit?
-
Perché 0.1 non si rappresenta esattamente in binario?
-
11111111su 8 bit: quanto vale come naturale, in modulo e segno e in CA2?