Aller au contenu

03 Cours Représentation entiers relatifs

Représentation d’un entier naturel⚓︎

Un entier naturel est un nombre entier positif ou nul. Le choix à faire (c’est-à-dire le nombre de bits à utiliser) dépend de la fourchette des nombres que l’on désire utiliser. Pour coder des nombres entiers naturels compris entre \(0\) et \(255\), il nous suffira de \(8\) bits (un octet) car \(2^8 = 256\). D’une manière générale un codage sur \(n\) bits pourra permettre de représenter des nombres entiers naturels compris entre \(0\) et \(2^{n}-1\).

Exemples :⚓︎

\(9 = 00000101_2\), \(128 = 10000000_2\), etc.

Représentation d’un entier relatif⚓︎

Un entier relatif est un entier pouvant être positif ou négatif. Il faut donc coder le nombre de telle façon que l’on puisse savoir s’il s’agit d’un nombre positif ou d’un nombre négatif.

Avec un codage sur \(n\) bits, on peut coder \(2^n\) nombres différents, la moitié d'entre eux positifs (dont \(0\)), l'autre moitié négatifs. On pourra donc coder les nombres de \(-2^{n-1}\) à \(2^{n-1} - 1\).

  • Sur \(8\) bits (\(1\) octet), l’intervalle de codage est \([-128~; 127]\).
  • Sur \(16\) bits (\(2\) octets), l’intervalle de codage est \([-32768~; 32767]\).
  • Sur \(32\) bits (\(4\) octets), l’intervalle de codage est \([-2147483648~; 2147483647]\).

Une première (fausse bonne) idée est d'ajouter un bit devant le codage du nombre qui marque le signe \(+\) ou le signe \(-\). Dans ce cas, le nombre relatif tel qu'il est écrit ressemble à un entier positif.
Il serait plus simple pour l'ordinateur si l'addition des relatifs utilisaient simplement l'addition des entiers écrits en binaire. Or ce n'est pas le cas avec cette technique.

Exemple :⚓︎

Imaginons que l'on code des nombres relatifs sur \(8\) bits, en considérant que le \(1^{\text{er}}\) bit est un \(1\) pour \(+\) ou un \(0\) pour \(-\).
On a alors \(8_{10} = 10001000_2\) et \(-8_{10} = 00001000_2\).
Alors, avec les règles arithmétiques usuelles :
\(10001000_2 + 00001000_2 = 10010000_{2}\)
Ce qui donnerait : \(8 + (-8) = 16\), ce qui est évidemment faux.
Notons que cela n'aurait pas mieux fonctionné en prenant \(0\) pour \(+\) et \(1\) pour \(-\).

Pour respecter l'addition : le binaire signé⚓︎

Afin que les règles d’addition soient conservées, une astuce a été trouvée : utiliser un codage que l’on appelle complément à deux. Cette représentation permet d’effectuer les opérations arithmétiques usuelles naturellement.

Comment coder ?

  • Un entier relatif positif ou nul sera représenté en binaire (base \(2\)) comme un entier naturel. On remarque que, comme le nombre positif est au maximum \(2^{n-1} - 1\), le \(1^{\text{er}}\) bit (dit le bit de poids fort), qui représente \(2^n\), sera forcément \(0\) pour tous les nombres positifs.

  • Un entier relatif négatif sera représenté grâce au codage en complément à deux.
    On va coder les nombres de manière cyclique, comme si on avait \(2^n = 0\).
    Tout nombre négatif \(x\) sera codé comme le nombre positif \(2^n + x\).
    Tout nombre qui représente en binaire un entier \(p\) supérieur à \(2^{n-1} - 1\), sera en fait le codage de \(p - 2^n\).

Exemple d'un codage sur \(4\) bits de nombres de \(-8\) à \(7\) :⚓︎

On a : \(0000\) représente \(0\)
\(0001\) représente \(1\)
\(0010\) représente \(2\)
\(0011\) représente \(3\)
\(0100\) représente \(4\)
\(0101\) représente \(5\)
\(0110\) représente \(6\)
\(0111\) représente \(7\)
ensuite :
\(1000\) représente \(-8 = 8 - 16\)
\(1001\) représente \(-7 = 9 - 16\)
\(1010\) représente \(-6 = 10 - 16\)
\(1011\) représente \(-5 = 11 - 16\)
\(1100\) représente \(-4 = 12 - 16\)
\(1101\) représente \(-3 = 13 - 16\)
\(1110\) représente \(-2 = 14 - 16\)
\(1111\) représente \(-1 = 15 - 16\)

Et on vérifie que : \(6 + (-8)\) est codé par \(0110 + 1000\).
L'ordinateur effectue cette somme binaire qui vaut : \(1110\). Cela représente bien le résultat souhaité : \(-2\).

Comment obtenir le complément à deux⚓︎

  1. Pour un nombre négatif, écrire d'abord la valeur absolue du nombre en base \(2\). Le bit de poids fort doit être égal à \(0\).
  2. Inverser les bits : les \(0\) deviennent des \(1\) et vice versa. On fait ce qu’on appelle le complément à un.
  3. On ajoute \(1\) au résultat (les dépassements sont ignorés).

Explication :

  1. correspond à coder \(|x|\) ;
  2. correspond à faire \(1111\text{...}1111\) - \(|x|\), ce qui vaut \(2^n - 1 - |x|\) ;
  3. correspond à ajouter \(1\) à ce qui précède. On a donc codé \(2^n - |x|\).

Exemple :⚓︎

On désire coder la valeur \(-19\) sur 8 bits. Il suffit :

  1. d’écrire \(19\) en binaire : \(00010011\)
  2. d’écrire son complément à \(1\) : \(11101100\)
  3. et d’ajouter \(1\) : \(11101101\)

La représentation binaire de \(-19\) sur 8 bits est donc \(11101101\).

On remarquera qu’en additionnant un nombre et son complément à deux on obtient 0. En effet, \(00010011 + 11101101 = 00000000\) (avec une retenue de 1 qui est éliminée).

Truc :⚓︎

Pour transformer de tête un nombre binaire en son complément à deux, on parcourt le nombre de droite à gauche en laissant inchangés les bits jusqu’au premier 1 (compris), puis on inverse tous les bits suivants. Prenons comme exemple le nombre \(20~\): \(00010100\).

  1. On garde la partie à droite telle quelle : \(00010100\)
  2. On inverse la partie de gauche après le premier un : \(11101100\)
  3. Et voici \(-20~\): \(11101100\)

Et pour convertir du binaire signé vers l'écriture décimale ?⚓︎

  1. Il faut impérativement le nombre \(n\) de bits sur lesquels le nombre est codé.
  2. Convertir l'écriture binaire en écriture décimale : notons \(p\) ce nombre.
  3. Si \(p < 2^{n-1}\) : très bien, le nombre codé était positif, c'est \(p\).
    Si \(p \geq 2^{n-1}\) : le nombre codé était négatif, et il vaut \(p - 2^n\).

Point de vigilance :⚓︎

Il faut toujours se rappeler sur combien de bits sont codés les nombres, et dans quel intervalle ils doivent être !
Reprenons l'exemple du codage sur \(4\) bits illustrés par la droite graduée plus haut.
Les nombres codés doivent être entre \(-8\) et \(7\).
Si je l'oublie et que j'essaie de calculer \(7 + 7\), j'obtiens : \(0111 + 0111\), qui est égal à \(1110\). Ce codage représente \(-2\) ! Ce qui est faux.
Mais on aurait dû l'anticiper car \(7 + 7 = 14\) ne peut pas être codé comme un nombre relatif sur \(4\).

Anecdote :⚓︎

Le 4 juin 1996, une fusée Ariane 5 a explosé 40 secondes après l’allumage. La fusée et son chargement avaient coûté 500 millions de dollars. La commission d’enquête a rendu son rapport au bout de deux semaines. Il s’agissait d’une erreur de programmation dans le système inertiel de référence. À un moment donné, un nombre codé en virgule flottante sur 64 bits (qui représentait la vitesse horizontale de la fusée par rapport à la plate-forme de tir) était converti en un entier sur 16 bits. Malheureusement, le nombre en question était plus grand que 32767 (le plus grand entier que l’on peut coder sur 16 bits) et la conversion a été incorrecte.

Exercice⚓︎

  1. Coder les entiers relatifs suivants sur 8 bits (16 si nécessaire) : \(456\), \(-1\), \(-56\), \(-5642\).
  2. Que valent, en base dix, les trois entiers relatifs suivants :
    • \(01101100_2\)
    • \(11101101_2\)
    • \(1010101010101010_2\) ?
Solution

Pour coder les entiers relatifs en binaire en complément à 2, on rappelle la méthode :
\(\bullet\) Si c'est un nombre positif, on le code en binaire, on s'assure que le premier chiffre est un zéro (sinon, c'est qu'on a un nombre trop grand, qui n'est pas dans le bon intervalle), et c'est terminé.
\(\bullet\) Si c'est un nombre négatif :
1. écrire sa valeur absolue (le nombre positif) en binaire
2. écrire son complément à \(1\)
3. ajouter \(1\)

\(\bullet\) \(456\) : \(456\) est positif, donc on code directement le nombre \(456\) sur \(16\) bits car \(8\) sont insuffisants.
\(456 = 256 + 128 + 64 + 8 = 2^8 + 2^7 + 2^6 + 2^3\), donc \(456_{10} = 0000~0001~1100~1000\)
\(\bullet\) \(-1\) : \(-1\) est négatif.
\(1_{10} = 0000~0001_{2}\)
complément à \(1\) : \(1111~1110\)
on ajoute \(1\) : \(1111~1111\) (\(-1\) est en effet représenté en complément à \(2\) comme le nombre entier \(2^8 - 1\) en binaire, donc le plus "grand" possible (que des \(1\))
\(\bullet\) \(-56\) : \(-56\) est négatif.
\(56 = 32 + 16 + 8 = 2^5 + 2^4 + 2^3\) donc \(56_{10} = 0011~1000_{2}\)
complément à \(1\) : \(1100~0111\)
on ajoute \(1\) : \(1100~1000\)
\(\bullet\) \(-5642\) : \(-5642\) est négatif, on le code sur \(16\) bits car \(8\) seront insuffisants.
\(5642 = 4096 + 1024 + 512 + 8 + 2 = 2^{12} + 2^{10} + 2^9 + 2^3 + 2^1\) donc \(5642_{10} = 0001~0110~0000~1010_{2}\)
complément à \(1\) : \(1110~1001~1111~0101\)
on ajoute \(1\) : \(1110~1001~1111~0110\)

\(\bullet\) \(01101100_2\) : il commence par \(0\), c'est un nombre positif !
\(01101100_2\) vaut, en décimal : \(2^2 + 2^3 + 2^5 + 2^6 = 4 + 8 + 32 + 64 = 108\)
\(\bullet\) \(11101101_2\) : il commence par \(1\), c'est un nombre négatif !
\(11101101_2\) vaut en décimal : \(2^0 + 2^2 + 2^3 + 2^5 + 2^6 + 2^7 - 2^8 = 1 + 4 + 8 + 32 + 64 + 128 - 256 = -19\)
\(\bullet\) \(1010101010101010_2\) : il commence par \(1\), c'est un nombre négatif !
\(1010101010101010_2\) vaut en décimal : \(2^1 + 2^3 + 2^5 + 2^7 + 2^9 + 2^{11} + 2^{13} + 2^{15} - 2^{16} = 2 + 8 + 32 + 128 + 512 + 2048 + 8192 + 32768 - 65538 = -21~846\)