Skip to content

1 1 3 4 texte

Représentation des entiers non-signés

Si nous devons manipuler des nombres entiers non-négatifs1 uniquement, on peut se contenter d’exprimer ces nombres en base \(2\). Cette représentation n’utilisera que les symboles \(0\) et \(1\) et constitue donc bien une représentation binaire. Ces nombres sont souvent appelés les nombres “non signés” en informatique, car il n’est pas nécessaire d’utiliser de symbole pour représenter leur signe. Dans les langages comme C ou C++, par exemple, on trouve le type unsigned int (Banahan, Brady, and Mark Doran 1991; Stroustrup 2018).

Si on considère une représentation sur un nombre \(n\) fixé de bits, cette technique permet de représenter tous les nombres de \(0\) (représenté par \(\underbrace{0\cdots 0}_n\)) à \(2^{n}-1\) (représenté par \(\underbrace{1\cdots 1}_n\)).

Représentation des nombres entiers signés

Voyons maintenant comment nous pouvons incorporer les nombres négatifs dans notre représentation. On ne peut pas se contenter de convertir les nombres vers la base \(2\), car le signe \(-\) qui est utilisé pour signaler qu’un nombre est négatif n’est pas directement manipulable par un ordinateur qui manipule des valeurs en binaire. Il faut donc trouver une technique pour représenter ce signe à l’aide de \(0\) et de \(1\) uniquement. Nous allons étudier quatre techniques différentes. Nous présenterons ces techniques en supposant que l’on considère une représentation sur \(n\) bits (par exemple, \(n=8\)).

Bit de signe

La première technique est la plus simple. Elle n’a que peu d’intérêt pratique, mais nous l’étudions quand même car elle sans doute la première idée à laquelle on pourrait songer, et qu’il est dès lors utile de la comparer à celles qui sont utilisées en pratique. Elle consiste à réserver le bit de poids fort pour représenter le signe du nombre (\(1\) signifiant que le nombre est négatif), qui sera représenté en valeur absolue sur les \(n-1\) bits de poids faible.

Exemple :

Avec le bit de signe sur \(n=8\) bits, le nombre \(5\) est représenté par \(0000\ 0101\). Le nombre \(-5\) est représenté par \(1000\ 0101\).

\(\blacksquare\)

Cette technique présente plusieurs inconvénients :

  • la valeur \(0\) possède deux représentations : \(0\cdots 0\) et \(10\cdots 0\) (qui représente \(-0\));

  • il est difficile d’effectuer des opérations sur cette représentation. En particulier, effectuer la somme (selon la procédure usuelle) d’un nombre positif et d’un nombre négatif ne donne pas le résultat attendu…

Les valeurs représentables à l’aide du bit de signe, et sur \(n\) bits vont de \(-2^{n-1}+1\) (représentée par \(1\cdots 1\)) à \(2^{n-1}-1\) (représentée par \(01\cdots 1\)). Cela fait au total \(2^n-1\) valeurs différentes, alors qu’il existe \(2^n\) représentations. La différence provient du fait que le zéro a deux représentations distinctes.

Complément à 1

Le complément à \(1\) d’un nombre binaire \(N\) est le nombre \(\overline{N}\) qu’on obtient en inversant tous les bits de \(N\). On peut utiliser le complément à \(1\) pour signaler qu’un nombre est négatif. Plus précisément, si on a une représentation sur \(n\) bits, on représente tous les nombres entiers non-négatifs par leur représentation binaire habituelle, et tous les nombres non-positifs par le complément à \(1\) de leur valeur absolue. Afin de pouvoir distinguer les nombres positifs des nombres négatifs, on limite les valeurs qu’on peut représenter : si on a une représentation sur \(n\) bits, on se limite aux nombres qui, en valeur absolue, tiennent sur \(n-1\) bits. Ainsi, le bit de poids fort sera toujours égal à \(0\) pour les nombres positifs, et à \(1\) pour les nombres négatifs.

Exemple :

Le nombre \(5\) est représenté par \(0000\ 0101\). La représentation de \(-5\) est obtenue en inversant tous les bits de la représentation de \(5\), soit \(1111\ 1010\). Sur \(8\) bits, la valeur \(128\), par exemple, n’est pas représentable, elle s’exprime en binaire par un nombre de \(8\) bits au moins: \(1000\ 0000\), et cette représentation s’interprète, en complément à \(1\), comme \(-0111\ 1111_2=-127\).

\(\blacksquare\)

L’avantage du complément à \(1\) sur le bit de signe est qu’il permet de faire des additions de manière relativement naturelle : on peut faire la somme usuelle de deux nombres (positifs ou négatifs) en complément à \(1\) et obtenir la réponse correcte, à condition d’ajouter le dernier report au résultat.

Exemple :

Nous donnons deux exemples sur \(4\) bits.

Considérons \(3-2 = 3+(-2)\). En binaire, avec le complément à \(1\), on obtient \(0011 + 1101\). En faisant la somme euclidienne, on obtient \(1\ 0000\), soit, sur \(4\) bits, \(0000\) avec un dernier report de \(1\). On ajoute ce report aux \(4\) bits de poids faible, et on obtient : \(0001\).

Considérons \(2-4 = 2+(-4)\). En binaire, avec le complément à \(1\), on obtient \(0010 + 1011\). En faisant la somme euclidienne, on obtient \(1101\) (le dernier report est égal à \(0\)), ce qui est bien la représentation, en complément à \(1\), de \(-2\).

\(\blacksquare\)

Malheureusement, comme avec le bit de signe, \(0\) possède toujours deux représentations en complément à \(1\) : \(0\cdots 0\) et \(1\cdots 1\). De ce fait, on ne peut, sur \(n\) bits, représenter que les nombres de \(-2^{n-1}+1\) à \(2^{n-1}-1\), soit à nouveau \(2^n-1\) valeurs différentes.

Complément à 2

Cette représentation est celle qui est utilisée en pratique pour les nombres entiers sur les processeurs modernes.

Le complément à \(2\) d’un nombre \(N\) est le nombre \(\overline{N}^2=2^n-N\) (où \(n\) est toujours le nombre de bits de la représentation). La représentation des nombres en complément à \(2\) suit le même principe que le complément à \(1\) : les nombres non-négatifs sont représentés par leur encodage binaire usuel, et les nombres négatifs sont représentés par le complément à \(2\) de leur valeur absolue.

Exemple :

Voici 3 exemples sur \(n=8\) bits :

  • \(1\) est représenté par \(00000001\) ;

  • \(-1\) est représenté par la représentation de \(2^8-1\), soit \(11111111\) ;

  • \(-5\) est représenté par la représentation de \(2^8-5\), soit \(11111011\).

\(\blacksquare\)

La technique du complément à \(2\) possède de nombreux avantages. Tout d’abord, \(0\) ne possède plus qu’une seule représentation, à savoir \(0\cdots 0\). Ensuite, on peut faire usage de l’addition usuelle sur tous les nombres positifs ou négatifs en complément à deux (il n’est pas nécessaire d’utiliser le report circulaire comme dans le cas du complément à \(1\), celui-ci peut être oublié).

Exemple :

Voici un exemple d’addition sur \(4\) bits. Considérons la somme \(7-5=7+(-5)\). En binaire et avec le complément à \(2\), \(-5\) est représenté par la représentation “classique” de \(2^4-5=16-5=11_{10}\), soit \(1011_2\). On a donc: \(0111_2 + 1011_2= 1\ 0010_2\), que l’on tronque sur \(4\) bits (on oublie systématiquement le dernier report) pour obtenir \(0010_2\), soit \(2_{10}\).

\(\blacksquare\)

Par ailleurs, comme zéro n’a plus qu’une seule représentation, on peut maintenant représenter \(2^n\) valeurs différentes sur \(n\) bits. La plus petite valeur représentable est maintenant \(-2^{n-1}\) (représentée par \(10\cdots 0\)), et la plus grande est \(2^{n-1}-1\) (représentée par \(01\cdots 1\)). On a donc gagné une valeur dans les négatifs par rapport au complément à \(1\).

Enfin, remarquons que \(\overline{N}^2\) peut être calculé plus facilement grâce à \(\overline{N}\), le complément à \(1\). En effet:

Théorème 1. Pour tout \(N\): \(\overline{N}^2=\overline{N}+1\).

Preuve

Nous considérons une représentation des nombres sur \(n\) bits. Nous savons que la somme d’un nombre avec son complément à \(1\) donne :

\[\begin{aligned} N + \overline{N} &= 1\cdots 1 \\ &= 2^n-1. \end{aligned}\]

Donc, en ajoutant \(1\) de part et d’autre de cette équation, nous avons :

\[\begin{aligned} N + \overline{N} + 1 &= 2^n-1 +1 \\ &= 2^n. \end{aligned}\]

En retranchant \(N\) de deux côtés, nous avons :

\[\begin{aligned} 2^n -N &= N + \overline{N} + 1 -N\\ &= \overline{N} + 1. \end{aligned}\]

Or, \(2^n-N=\overline{N}^2\), par définition. La dernière équation prouve donc que \(\overline{N}^2 = \overline{N}+1\). \(\Box\)

Excès à \(K\)

La technique de l’excès à \(K\) est à nouveau une idée simple : elle consiste à fixer une valeur \(K\) (appelée biais) suffisamment grande, et à représenter tous les nombres \(N\) (positifs ou négatifs) par la représentation binaire de \(N+K\) (nécessairement positif). De ce fait, sur \(n\) bits, toutes les valeurs entre \(-K\) (représentée par \(0\cdots 0\)) et \(2^n-1-K\) (représentée par \(1\cdots 1\)) sont représentables. On choisit souvent \(K\) égal à \(2^{n-1}\) de manière à répartir les valeurs positives et négatives représentables de manière équitable, mais ce n’est pas obligatoire (par exemple, dans la norme IEEE754 que nous verrons plus tard, ce n’est pas le cas).

Exemple :

Voici trois exemples sur 8 bits avec \(K=2^{n-1}=2^7=128_{10}\) :

  • \(1\) est représenté par la représentation binaire de \(1+2^7=129\), soit \(1000\ 0001\) ;

  • \(-1\) est représenté par la représentation de \(2^7-1\), soit \(0111\ 1111\) ;

  • \(-5\) est représenté par la représentation de \(2^7-5\), soit \(0111\ 1011\).

\(\blacksquare\)

Comparaison des différentes représentations

Afin de bien comprendre comment les différentes techniques de représentation fonctionnent, il peut être utile de les comparer. C’est l’objet de la table suivante : elle montre comment une même représentation binaire sur \(n\) bits (colonne de gauche) représente des valeurs différentes en fonction de la convention utilisée (voir aussi, à ce sujet, la discussion à la fin du présent chapitre).

Valeur représentée
Représentation Non signé Bit Signe Cpl. 1 Cpl. 2 Excès \(K\)
\(00\cdots 00\) \(0\) \(0\) \(0\) \(0\) \(-K\)
\(00\cdots 01\) \(1\) \(1\) \(1\) \(1\) \(-K+1\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(01\cdots 11\) \(2^{n-1}-1\) \(2^{n-1}-1\) \(\;\;\;2^{n-1}-1\;\;\;\) \(2^{n-1}-1\) \(\;\;\;2^{n-1}-1 - K\)
\(10\cdots 00\) \(2^{n-1}\) \(0\) \(-2^{n-1}+1\;\;\;\) \(-2^{n-1}\) \(2^{n-1}-K\)
\(10\cdots 01\) \(2^{n-1}+1\) \(-1\) \(-2^{n-1}+2\;\;\;\) \(\;\;\;-2^{n-1}+1\;\;\;\) \(\;\;\;2^{n-1}+1 - K\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(11\cdots 11\) \(2^n-1\) \(-2^{n-1}+1\) \(0\) \(-1\) \(2^n-1-K\)

Comparaison des différentes représentations (sur \(n\) bits).

Banahan, Mike, Declan Brady, and Mark Doran. 1991. The c Book. Addison Wesley. .

Stroustrup, Bjarne. 2018. A Tour of c++. Addison-Wesley.


  1. On se souviendra qu’un nombre positif est un nombre \(>0\) et qu’un nombre négatif est un nombre \(<0\). Les nombres \(\geq 0\) sont donc les nombres “non-négatifs”.