Cours : Une machine à calculer : l'octet

Du bit à l’octet

Rappel

On appelle bit une unité d’information binaire ($0$ ou $1$). Dans le système binaire, un nombre entier est codé avec des bits.

Taille d’un entier

Dans le système décimal, avec $x$ chiffres, on peut représenter $10^x$ nombres différents. Par exemple, avec 4 chiffres, on peut représenter $10^{4}=10\,000$ nombres (de $0000$ à $9999$).

Propriété

Avec $x$ bits, on peut représenter $2^x$ nombres différents.

Avec $4$ bits par exemple, on peut donc représenter $2^4$, soit 16 nombres (de $0000$ à $1111$, qui signifie 15 en binaire).

Définition

Taille d’entier :

En informatique, la taille d’un entier est le nombre de bits avec lequel celui-ci est codé.

Selon le système informatique ou le programmeur, on choisira de coder une donnée de type entier avec un nombre $n$ fixé de bits. Ce nombre de bits limite donc la valeur que peut prendre la donnée à un maximum qui correspondra à $2^{n}-1$.

Exemple

Par exemple, si l’on choisit de coder une donnée de type entier sur $4$ bits, celle-ci pourra prendre la valeur $3$, car $3$ peut être codé en binaire avec $4$ bits $(0011)$.

En revanche, cette même donnée ne pourra pas prendre une valeur strictement supérieure à $15$, car les entiers au-delà de cette limite nécessitent plus de $4$ bits pour être codés en binaire. En effet, $15$ est codé sur $4$ bits $(1111)$, $16$ (codé $10000$) et les nombres supérieurs le sont sur $5$ bits ou plus.

Propriété

Pour évaluer le nombre de bits nécessaires pour coder un entier, on cherche la plus petite puissance de deux dont la valeur est strictement supérieure à cet entier (voir le cours précédent pour la représentation d’un entier en binaire).

Exemple

Le nombre $614$ est plus grand que $2^{9} = 512$ et plus petit que $2^{10} = 1024$.
Il faudra donc au moins $10$ bits pour coder ce nombre.

En effet, son codage en binaire est $10\,0110\,0110$.

À retenir

Dans un système informatique donné, les entiers sont souvent codés avec une taille standard (souvent $8$, $16$, $32$ ou $64$ bits). Plus cette taille sera grande, plus les calculs pourront être précis, mais ils nécessiteront aussi plus de ressources (que ce soit tant en ressource de calcul, en espace mémoire qu’en stockage disque).

Octet

La taille d’un entier peut être exprimée en bits, mais il est bien plus courant de l’exprimer en octets.

Définition

Octet :

Un octet est un groupe de $8$ bits. Le mot vient de la racine latine octo qui veut dire $8$.

On peut représenter $256$ entiers avec un octet (de $0$ à $255$). Les tailles d’entiers standards ($8$, $16$, $32$ ou $64$ bits) correspondent respectivement à $1$, $2$, $3$ ou $4$ octets.

À retenir

L’octet est l’unité de mesure la plus utilisée pour la taille d’une information (pas seulement d’un entier).
Ainsi, on mesure souvent la taille d’un fichier en kibioctets $(\text{Kio})$, mébioctets $(\text{Mio})$ ou gibioctets $(\text{Gio})$. De même, le débit d’une transmission d’informations peut être mesuré en $\text{Kio}$, $\text{Mio}$ ou $\text{Gio}$ par seconde : $\text{Kio}\cdot\text{s}^{-1}$, $\text{Mio}\cdot\text{s}^{-1}$, $\text{Gio}\cdot\text{s}^{-1}$.

Rappel

$\text{Ki}$ correspond à $10^{10}$
$\text{Mi}$ à $10^{20}$
$\text{Gi}$ à $10^{30}$
$\text{Ti}$ à $10^{40}$

Le système hexadécimal

Définition

Système hexadécimal :

Le système hexadécimal est un système de numération en base $16$, c’est-à-dire qu’il utilise 16 chiffres pour représenter les entiers, de $0$ à $9$ puis de $\text{A}$ à $\text{F}$.

Nous avons donc les correspondances suivantes :

• On note parfois la base d’un nombre en indice après celui-ci, tels que $\text{nombre}_s$.

Ainsi, $10_2$ est un nombre codé en binaire, $10_{10}$ un nombre codé en décimal, et $10_{16}$ un nombre codé en hexadécimal.
Il existe une autre notation : pour signifier qu’un nombre est exprimé avec le système hexadécimal, on lui accole le préfixe $0\text{x}$ (c’est la lettre « $\text{x}$ » et non un signe de multiplication). Le préfixe $0\text{b}$ indique que le nombre est exprimé avec le système binaire.

L’intérêt du système hexadécimal, pour un informaticien, est qu’il possède la propriété suivante :

Propriété

On peut représenter les nombres de $0$ à $15$ avec un caractère en hexadécimal, soit autant qu’avec quatre bits en binaire.
Autrement dit, on peut représenter un octet avec deux caractères hexadécimaux. Ainsi, l’écriture d’un nombre en hexadécimal peut se voir comme une écriture condensée du binaire, puisque l’on utilise deux caractères hexadécimaux pour représenter un octet qui tient sur $8$ bits, soit 4 fois plus de caractères

Pour passer le codage d’un entier du binaire à l’hexadécimal, il suffit de remplacer chaque groupe de $4$ bits par le caractère correspondant, et vice-versa. Pour passer du décimal à l’hexadécimal ou l’inverse, le plus simple est encore de passer par le binaire, même s’il y existe d’autres méthodes.

Exemple

Prenons le nombre $42_{10}$, c’est-à-dire $0010\,1010_2$.
Puisque $0010_{2}=2=0\text{x}2$
et $1010_{2}=10=0\text{xA}$
alors $0010\,1010_{2}=0\text{x}2\text{A}$.

Le tableau suivant donne une correspondance entre plusieurs systèmes de numération pour différents entiers :

Entiers relatifs

La plupart des systèmes informatiques qui codent des entiers le font sous forme d’entiers relatifs, il faut donc un moyen de représenter le signe (positif ou négatif) des entiers.

Représentation naïve

Définition

Bit de signe :

Dans le codage d’un entier relatif, le bit de signe est un bit qui vaut $0$ si l’entier est positif ou $1$ s’il est négatif.

On pourrait coder un entier relatif comme un entier naturel, mais avec un bit qui indiquerait son signe. Par exemple, le bit le plus à gauche, qu’on appelle aussi bit de poids le plus fort, alors que le bit le plus à droite est appellé le bit de poids le plus faible.

Par exemple, on aurait $0000\,0001$ qui vaudrait $1$ et $1000\,0001$ qui vaudrait $-1$. C’est quelque chose qui est rarement fait, et ce, pour deux raisons principales :

• D’abord, parce que le $0$ aurait deux représentations : $0000\,0000$ vaudrait $+0$ et $1000\,0000$ vaudrait $-0$. Ce n’est pas très grave, mais c’est peu élégant.
• Surtout, parce qu’il est difficile de trouver des algorithmes simples pour additionner ou soustraire des nombres représentés ainsi. Or, c’est ce que l’on va principalement demander à l’ordinateur de faire avec ces nombres.
• Voilà pourquoi on utilise plutôt une autre représentation, que l’on appelle complément à deux.

Le complément à deux

Définition

Complément à un :

Le complément ou complément à un d’un nombre binaire est le nombre obtenu en remplaçant chaque $0$ par un $1$ et chaque $1$ par un $0$.

Exemple

• Le complément à un de $1011$ est $0100$.
• Le complément à un de $0110$ est $1001$.

Définition

Complément à deux :

Le complément à deux d’un nombre binaire est le nombre obtenu en prenant son complément et en lui ajoutant $1$.

Exemple

• Le complément à deux de $1011$ est $0101$ : le complément à un de $1011$ est $0100$ et $0100$ auquel on ajoute $1$ donne $0101$.
• Le complément à deux de $0110$ est $1010$ : le complément à un de $0110$ est $1001$ et $1001$ auquel on ajoute $1$ donne $1010$.

La plupart des systèmes d’information modernes codent les nombres entiers relatifs avec le système du complément à deux, où l’opposé d’un nombre est codé par son complément à deux.

• Dans ce système, le bit le plus à gauche est toujours le bit de signe.

Exemple

Dans un système de complément à deux à $4$ bits, on a :

$0000$	$0$	$\ $	$\ $
$0001$	$1$	$1111$	$-1$
$0010$	$2$	$1110$	$-2$
$0011$	$3$	$1101$	$-3$
$0100$	$4$	$1100$	$-4$
$0101$	$5$	$1011$	$-5$
$0110$	$6$	$1010$	$-6$
$0111$	$7$	$1001$	$-7$
$\ $	$\ $	$1000$	$-8$

On peut constater que le bit de gauche vaut $0$ dans la codification des entiers positifs, tandis qu’il vaut $1$ dans celle des entiers négatifs.

Dans un système de complément à deux, l’addition et la soustraction fonctionnent de la même manière que pour l’addition d’entiers naturels, à la seule différence qu’il faut ignorer l’éventuel dépassement dû à la dernière retenue.

Exemple

On voit dans le tableau précédent que, par exemple,

• $1100 + 0011 = 1111$ (soit $-4 + 3 = -1$).
• $1101 + 0101 = 1\,0010$, ce qui donne $0010$ en ignorant le dépassement (soit $-3 + 5 = 2$).

Dans un système de complément à deux, un entier relatif codé sur $n$ bits peut valoir entre $2^{n-1}-1$ et $-2^{n-1}$. Voir le tableau suivant :

Des entiers trop grands

Taille du résultat d’une opération

On peut estimer la taille du résultat d’une opération sur les entiers.

Propriété

Soit deux entiers naturels dont l’expression en binaire nécessite au plus $n$ bits et $m$ bits (respectivement).

• La somme de ces entiers nécessite pour son expression binaire au plus $\text{max}(n, m) + 1$ bits.
• Le produit de ces entiers nécessite pour son expression binaire au plus $n+m$ bits.

Démonstration

• Pour la somme, on peut l’observer comme une conséquence de la manière dont les additions sont posées : le nombre de « colonnes » est égal au nombre de bits du nombre additionné le plus grand, et une colonne supplémentaire est nécessaire s’il y a une retenue sur la dernière colonne.
• Pour le produit, on peut aussi l’observer comme une conséquence de la manière dont sont posées les multiplications.

Cette propriété n’est en réalité pas spécifique au système binaire : elle est vraie pour les additions et les multiplications dans n’importe quel système de numération.

Dépassement d’entier

Définition

Dépassement d’entier :

On appelle dépassement d’entier (integer overflow) l’erreur informatique qui se produit quand le résultat d’un calcul est un entier trop grand pour la taille qui lui a été attribuée. Le système informatique est alors incapable d’écrire le résultat correctement.

On a vu que les valeurs prises par une donnée entière codée selon $8$, $16$, $32$ ou $64$ bits ne pouvait pas dépasser une limite inférieure, ni une limité supérieure. Ainsi, si le résultat d’un calcul venait à dépasser l’une de ces limites, celui-ci ne pourrait pas être codé par le calculateur. Selon le système informatique, un dépassement d’entier peut être plus ou moins grave : un programme bien conçu peut prévoir cette possibilité et établir une marche à suivre si un tel cas ce produit. Parfois, les limites techniques du calculateur font du dépassement d’entier un problème critique.

Exemple

Il est possible de provoquer un dépassement d’entier sur une calculatrice ordinaire : si on lui demande de réaliser un calcul dont le résultat trop grand est impossible à coder, elle affiche un message d’erreur.

Bien que le dépassement d’entier soit une erreur informatique très connue et courante, il est déjà arrivé que des erreurs de conception mènent à de véritables catastrophes à la suite de dépassements d’entier.

Exemple

L’échec du vol inaugural du lanceur d’engin spatial européen Ariane $\text{V}$, en 1996, est l’exemple le plus célèbre. Le système de guidage électronique, très fiable sur les précédents lanceurs, n’avait pas été re-testé. Mais il n’avait pas été prévu pour calculer des vitesses aussi grandes que celles de cette nouvelle fusée. Un dépassement d’entier a provoqué un dysfonctionnement : le système « corrigea » la trajectoire de la fusée en lui faisant prendre un virage de 90°, la mettant à l’horizontale ; elle commença à se désagréger. Le mécanisme d’autodestruction se déclencha alors, et la fusée explosa au-dessus de la base spatiale de Kourou.

Entiers de taille arbitraire

Pour permettre des calculs sur les valeurs élevées, les langages de programmation proposent souvent des types d’entier spécifiques.

Définition

Entier de taille arbitraire :

Un entier de taille arbitraire est un entier dont la taille n’est pas fixée dans le système d’information pouvant évoluer jusqu’aux limites physiques du système informatique.

Exemple

Dans le langage Python, un entier peut être défini comme de type integer (int) ou long integer (long).

• Les integer sont codés sur $4$ octets (soit $32$ bits) avec le système de complément à deux ; il est donc possible qu’un dépassement d’entier ait lieu si on essaye de leur affecter une trop grande valeur.
• Les long integer sont de taille arbitraire : Python peut leur attribuer une taille virtuellement infinie (pour peu que l’espace de stockage physique soit suffisant).

Sachant que manipuler un long integer est plus coûteux en temps et en ressources que de manipuler un integer, la plupart du temps, les programmeurs utilisent le type int lorsqu’ils savent que l’entier en question ne dépassera pas une certaine valeur.