Représentation des entiers relatifs

Il est naturel et intéressant de se demander comment un ordinateur peut représenter les entiers relatifs. Le langage python gère bien entendu les entiers relatifs, qui sont représentés à l'écran comme on peut s’y attendre:

>>> answer = 42
>>> -answer
-42

Cependant, nous savons bien à présent que l’affichage en base 10 n’est qu’une représentation pour nous autres humains. Qu’en est-il en interne ?

Une première tentative consiste à utiliser la fonction `bin` sur un entier négatif:

>>> bin(23)
'0b10111'
>>> bin(-23)
'-0b10111'

Il semblerait donc que python se contente de préfixer l’entier par un signe de négation, comme en mathématiques. Mais cela est-il vraiment la représentation interne du nombre ? N’est-ce pas plutôt encore une facilité d’affichage ?

Comment représenter le signe moins ? Un premier essai

Nous avons admis le postulat de base que, dans la mémoire de l’ordinateur, tout doit être représenté sous forme de bits. Un signe moins n’est pas un bit, mais on peut peut-être imaginer une méthode permettant un encodage du signe moins: après tout, soit un nombre est positif, soit il est négatif: il n’y a que deux états possibles, on peut donc utiliser un bit pour cela.

Prenons le cas d’un octet. On peut convenir que le premier bit (c’est-à-dire le bit de poids fort, le plus à gauche) sert à représenter le signe du nombre:

  • Un bit de poids fort à `0` signifie que le nombre est positif;
  • Un bit de poids fort à `1` signifie que le nombre est négatif.

Ainsi, le nombre \(23\) s'écrirait toujours \(00010111_2\), alors que \(-23\) deviendrait \(10010111_2\).

Quels sont les inconvénients de cette méthode:

  • On perd un bit sur les 8 pour la représentation du signe. Il ne reste donc plus que 128 nombres représentables, mais avec deux signes possibles: on peut donc aller de -127 à 127 sur un octet; Cet inconvénient est absolument impossible à supprimer, quelle que soit la méthode employée, car il faut nécessairement utiliser au moins un bit pour représenter le signe;
  • Le point précédent amène à une possible incohérence: il y a 128 nombres entre 0 et 127, plus les 127 nombres négatifs entre -127 et -1, ce qui ne fait que 255 valeurs distinctes. Or, il est possible d’encoder 256 valeurs sur 8 bits. Où est passée la dernière ?
  • Ce paradoxe apparent s'éclaircit lorsqu’on s’aperçoit que le nombre 0 a à présent deux représentations binaires distinctes: \(00000000_2\) et \(10000000_2\). On a donc à nouveau 256 valeurs, mais elles ne sont pas toutes distinctes. Et cela n’a pas vraiment de sens mathématiquement parlant;

Ces inconvénients sont bien réels, mais ce n’est pas le plus grave. Pour comprendre pourquoi la méthode proposée ici n’est pas intéressante, il faut s’intéresser à la manière dont un ordinateur additionne des nombres en binaire.

Addition en binaire

Nous verrons dans un cours futur qu’un microprocesseur possède notamment une partie de ces circuits dédiée aux additions binaires. En attendant, retenons simplement que l’addition binaire est une des opérations les plus élémentaire que peut effectuer un microprocesseur, quel qu’il soit.

Comment additionne-t-on deux nombres en binaire ? Exactement comme en décimal (avec la méthode apprise à l'école élémentaire), à la seule différence qu’il n’y a que deux chiffres. Seules 4 combinaisons peuvent apparaître:

Bit A Bit B Somme Retenue
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Mais en réalité, il faut aussi tenir compte d’une éventuelle retenue précédente, ce qui double le nombre de cas:

Bit A Bit B Retenue précédente Somme Retenue
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 1

Calculons en exemple la somme 108 + 23. Les représentations binaires de ces deux nombres sur un octet sont 01101100 et 00010111 respectivement.

\begin{array}[t]{r} \tt \overset{1}{0}\overset{1}{1}\overset{1}{1}\overset{1}{0},\overset{1}{1}100 \\\
\tt 0001,0111 \\\
\hline \tt 1000,0011 \end{array}

On peut constater qu’il y a beaucoup plus de retenues qu’en décimal. On conviendra que, s’il y avait eue une retenue sur le bit de poids fort, alors on l’aurait abandonnée: on dit que cette addition se fait sans dépassement (les microprocesseur offrent tous un moyen de savoir si cette dernière retenue a existé ou non, car dans certains cas c’est important de pouvoir le savoir afin de réagir le cas échéant).

À présent que nous savons additionner, nous souhaitons que l’addition soit compatible avec notre représentation des nombres relatifs. Cela est-il bien le cas ?

Effectuons l’addition de 23 et de -23 avec les représentations binaires associées:

\begin{array}[t]{r} \tt 00\overset{1}{0}1,\overset{1}{0}\overset{1}{1}\overset{1}{1}1 \\\
\tt 1001,0111 \\\
\hline \tt 1010,1110 \end{array}

On trouve le nombre \(1010,1110_2 = 174\), qui n’est pas du tout le zéro attendu (même avec les deux représentations possibles de zéro).

Le système proposé ici n’est donc pas compatible avec l’addition binaire, il faut trouver autre chose.

La solution idéale: le complément à 2

Remarquons une chose intéressante: si on effectue l’addition sans dépassement de \(1111,1111_2 = 255\) avec 1, on trouvera \(0000,0000_2 = 0\) (en effet, le résultat devrait théoriquement être \(1,0000,0000_2 = 256\), mais la dernière retenue a été perdue.

Cela nous met sur la bonne voie: dans la représentation idéale des entiers relatifs, le nombre \(1111,1111_2\) devrait représenter l’entier \(-1\), puisqu’il donne zéro lorsqu’on lui ajoute 1 !

C’est exactement comme cela que nous allons procéder: puisque nous avons vu que, en tronquant à 8 bits, le nombre 256 donne zéro, on pourra représenter un entier négatif \(-n\) par \(256 - n\).

Dans la pratique, on n’effectuera pas de soustraction, il y a beaucoup plus rapide. En effet, on peut écrire: \[256 - n = 255 + 1 - n = (255 - n) + 1\] Pourquoi faire cela ? Tout simplement parce que \(255 - n\) se calcule très facilement en binaire: il suffit d’inverser tous les bits: c’est ce qu’on appelle le complément à deux.

Complément à deux Pour calculer le complément à deux d’un entier \(n\) sur un nombre de bit donné, on procède toujours en deux étapes:

  1. On inverse les bits de la représentation binaire de \(n\);
  2. On ajoute 1 (sans dépassement)

Le nombre obtenu sera appelé le complément à deux de \(n\), et il représente le nombre \(-n\), bien que son nom réel devrait être complément à deux puissance \(N\), où \(N\) est le nombre de bits de la représentation de ce nombre (8, 16, 32, etc).

Deux questions se posent:

  • Pourquoi \(255 - n\) correspond-il à l’inversion des bits ? Tout simplement parce que \(255 = 2^7 + 2^6 + \cdots + 2^0\) est la somme des huits puissances de deux. En effectuant \(255 - n\), on supprime donc de cette somme les puissances composant le nombre \(n\): cela revient à chercher exactement les puissances qui ne sont pas dans \(n\), autrement dit, à inverser les bits de la représentation de \(n\).
  • Combien de nombres négatif peut-on représenter ainsi ? Comme on a 256 valeurs possibles, le plus judicieux est de couper la poire en deux: on aura 128 valeurs positives (les nombres entre 0 et 127) et 128 valeurs négatives (les nombres entre -128 et -1). Cela fonctionne très bien:
Représentation binaire Entier non signé Entier signé
1111 1111 255 -1
1111 1110 254 -2
1111 1101 253 -3
\(\vdots\) \(\vdots\) \(\vdots\)
1000 0010 130 -126
1000 0001 129 -127
1000 0000 128 -128
0111 1111 127 127
0111 1110 126 126
\(\vdots\) \(\vdots\) \(\vdots\)
0000 0010 2 2
0000 0001 1 1
0000 0000 0 0

On constate plusieurs choses:

  • Le zéro a à nouveau une représentation unique, ce qui est une bonne chose;
  • Étant donné une représentation binaire sur un octet (ou toute autre taille), il n’y a aucun moyen de savoir s’il s’agit d’un nombre signé (entre -128 et +127) ou bien un nombre non signé (entre 0 et 255): il appartient au programmeur de toujours savoir ce que contient un octet: s’il y a placé un nombre signé, il devra l’interpréter comme tel.
  • On garde tout de même un effet bénéfique de notre tentative ratée de représenter les entiers négatifs: un entier sera négatif si et seulement si son bit de poids fort est à 1 !

Exercices pratiques

Comment déterminer dans la pratique le complément à deux d’un entier \(n\) sur une représentation à \(N\) bits ? Nous avons vus plusieurs algorithmes potentiels:

  • Le complément à deux se calcule simplement par l’opération \(2^N - n\), par exemple \(256 - n\) si on est sur 8 bits, \(65536 - n\) sur 16 bits, etc.

  • On peut avantageusement remplacer cette soustraction par:

    • Inverser les bits (ce qui correspond à une négation logique)
    • Ajouter 1
  • Ce dernier algorithme peut même être raccourci davantage pour une conversion de tête:

    • En commençant par le bit de poids faible (à droite), chercher le premier bit à 1 (s’il y en a).
    • Inverser tous les bits situés à gauche de celui-ci.

    Notons que s’il n’y a aucun bit à 1, on n’inverse rien du tout. Le seul cas où cela pourrait se produire est le cas où \(n = 0\), et c’est alors normal de ne pas inverser de bits puisque la représentation de 0 est unique.

Comparons ces trois algorithmes sur le nombre \(n = 37\) avec une représentation sur 8 bits signés.

  • Le calcul de \(256 - 37\) donne \(11011011_2\).
  • La représentation de 37 étant \(00100101_2\) sur 8 bits, l’inversion des bits donne \(11011010_2\), ce qui nous amène bien à \(11011011_2\) lorsque l’on rajoute 1.
  • Dans la représentation de 37, le 1 le plus à droit est le dernier. Si on inverse tous les bits situés à sa gauche, c’est-à-dire \(\underline{0010010}\mathbf{1}_2\), on trouve bien \(11011011_2\).

Comment effectuer l’opération inverse, à savoir déterminer un nombre dont la représentation en complément à deux sur \(N\) bits est connue ?

  • On peut inverser l’algorithme précédent:
    • Soustraire 1
    • Inverser les bits
  • Mais en réalité il est beaucoup plus simple de constater le fait suivant: le complément à deux du complément à deux de \(n\) est \(n\). Autrement dit, appliquer deux fois l’opération du complément à deux retourne au nombre de départ. C’est plutôt logique lorsque l’on se rappelle que le complément à deux sert à calculer l’opposé d’un nombre. Et cela se justifie aisément d’un point de bue mathématique:
    • Le premier complément à deux revient à calculer \(2^N - n\).
    • Le second complément à deux donne alors \(2^N - \big(2^N - n\Big) = 2^N - 2^N + n = n\).

Prenons par exemple le nombre dont la représentation sur 16 bits signés est \(1111111101101000_{16}\). Quel est le nombre \(n\) représenté ?

Il suffit d’inverser tous les bits situés à gauche du 1 le plus à droite, c’est-à-dire \(\underline{111111110110}\mathbf{1}000_{16}\) pour trouver \(0000000010011000_{16}\) = 152. Le nombre original représente alors \(n = -152\).