Bases de numération, complément à 2, flottants et texte

Écrire un entier dans une base

Dans la vie courante, on écrit les nombres en base 10 : dix chiffres, et chaque chiffre vaut dix fois plus que celui de droite. Un ordinateur travaille avec deux états physiques (courant qui passe ou non) : il utilise la base 2, avec deux chiffres, 0 et 1, appelés bits.

En base 2, les « poids » des bits sont $1, 2, 4, 8, 16, 32, 64, 128\dots$ En base 16 (hexadécimal), on utilise seize symboles : $0$ à $9$ puis $\mathrm{A}=10$, $\mathrm{B}=11$, $\mathrm{C}=12$, $\mathrm{D}=13$, $\mathrm{E}=14$, $\mathrm{F}=15$.

Manipule les bits ci-dessous : chaque bit allumé ajoute son poids.

Pourquoi l'hexadécimal ? Parce que $16 = 2^4$ : un chiffre hexadécimal remplace exactement un groupe de 4 bits. C'est une écriture abrégée du binaire, bien plus lisible pour un humain. En Python, on écrit 0b10110101 pour le binaire et 0xB5 pour l'hexadécimal.

Combien de bits faut-il ?

Un octet (symbole o) regroupe 8 bits. Avec $n$ bits, on peut former $2^n$ combinaisons différentes. Si on les utilise pour écrire des entiers positifs (non signés), on représente tous les entiers de $0$ à $2^n - 1$.

Pourquoi ? Avec $n-1$ bits on atteint au plus $2^{n-1} - 1$ ; si $N$ est plus grand, il faut un bit de plus. Les tailles usuelles de registres et de variables sont 8, 16, 32 et 64 bits.

Les quantités de données se mesurent en octets, avec les préfixes du système international (puissances de 1 000) : $1\ \text{ko} = 1\,000\ \text{o}$, $1\ \text{Mo} = 10^6\ \text{o}$, $1\ \text{Go} = 10^9\ \text{o}$, $1\ \text{To} = 10^{12}\ \text{o}$. Les préfixes kio, Mio, Gio désignent des puissances de 1 024 ($1\ \text{kio} = 1\,024\ \text{o}$) ; on les rencontre moins souvent.

Les entiers relatifs : le complément à 2

Comment représenter $-5$ avec seulement des 0 et des 1 ? On pourrait réserver un bit pour le signe, mais l'addition deviendrait compliquée. La solution retenue par les machines est le complément à 2.

Sur $n$ bits, on partage les $2^n$ codes en deux moitiés : ceux qui commencent par 0 représentent les entiers positifs, ceux qui commencent par 1 les entiers négatifs.

Pourquoi ça marche ? Sur $n$ bits, les calculs se font « modulo $2^n$ » : on perd la retenue qui sort à gauche. Le code de $-x$ est celui de $2^n - x$, car $x + (2^n - x) = 2^n$ s'écrit $1\,0\dots0$ et la retenue finale disparaît, ce qui donne $0$. Or $2^n - x = (2^n - 1 - x) + 1$, et $2^n - 1 - x$ est précisément $x$ dont on a inversé les bits (le nombre $2^n - 1$ est formé uniquement de 1). Du coup, l'addition ordinaire fonctionne sans traitement particulier pour les entiers positifs comme négatifs.

Les nombres à virgule : les flottants

Comme pour les entiers, on peut écrire un nombre décimal en binaire. Après la virgule, les poids sont $\frac12, \frac14, \frac18, \dots$ c'est-à-dire $2^{-1}, 2^{-2}, 2^{-3}, \dots$

Pour convertir la partie après la virgule, on la multiplie par 2 de façon répétée : la partie entière obtenue à chaque étape est le bit suivant.

Certains nombres décimaux « simples » ont un développement binaire infini. C'est le cas de $0{,}1$ et de $0{,}2$. Or la mémoire est finie : la machine ne garde qu'un nombre limité de bits, donc une valeur approchée.

Un nombre flottant s'écrit sous la forme $(-1)^s \times 1{,}m \times 2^{e - \text{biais}}$, avec un bit de signe $s$, un exposant $e$ et une mantisse $m$ (les chiffres après la virgule). En double précision (le float de Python), il y a 64 bits : 1 de signe, 11 d'exposant et 52 de mantisse. Aucune norme précise n'est à connaître, mais le principe l'est.

Dans un format simplifié avec 3 bits d'exposant (biais 3) et 4 bits de mantisse, le nombre $(1\ 011\ 1000)_2$ se décode ainsi : $s = 1$ (négatif), $e = (011)_2 = 3$ donc $2^{3-3} = 1$, mantisse $1{,}1000_2 = 1{,}5$. Valeur : $-1{,}5$.

Entre $2^E$ et $2^{E+1}$, les flottants sont répartis régulièrement, mais chaque fois que l'exposant augmente de 1, l'écart entre deux flottants voisins double. Les flottants sont donc très serrés près de 0 et de plus en plus espacés quand on s'éloigne.

>>> 0.1 + 0.2

0.30000000000000004

>>> 0.1 + 0.2 == 0.3

False

>>> abs((0.1 + 0.2) - 0.3) < 1e-9

True

L'égalité est fausse parce que $0{,}1$, $0{,}2$ et $0{,}3$ sont stockés sous forme approchée, et les petites erreurs ne se compensent pas exactement. En revanche, $0{,}25 = (0{,}01)_2$ est stocké exactement.

Retour au début : le résultat de Lina vient donc de l'approximation de $0{,}1$ et de $0{,}2$, pas d'un bug de Python.

Représenter du texte

Un caractère est un nombre : on associe à chaque lettre, chiffre ou symbole un code. Il faut que l'émetteur et le récepteur utilisent le même encodage, sinon on obtient des « é » mal affichés dans un message.

En ASCII, 'B' a pour code $66 = (42)_{16}$. Les lettres se suivent : 'C' = 67, 'D' = 68… Une minuscule a un code qui dépasse de 32 celui de la majuscule correspondante. En Python : ord('B') renvoie 66 et chr(67) renvoie 'C'.

UTF-8 est un encodage à longueur variable : les 128 caractères ASCII restent sur 1 octet (un fichier ASCII est donc aussi un fichier UTF-8 valide), les lettres accentuées prennent 2 octets, des symboles comme € en prennent 3 et un émoji 4.

L'essentiel

• Base $b$ : un entier se décompose en puissances de $b$. En binaire, les poids sont $1, 2, 4, 8\dots$ ; un chiffre hexadécimal = 4 bits.

• Avec $n$ bits : $2^n$ valeurs, donc les entiers de $0$ à $2^n - 1$. Il faut $\lfloor \log_2 N \rfloor + 1$ bits pour écrire $N$ ; la somme de deux entiers de $n$ bits tient sur $n+1$ bits et leur produit sur $2n$ bits.

• Unités : $1\ \text{o} = 8$ bits ; ko, Mo, Go, To sont des puissances de 1 000.

• Complément à 2 sur $n$ bits : plage $[-2^{n-1} ; 2^{n-1} - 1]$ ; $-x$ s'obtient en inversant les bits de $x$ puis en ajoutant 1 ; l'addition se fait comme pour les entiers positifs, en oubliant la retenue finale. Attention au dépassement de capacité.

• Flottants : représentation approchée (signe, exposant, mantisse ; 1 + 11 + 52 bits en double précision). On ne teste jamais l'égalité de deux flottants avec ==.

• Texte : ASCII (7 bits), ISO 8859-1 (1 octet par caractère), UTF-8 (1 à 4 octets, compatible ASCII).

Retour au début : 0.1 + 0.2 != 0.3 parce que $0{,}1$ et $0{,}2$ n'ont pas d'écriture binaire finie.