Codage en complément à deux

On explique le codage utilisé sur un type "entier signé sur un octet" (on se limite à un octet afin de faciliter la manipulation, les entiers en jeu étant ainsi plus petits qu'avec 16 bits).

Combien?

Combien d'entiers peut-on coder sur 8 bits?

Combien

On dispose de 2⁸ = 256 codes différents.

Lesquels?

• Si sur ces 8 bits, on code uniquement les entiers positifs à partir de 0 (par leur écriture en base 2), quel est le plus grand entier codé?

réponse

On code les entiers de 0000 0000_deux = 0 à 1111 1111_deux = 255.

• Si on décide d'utiliser ces codes sur 8 bits pour coder les entiers d'un intervalle [ e_min; e_max] comportant autant d'entiers strictement négatifs que d'entiers positifs ou nuls, que valent e_min et e_max?

réponse

La moitié de $2^8$ est $2^7$. On code donc $2^7$ entiers strictement négatifs (de $-1$ à $-2^7$) et $2^7$ entiers positifs ou nuls (de $0$ à $2^7-1$).
Le plus petit sera -2⁷ = -128.
Le plus grand sera 2⁷ - 1 = 127.

Complément à M

Soit $M$ un nombre.

Pour un nombre $x$, on appelle complément à $M$ le nombre $y$ tel que $x+y = M$.

Exemple

Le complément à 16 de $x=5$ est $y=11$ car $5+11=16$.

Remarque

Le complément à $M$ de $x$ est bien entendu obtenu par l'opération $M-x$.

Complément à $2^8$

• Quels sont les entiers naturels dont l'écriture en base deux utilise 8 bits et qui commence par 1 ?

Solution

Le plus petit est 1000 0000_deux = 128.
Le plus grand est 1111 1111_deux = 255.

• Quels sont les compléments à $2^8$ des entiers précédents ?

Solution

Ce sont les entiers entre $2^8 - 255 = 1$ et $2^8 - 128 = 127$.

Important

Si l'on écrit tous ces entiers en binaire avec 8 bits, les écritures des entiers entre 1 et 127 commencent par un 0 (à gauche) et les entiers complémentaires à $2^8$ (compris entre 128 et 255) ont une écriture qui commence par un 1 (à gauche).

Coder les entiers relatifs en machine

Sur 8 bits, on va chercher à coder les entiers relatifs de $-128 = -2^7$ à $127 = 2^7-1$ (pour coder autant de négatifs que de positifs ou nul).

Le codage utilisé est en général le codage dit en complément à 2 sur 8 bits défini ci-dessous:

• les entiers naturels (entre 0 et 127) sont représentés par leur écriture binaire usuelle.
• les entiers négatifs (entre -128 et -1) sont représentés par le complément à $2^8$ de leur valeur absolue. En d'autres termes, pour un entier négatif $n$ (où $-128 \leqslant n \leqslant -1$), on utilise l'écriture en base deux de l'entier $2^8 - \left|n\right| = 2^8+n$.

Remarque

Avec ce choix (cf exercice précédent), les entiers positifs ou nul (entre 0 et 127) ont une écriture en complément à 2 sur 8 bits qui commencent (bit de gauche) par 0,
tandis que les négatifs (entiers entre -128 et -1) ont une écriture en complément à 2 sur 8 bits qui commencent (bit de gauche) par 1.

Exercice

• Donnez le code en complément à deux sur 8 bits de l'entier 75.
• Donnez le code en complément à deux sur 8 bits de l'entier -75.

75

L'entier 75 est représenté par son écriture binaire usuelle (obtenue par exemple par l'algorithme des divisions en cascade): 0100 1011.

-75

La valeur absolue de -75 est bien entendu 75. Le complément à $2^8$ de 75 est $2^8 - 75 = 181$. L'écriture binaire de 181 est 1011 0101.

La représentation en complément à deux sur 8 bits de $-75$ est donc 1011 0101.