Bits, octets et encodage des entiers
En classe de première générale, un attendu du programme de NSI est la représentation binaire des entiers, naturels et relatifs. Ainsi, vous savez ce qui se passe sous le capot lorsque vous définissez un entier avec l’instruction int en codant avec Python.
Nous survolerons d’abord quelques notions puis, après un détour par la base 2, nous évoquerons le concept de boutisme avant de parvenir au but du voyage : la représentation binaire des entiers relatifs (vous pourrez cependant poursuivre l'aventure avec la représentation binaire des réels non entiers).
Bits
Rappelons d’abord ce qu’est un bit. Souvent, ce terme a été vu en seconde.
Le mot est né de la locution anglaise binary digit. Un bit est l’unité élémentaire d’information. Il prend la valeur 0 ou 1. Pourquoi ?
Les machines échangent grâce à une succession de signaux pour lesquels il n’existe que deux possibilités : soit le courant passe soit il ne passe pas, soit il y a une lumière soit non, etc.
En logique, on emploierait plutôt la distinction vrai ou faux. Pas très pratique à manipuler. Or, la logique trouve sa formulation mathématique dans l’algèbre de Boole qui est celle des 0 et des 1. C'est ainsi que les nombres et les caractères sont encodés. Et vous vous rendrez vite compte que cette « grammaire » permet des possibilités incroyables (par exemple le fait que cette page existe et que vous la lisez sur un écran).
Octets
Les bits sont regroupés par huit. Ce sont les octets (ou bytes, en anglais). Un exemple d’octet est 01100101. Comme il n’y a que deux bits possibles, il en existe \(2^8 = 256\) différents. Un octet permet donc d'encoder tous les entiers de 0 à 255. Avec deux octets, on passe à \(2^{16} = 32\,768\) entiers.
Un kilo-octet (ko) vaut 1 000 octets, un mégaoctet (Mo) vaut 1 000 kilo-octets, un gigaoctet (Go) vaut 1 000 mégaoctets, un téraoctet (To) vaut 1 000 gigaoctets, un pétaoctet (Po) vaut 1 000 téraoctets.
Un mot machine est un regroupement d’octets, généralement quatre ou huit. C’est l’unité de base d’un microprocesseur : s’il sait traiter l’information sur 64 bits, c’est qu’il utilise des regroupements de huit octets (\(8 \times 8 = 64\)).
Grâce à eux, il est possible de manipuler des nombres entiers et des approximations de réels non entiers.
Base 2
L’encodage le plus évident consiste à traduire un nombre de la base 10 à la base 2. La page sur les bases montre quels calculs manuels et quelles fonctions de Python permettent de le faire.
Par exemple, comment s’écrit 1 000 (base 10) en base 2 ?
Étudions les puissances de 2 contenues dans ce nombre. Il y a une fois 512, c’est-à-dire \(2^9\), plus une fois \(2^8\) (256) ce qui nous fait 768. Il reste 232 à décomposer. Il y a une fois \(2^7\) (128), reste 104 donc une fois 64 (soit \(2^6\)), reste 40 donc une fois 32 (soit \(2^5\)), reste 8 donc zéro fois \(2^4\) et une fois \(2^3.\) L’opération étant terminée, il n’y a ni \(2^2\) ni \(2^1\) ni \(2^0.\) D'ailleurs, comme \(2^0 = 1,\) la traduction d’un nombre impair en base 2 se termine toujours par 1 mais ce n’est pas le cas ici. Si vous traduisez un nombre en base 2 et qu’à un moment vous trouvez deux fois la même puissance de 2, refaites votre calcul !
Par conséquent, on obtient 1111101000.
Vérification avec Python :
print bin(1000)
On obtient :
0b1111101000
Boutisme
Dans l’architecture d’une machine, les octets peuvent être organisés de deux façons (principalement) : en gros boutisme ou en petit boutisme.
L’origine de ce mot se trouve dans les Voyages de Gulliver de J. Swift (illustration ci-dessous : Gulliver se relève et tous les nains sont culbutés).
En gros boutisme, l’octet le plus important se trouve à l’adresse la plus petite. Par exemple, sur 32 bits, 1A236CC0 (en hexadécimal) se présente ainsi :
| 1A | 23 | 6C | C0 |
Au contraire, en petit boutisme la séquence est la suivante :
| C0 | 6C | 23 | 1A |
On peut employer l’image suivante : en japonais, le format de date est AAAA/MM/JJ, écriture gros-boutiste puisque le paramètre le plus important est l’année, suivie du mois puis du jour. En Europe, l’ordre est petit-boutiste : JJ/MM/AAAA.
À moins de devoir lire des fichiers binaires, vous n’aurez probablement rien à faire de cette distinction dans votre vie professionnelle.
Entiers relatifs
Comment encoder un entier négatif en s'appuyant sur la base 2 ? L’idée de départ est que le bit de poids le plus fort, c’est-à-dire le premier, donne le signe : 0 pour positif et 1 pour négatif.
Hélas, cette convention pose quelques soucis.
- Le nombre 0 peut être représenté de deux façons.
- L’addition d’un nombre positif et d’un nombre négatif donne un résultat faux.
D’où l’idée de recourir à une astucieuse forme d’encodage, le complément à deux.
Avec cette technique, l’encodage ne change pas pour les positifs (ceux qui commencent par 0). Pour les autres, toutes les valeurs servant à encoder sont inversées, la retenue finale étant ignorée, et on ajoute 1.
Prenons quelques exemples.
Supposons un encodage sur 4 bits. Zéro devient 0000. Les valeurs inversées donnent 1111. Ajoutons 1. Ceci nous donne 10000. Le 1 qui se trouve en première position est la retenue qui, contrairement à ce que laisse présager son nom, n’est pas retenue (vous suivez ?).
Nous avons bien \(-0 = 0\) si vous nous permettez cette écriture bizarre.
Autre exemple. Comment écrire \(-3\) avec 4 bits dont le premier indique le signe ?
En base 2 et avec 3 bits, 3 s’écrit 011. Donc les valeurs inversées donnent 100. On ajoute 1 pour obtenir 101.
Facile, il n’y a pas de retenue. On ajoute le bit de signe 1 et l’on obtient 1101.
Et comment écrire \(-74\) avec le complément à 2 en n'utilisant qu'un octet ?
\(74 = 2^6 + 2^3 + 2^1\) donc en base 2 sur 7 bits, ce nombre s’écrit 1001010. Inversons pour obtenir 0110101. Ajoutons 1 et il devient 0110110 (il y a une retenue), plus le bit de signe, soit 10110110.
À présent, vous pouvez vous atteler au premier exercice d'encodage des nombres...
