Représentation des entiers

4	Représentation des entiers

L'écriture des entiers vue dans la section précédente s'appelle représentation simple de position. Ce n'est pas tout à fait celle choisie pour représenter les nombres en machines. En effet, il se pose le problème de la représentation des entiers négatifs. La solution utilisée dans le langage mathématique courant consiste à utiliser un symbole (+ ou -), placé devant le nombre, indiquant s'il est positif ou négatif; ce système de représentation est appelé représentation simple de position avec bit de signe. Bien que d'usage courant, ce système implique qu'il faut deux algorithmes différents, l'un pour soustraire, l'autre pour additionner, et cela n'est ni souhaitable, ni nécessaire, comme nous allons le voir. Le mécanisme de représentation des entiers en machine que nous allons maintenant détailler s'appelle représentation simple de position, en complément à la base, et permet, lui, d'utiliser le même algorithme pour l'addition comme pour la soustraction.

4.1

Principe

Classiquement, et pour des raisons techniques, les entiers manipulés par les machines sont limités en taille, c'est-à-dire en nombre de chiffres. Soit N le nombre de chiffres disponibles : si la machine << travaille en base b >>, elle peut manipuler tous les nombres compris entre 0 et b^N-1, en représentation simple de position. Le principe de la représentation simple de position en complément à la base consiste à utiliser la moitié de cet intervalle de représentation pour représenter les nombres négatifs, selon la définition suivante : soit R(x) la représentation de l'entier x, et supposons b pair (c'est toujours le cas, en général b=2,4,8,16 ou 10)

si x Î [0,b^N/2-1], alors R(x)=x.
si x Î [-b^N/2, 0[, alors R(x) = x + b^N.

et les entiers (en machine) de b^N/2 à b^N-1 représentent les entiers négatifs de -b^N/2 à -1 .

Exemple : prenons b=10 et N=2. Les entiers représentables vont de -b^N/2=-10²/2=-50 à b^N/2-1=10²/2-1 =49 et, par exemple, R(-16)=-16+100=84.

4.2

Opérations

L'addition et la soustraction sont assurées par le même algorithme, puisque les positifs et les négatifs ont des représentations <<cohérentes>>. Notons Å un algorithme d'addition (cf section 6), supposé correct (c'est-à-dire donnant toujours le bon résultat); on définit l'addition par

R(x+y) = R(x) Å R(y)

dont on ne garde que les N derniers chiffres.

Exemple : prenons encore une fois b=10 et N=2. On a

R(25 + 13) = R(25)Å R(13)=25Å13=38=R(38)

qui est bien le résultat. Si on considère les négatifs :

R(-16 - 25) = R((-16)+(-25)) = R(-16) Å R(-25) = 84 Å 75 = 159

que l'on tronque à 59; or 59 = -41 + 100 et donc 59 = R(-41) et le résultat est encore une fois exact. Enfin voyons la soustraction :

R(45 - 37)=R(45+(-37))=R(45) Å R(-37)=45Å63=108

que l'on tronque à 08 qui est la représentation de 8, résultat de la soustraction de 37 à 45.

Que se passe-t-il si l'on dépasse les bornes de représentation, c'est-à-dire si le résultat d'une addition est strictement inférieur à -b^N/2 ou strictement supérieur à b^N/2-1 (ce que l'on nomme un dépassement de capacité)? Examinons ce cas sur un exemple (toujours en supposant b=10 et N=2): soit à additionner 38 et 42. L'algorithme d'addition va donner 80, qui est en fait la représentation de -20 ! Dans l'autre sens, si l'on additionne deux nombres négatifs dont la somme est trop grande (en valeur absolue), on va obtenir un nombre positif :

R(-30 - 35) = R(-30) Å R(-35) = 70 Å 65 = 135

tronqué à 35, qui est la représentation de 35 ! Résumons :

le résultat de l'opération 38 + 42 est -20;
le résultat de l'opération -30 - 35 est 35.

La conclusion est la suivante : un dépassement de capacité se traduit par un résultat de signe différent des opérandes. Il n'y a pas de dépassement de capacité si les opérandes sont de signes différents.

Exercices de la partie 4

Montrer que si les opérandes d'une addition sont de signes différents, il ne peut pas y avoir de dépassement de capacité.
La base est 4, le nombre de chiffres est 3. Donner tous les entiers représentables, et leur représentation.
La base est 10, le nombre de chiffres est 10. Donner les bornes de la représentation, et les représentations de -17914 et 59819.
La base est 10, le nombre de chiffres est 4. Effectuer les opérations suivantes :
4977 - 1728 3285 + 4827 1724 - 3021
Étudier les différentes façons de représenter les négatifs en base 2.