Rappresentazione binaria dei dati

In memoria tutto è una sequenza di bit; il significato (intero, reale, carattere, istruzione) dipende da come il programma la interpreta. Questo spiega comportamenti che si vedono nei tipi di Python e C: overflow degli int in C, 0.1 + 0.2 != 0.3, dimensione delle stringhe in byte.

Basi di numerazione

Formula (valore di un numero in base $b$). Un numero in base $b$ con cifre $c_{n-1} \dots c_1 c_0$ vale

$$\sum_{i=0}^{n-1} c_i \, b^i$$

Esempio. int("2d", 16) restituisce 45 ($2\cdot16+13$) e bin(45) restituisce '0b101101'.

Proprietà (conversioni tra basi 10, 2 e 16)

• Da base 10 a base 2: divisioni successive per 2, i resti letti dal basso verso l'alto. $45 \to 22\,r1 \to 11\,r0 \to 5\,r1 \to 2\,r1 \to 1\,r0 \to 0\,r1$, quindi $101101_2$.
• Base 2 ↔ 16: ogni cifra esadecimale corrisponde a 4 bit ($0010\,1101_2 = 2D_{16}$). Per questo gli indirizzi di memoria e i byte si scrivono in esadecimale.

Esempio. hex(0b00101101) restituisce '0x2d': i gruppi 0010 e 1101 sono le cifre 2 e d.

bin(45), oct(45), hex(45)   # ('0b101101', '0o55', '0x2d')
int("101101", 2)            # 45
int("2d", 16)               # 45

Con $n$ bit si rappresentano $2^n$ configurazioni: 8 bit → 256, 16 → 65 536, 32 → circa $4{,}3 \cdot 10^9$.

Interi senza segno

Definizione (interi senza segno e overflow). Con $n$ bit: valori da $0$ a $2^n - 1$. Somma binaria in colonna con riporto; se il risultato non sta in $n$ bit si ha overflow e il bit di riporto finale si perde (il risultato è preso modulo $2^n$).

Esempio. A $8$ bit $255+1=256$ e il risultato preso modulo $2^8$ è $0$: in Python (255 + 1) % 256 restituisce 0.

Interi con segno: complemento a 2

Formula (valore in complemento a 2). Con $n$ bit il bit più significativo ha peso negativo $-2^{n-1}$:

$$x = -c_{n-1} 2^{n-1} + \sum_{i=0}^{n-2} c_i 2^i$$

Esempio. A $8$ bit, $1111\,1011=-128+64+32+16+8+2+1=-5$.

Proprietà (complemento a 2: intervallo, opposto e overflow)

• Intervallo: da $-2^{n-1}$ a $2^{n-1} - 1$ (8 bit: da $-128$ a $127$). Asimmetrico: c'è un negativo in più.
• Bit più significativo = 1 ⇔ numero negativo. Lo zero ha una sola rappresentazione.
• Opposto di un numero: si invertono tutti i bit e si somma 1. Esempio a 8 bit: $5 = 00000101$, inverto → $11111010$, +1 → $11111011 = -5$.
• La sommatrice è la stessa degli interi senza segno: è il motivo per cui il complemento a 2 si usa ovunque.
• Overflow: sommando due numeri dello stesso segno si ottiene un risultato di segno opposto. A 8 bit: $127 + 1 = 10000000 = -128$.

Esempio. In Python (-5) & 0xFF restituisce 251, cioè 0b11111011, la rappresentazione di $-5$ a $8$ bit.

In Python gli int hanno precisione arbitraria: niente overflow, 2**100 è esatto. In C gli interi hanno dimensione fissa (tipicamente int a 32 bit) e l'overflow sui tipi con segno è comportamento indefinito (vedi Tipi, operatori e controllo del flusso in CTipi interi e reali del C con dimensioni e limiti, conversioni implicite e cast, divisione intera, operatori di incremento, logici e bit a bit; if, switch, while, do-while, for, break e continue.Tipi, operatori e controllo del flusso in C →).

Numeri reali: virgola mobile (IEEE 754)

Definizione (virgola mobile IEEE 754). Un reale è rappresentato come $(-1)^s \cdot 1.m \cdot 2^{e - \text{bias}}$:

Formato	Bit totali	Segno $s$	Esponente $e$	Mantissa $m$	Cifre decimali circa
singola precisione (float in C)	32	1	8 (bias 127)	23	7
doppia precisione (float in Python, double in C)	64	1	11 (bias 1023)	52	15–16

Esempio. In Python 0.1 + 0.2 == 0.3 è False e 0.1 + 0.2 vale 0.30000000000000004.

Conseguenze:

• Solo i numeri della forma $k / 2^j$ sono esatti. $0.1$ in binario è periodico, quindi è approssimato.
• La precisione è relativa: la distanza tra due float consecutivi cresce con il valore.
• Valori speciali: inf, -inf, nan (risultato di operazioni indefinite; nan != nan).

0.1 + 0.2 == 0.3                  # False
0.1 + 0.2                         # 0.30000000000000004
import math
math.isclose(0.1 + 0.2, 0.3)      # True: confronto con tolleranza
1e308 * 10                        # inf

Proprietà (confronto di numeri in virgola mobile). Regola: mai confrontare float con ==; usare una tolleranza (math.isclose o abs(a - b) < eps).

Esempio. math.isclose(0.1 + 0.2, 0.3) restituisce True.

Caratteri e testo

Definizione (ASCII, Unicode e UTF-8)

• ASCII: 7 bit, 128 caratteri (lettere inglesi, cifre, punteggiatura, controllo). 'A' = 65, 'a' = 97, '0' = 48: le lettere e le cifre sono consecutive.
• Unicode: assegna un numero (code point) a ogni carattere di ogni lingua ('è' = U+00E8 = 232, '€' = U+20AC).
• UTF-8: codifica Unicode in 1–4 byte; i caratteri ASCII occupano 1 byte ed hanno lo stesso codice. È la codifica standard per i file di testo.

Esempio. ord("A") restituisce 65, chr(97) restituisce 'a' e len("è".encode("utf-8")) restituisce 2.

ord("A"), chr(97)                 # (65, 'a')
len("è"), len("è".encode("utf-8"))  # (1, 2): 1 carattere, 2 byte

In C un char è 1 byte e una stringa è un array di byte: una lettera accentata in UTF-8 occupa più char (vedi Array e stringhe in CArray di dimensione fissa in memoria contigua, inizializzazione, nessun controllo sugli indici, passaggio a funzioni con la lunghezza, matrici; stringhe come array di char terminati da '\0' e funzioni di string.h.Array e stringhe in C →).

Errori tipici

• Dimenticare che nel complemento a 2 l'intervallo è asimmetrico ($-128 \dots 127$, non $-127 \dots 128$).
• Usare == tra float o usare float per quantità che devono essere esatte (es. importi in centesimi: meglio interi).
• Confondere il numero di caratteri di una stringa con il numero di byte che occupa codificata.