Entiers relatifs : complément à 2

Travailler avec uniquement des entiers naturels serait peu pratique en informatique, puisque nous avons dans la vie de tous les jours l'habitude de manipuler des entiers relatifs.

Il nous faut donc trouver une représentation, un codage, à l'aide de bits, pour représenter les entiers relatifs.

Représentation "naïve"

La première idée qu'on pourraît avoir serait, pour un entier relatif à $n$ bits, de réserver le bit de poids fort (le bit $n-1$) pour le signe du nombre : $0$ pour un nombre positif, $1$ pour un nombre négatif.

Les autres bits seraient alors la valeur absolue du nombre.

Exemple sur 4 bits:

4 bits	Décimal si naturel	Décimal si relatif
$0011$	3	3
$1011$	11	-3
$1111$	15	-7
$0000$	0	0
$1000$	8	0

Cette représentation pose deux problèmes :

Le nombre $0$ a deux représentations différentes.
L'addition ne fonctionne pas comme une addition entière.

Aussi, si on fait $6 + (-1) = 5$ sur nos 4 bits, avec la représentation signée en utilisant une addition comme pour les entiers naturels, on a donc $0110 + 1001 = 1111$, ce qui vaudrait $-7$ !

Pour palier ces problèmes, la plupart des ordinateurs utilisent un autre codage des entiers relatifs, le complément à 2.

Représentation en complément à 2

La représentation en complément à 2, notée $cpt2$ dans ce cours, code un nombre relatif sur $n$ bits de la manière suivante :

Les entiers positifs et zéro sont représentés en base 2 usuelle, sur les $n-1$ bits de poids faible.
Un entier négatif est calculé à partir de sa valeur absolue, avec deux opérations :
- Un NON bit-à-bit sur le nombre, le complément à 1. $0011_{cpt2}$ devient donc $1100_{2}$.
- On ajoute $1$ au résultat avec une addition d'entier naturel. ${1100_{2} + 1} = 1101_{cpt2}$.

Donc en complément à 2, $0011_{cpt2} = 3_{10}$ et $1101_{cpt2} = -3_{10}$

Remarque

La représentation en complément à 2 ne marche que si le nombre est codé sur un nombre fini de bits. C'est particulièrement adapté à nos ordinateurs, qui en général représentent les nombres entiers sur 8, 16, 32 ou 64 bits.

Cette représentation est très avantageuse :

Zéro n'a qu'une seule représentation, qui est tous les bits à zéro, comme les entiers naturels en base 2.
L'addition binaire des entiers naturels fonctionne si l'on ne considère pas le dépassement d'entiers !

Si on fait $6 + (-1) = 5$ sur nos 4 bits avec la représentation complément à 2, $0110_{cpt2} + 1111_{cpt2} = 0101_{cpt2}$, ce qui fait bien $5$ :

Ces deux propriétés permettent de réutiliser les circuits d'addition des entiers naturels pour additionner des entiers relatifs, et donc d'économiser une place précieuse dans les processeurs !

Plages de valeurs

Observont les valeurs de nos entiers relatifs en complément à 2 sur 4 bits

valeur en cpt 2 sur 4 bits	Valeur décimale
$0000$	$0$
$0001$	$1$
$0010$	$2$
$0011$	$3$
$0100$	$4$
$0101$	$5$
$0110$	$6$
$0111$	$7$
$1000$	$-8$
$1001$	$-7$
$1010$	$-6$
$1011$	$-5$
$1100$	$-4$
$1101$	$-3$
$1110$	$-2$
$1111$	$-1$

On remarque que si le bit de poids fort est à 1, alors le nombre est négatif. Sinon, il est positif.

En complément à 2 sur $n$ bits, on peut donc représenter toutes les valeurs de l'intervalle :

\[ [2^{n-1}; 2^{n-1}-1] \]

Exercice

Question 1Réponse

Quel est l'intervalle des valeurs représentables sur 8 bits en complément à 2 ? ($2^{8} = 256$, $2^{7} = 128$)

$[2^{7}; 2^{7}-1]$, soit $[-128;127]$

Question 2Réponse

Quel est l'intervalle des valeurs représentables sur 16 bits en complément à 2 ? ($2^{16} = 65536$, $2^{15} = 32768$)

$[2^{15}; 2^{15}-1]$, soit $[-32768;32767]$

Question 3Réponse

Peut-on représenter $- 2,5 \times 10^{9} = -2500000000$ en complément à 2 sur 32 bits ? ($2^{32} = 4294967296$, $2^{31} = 2147483648$)

Non, la plus petite valeur représentable en complément à 2 sur 32 bits est $-2^{31} = -2147483648$

Conversions

Changement de signe

Pour changer rapidement le signe d'un nombre en complément à 2, il suffit d'inverser tous les bits qui ont un poids plus fort que le bit à $1$ de poids le plus faible.

Autrement dit, on lit le nombre de droite à gauche. A partir du moment où on rencontre un 1, on inverse tous les bits suivants qu'on rencontre.

Inverser le signe de $0110_{cpt2}$ sur 4 bits donne $1010_{cpt2}$.

Attention

Il y a deux exceptions à cette règle pour un nombre à $n$ bits : $0$ et $-2^{n-1}$. Par exemple, sur 4 bits :

$0000_{cpt2}$ (0) n'a pas d'inverse.

$1000_{cpt2}$ (-8) n'a pas d'inverse, ou plutôt 8 ne peut être représenté en complément à 2 sur 4 bits.

Exercice

Tous les nombres traités ici sont sur 8 bits.

Question 1Réponse

Calculez la représentation complément à 2 de l'inverse de $10000100_{cpt2}$.

$01111100_{cpt2}$

Détails : on lit de droite à gauche jusqu'au premier 1 inclus. On garde donc la partie en gras : 10000100, et on inverse le reste.

Question 2Réponse

Calculez la représentation complément à 2 de l'inverse de $00100101_{cpt2}$.

$11011011_{cpt2}$

Depuis la base 10

Pour calculer une représentation en complément à 2 sur $n$ bits d'un nombre $m$ en base 10 :

On s'assure qu'on peut bien représenter $m$ en complément à 2 sur $n$ bits.
Si $m = -2^{n-1}$, alors sa représentation est un $1$ suivi de $n-1$ zéros.
Sinon, on calcule la représentation en complément à 2 de $|m|$ sur $n$ bits.
Puis, si $m < 0$, on inverse son signe.

Exemple, on calcule $-82$ sur 8 bits :

$- 2^{7} <= -82 <= 2^{7} - 1$ On peut donc faire la conversion.

$-82 \neq - 2^{7}$, donc on continue la conversion

$|-82| = 01010010_{cpt2}$

Comme $-82 < 0$, on inverse la représentation : $10101110_{cpt2} = -82_{10}$.

Exercice

Question 1Réponse

Calculez la représentation en complément à 2 sur 8 bits de $-10$

$- 2^{7} <= -10 <= 2^{7} - 1$ On peut donc faire la conversion.

$-10 \neq - 2^{7}$, donc on continue la conversion

$|-10| = 00001010_{cpt2}$

Comme $-10 < 0$, on inverse la représentation : $11110110_{cpt2} = -10_{10}$.

Question 2Réponse

Calculez la représentation en complément à 2 sur 8 bits de $-128$

$- 2^{7} <= -128 <= 2^{7} - 1$ On peut donc faire la conversion.

$-128 = - 2^{7}$, donc sa représentation est un $1$ suivi de $7$ zéros : $-128 = 10000000_{cpt2}$.

Vers la base 10

Pour calculer la valeur décimale d'un nombre en représentation complément à 2 sur $n$ bits, on applique la méthode suivante :

Si le nombre est positif (le bit de poids fort est $0$), on calcule sa valeur en utilisant la même méthode que la représentation en base 2.
Si le nombre est négatif (le bit de poids fort est $1$):
- Soit (méthode 1) on inverse le signe de sa représentation, puis on calcule sa valeur absolue en utilisant la même méthode que la représentation en base 2, que l'on passe ensuite en négatif.
- Soit (méthode 2) on calcule la valeur $x$ de la représentation comme si elle était en base 2, puis on calcule sa valeur en faisant $x - 2^{n}$

Calculons la valeur décimale de $0011_{cpt2}$. Le bit de poids fort est $0$, on applique donc la même méthode que pour la représentation en base 2.

\[ \begin{align} 0011_{cpt2} &= 0 \times 2^{3} + 0 \times 2^{2} + 1 \times 2^{1} + 1 \times 2^{0} \\ &= 2 + 1 \\ &= 3 \end{align} \]

Calculons la valeur décimale de $1110_{cpt2}$. Le bit de poids fort est $0$, on inverse donc le signe, ce qui nous donne $0010_{cpt2}$, la valeur absolue. Comme elle est positive, on peut calculer sa valeur avec la méthode de la base 2. Celà donne donc 2. Comme $1110_{cpt2}$ est négatif, on prends l'inverse de sa valeur absolue, donc $1110_{cpt2} = -2$

Alternativement, on aurait pu utiliser la seconde méthode :

$1110_{cpt2}$ est sur 4 bits. On calcule la valeur décimale de $1110_{2}$ : $1110_{2} = 14$.

On applique la formule $x - 2^{n +1}$ :

\[ \begin{align} 1110_{cpt2} &= 14 - 2^{4}\\ &=14 - 16\\ & = -2 \end{align} \]

Exercice

Question 1Réponse

Quelle est la valeur décimale de $01001110_{cpt2}$ ?

Le bit de poids fort est 0 donc le nombre est positif. On applique donc la méthode de la base 2 :

\[ \begin{align} 01001110_{cpt2} &= 1 \times 2^{6} + 1 \times 2^{3} + 1 \times 2^{2} + 1 \times 2^{1} \\ &= 64 + 8 + 4 + 2\\ &= 78 \end{align} \]

Question 2Réponse (méthode 1)Réponse (méthode 2)

Quelle est la valeur décimale de $11001111_{cpt2}$ ?

Le bit de poids fort est $1$, on inverse donc le signe, ce qui nous donne $00110001_{cpt2}$, la valeur absolue.

Comme elle est positive, on peut calculer sa valeur absolue avec la méthode de la base 2 :

$$ \begin{align} 00110001_{cpt2} &= 1 \times 2 ^ {5} + 1 \times 2 ^ {4} + \times 2 ^{1}\ &= 32 + 16 + 1 \ &= 49 \end{align} $$.

On prends alors l'inverse de sa valeur absolue :$11001111_{cpt2} = -49$

Le bit de poids fort est $1$, le nombre est sur 8 bits. On calcule la valeur décimale comme si la représentation était en base 2:

\[ \begin{align} $11001111_{2} &= 1 \times 2 ^{7} + 1 \times 2 ^{6} + 1 \times 2 ^ {3} + 1 \times 2 ^ {2} + 1 \times 2 ^ {1} + 1 \times 2 ^ {0}\\ &=128 + 64 + 8 + 4 + 2 + 1\\ &=207 \end{align} \]

On applique ensuite la formule $x - 2^{n +1}$ :

\[ \begin{align} 207 - 2^{8} &= 207 - 256\\ &= -49 \end{align} \]

Notation Hexadécimale

On peut aussi noter la représentation en complément à 2 sous forme hexadécimale. on le notera 0xcpt2 dans ce cours. Par exemple, $00101011_{cpt2} =$ 3B_0xcpt2.

La conversion se fait avec exactement la même méthode qu'une représentation binaire : on fait des paquets de 4 bits en partant de la droite, et on convertis :

$00101011_{cpt2} =$ 3B_0xcpt2.

Augmenter le nombre de bits

Si on veut ajouter des bits à un nombre en complément à 2 sans changer sa valeur, il faut ajouter des bits de poids fort (a droite) de même valeur que le bit de poids fort du nombre initial.

Esquisse de preuve (exploration, difficile)

La preuve qui suit n'est pas parfaitement formalisée, elle vise à donner une idée précise de pourquoi la propriété ci-dessus est vraie.

Nombres positifs Soit $m \geq 0$ une valeur exprimée en complément à deux sur $n$ bits. Si on ajoute un zéro à droite, le nombre obtenu exprime la même valeur (propriété des nombres en représentation en base 2.).

Nombres négatifs. Soit $m \lt 0$ une valeur exprimée en complément à deux sur $n$ bits. On l'écrit donc comme suit : $r = b_{n-1}...b_{1},b_{0}$. Supposons que la valeur de $r$ interprêté comme une représentation en base 2 soit $p$.

On a alors $m = p - 2^n$ (formule vue plus haut).

Supposons alors que l'on ajoute un 1 à droite de cette représentation. On a donc $r_2 = 1b_{n-1}...b_{1},b_{0}$ écrite sur $n+1$ bits. La valeur de $r_2$ interprêté comme une représentation base 2 est $p + 2^n$. On remarque aussi que $2^{n+1} = 2*2^{n} = 2^{n} + 2^{n}$. On note $m_{2}$ la valeur de $r_2$ interprêté comme une représentation en complément à 2.

Finalement :

\[ \begin{align} m_{2} &= (p + 2^n) - (2^{n+1})\\ &= p + 2^{n} - 2^{n} + 2^{n} \\ &= p + 2^{n}\\ &= m \end{align} \]

Donc, si on ajoute un 1 à droite à la représentation en complément à 2 d'une valeur négative, la nouvelle représentation obtenue corresponds à la même valeur en complément à 2.

C'est ce qu'on appelle une extension de signe.

Pour passer $0110_{cpt2}$ de 4 à 8 bits, on rajoute $4$ zéros à gauche : $00000110_{cpt2}$.

Pour passer $1101_{cpt2}$ de 4 à 8 bits, on rajoute $4$ $1$ à gauche : $11111101_{cpt2}$

Exercice : plus de bits

Question 1Réponse

Quelle est la représentation en complément à 2 sur 16 bits de $00110011_{cpt2}$ ?

$00110011_{cpt2}$ est sur 8 bits. Le bit de poids fort est un 0. On rajoute donc 8 bits $0$ a gauche pour faire 16 bits :

\[ 0000000000110011_{cpt2} \]

Question 2Réponse

Quelle est la représentation en complément à 2 sur 16 bits de $10110011_{cpt2}$ ?

$10110011_{cpt2}$ est sur 8 bits. Le bit de poids fort est un 1. On rajoute donc 8 bits $1$ a gauche pour faire 16 bits :

\[ 1111111110110011__{cpt2} \]

Question 3Réponse

Quelle est la représentation en complément à 2 sur 8 bits de $0011_{cpt2}$ ?

$0011_{cpt2}$ est sur 4 bits. Le bit de poids fort est un 0. On rajoute donc 8 bits $0$ a gauche pour faire 16 bits :

\[ 00000011__{cpt2} \]

Réduire le nombre de bits

Supposons qu'on veuille écrire $1111111110001101_{cpt2}$ 16 bits sur 8bits, sans changer la valeur représentée ?

Pour ça, on va retirer les 8 bits de poids fort (droite) $11111111$, ce qui nous laisse $10001101_{cpt2}$ sur 8 bits.

Si on veut réduire le nombre de bits d'une représentation en complément à 2, on peut retirer les bits à droite qui ont la même valeur de bit de poids fort, sauf un.

A noter que ce n'est pas toujours possible de réduire le nombre de bit.

On peut enlever les $n$ bits à droite d'une représentation en complément à 2 dans en changer la valeur, seulement si les $n+1$ bits de droite ont tous la même valeur.

Par exemple, $1111111110001101_{cpt2}$, sur 16 bits, a la même valeur que $10001101_{cpt2}$, sur 8 bits.

On a pu retirer $11111111$ (8bits) à droite, parce que le les 9 bits de droite sont à 1..

De la même manière, $00000111_{cpt2}$, sur 8bits, a la même valeur que $0111_{cpt2}$.

Par contre, $110101_{cpt2}$, sur 4 bits, n'a pas la même valeur que $101_{cpt2}$, sur 3 bits, parce qu'ici, on a retiré à droite $110$, qui contient à la fois des 1 et des 0.

Aussi, $0101_{cpt2}$, sur 4 bits, n'a pas la même valeur que $101_{cpt2}$, sur 3 bits, parce qu'ici, on a retiré un 1 à droite, et le bit de poids fort est maintenant 0.

Exercice : moins de bits

Question 1Réponse

Si possible, exprimez $11111111010_{cpt2}$ (12 bits) sur 4 bits.

On peut retirer les 8 bits de poids fort, puisque les 9 bits de poids fort sont des 1.

$11111111010_{cpt2}$ sur 12 bits a la même valeur que $1010_{cpt2}$ sur 4 bits.

Question 2Réponse

Si possible, exprimez $11110000_{cpt2}$ (8bits) sur 4 bits.

Pour écrire $11110000_{cpt2}$ sur 4 bits, il faudrait retirer $1111$ a droite. Or, les 5 bits de poids fort sont $11110$, contiennent des 1 et de 0.

On ne peut donc pas écrire $11110000_{cpt2}$ sur 4 bits.

Question 3Réponse

Si possible, exprimez $1110111110001101_{cpt2}$ (16 bits) sur 8 bits.

On voudrait retirer les 8 bits de poids fort, $1101111$, mais ils contiennent des $0$ et des $1$ à la fois.

Donc on ne peut pas écrire $1110111110001101_{cpt2}$ sur 8 bits.

valeur en cpt 2 sur 4 bits	Valeur décimale
\(0000\)	\(0\)
\(0001\)	\(1\)
\(0010\)	\(2\)
\(0011\)	\(3\)
\(0100\)	\(4\)
\(0101\)	\(5\)
\(0110\)	\(6\)
\(0111\)	\(7\)
\(1000\)	\(-8\)
\(1001\)	\(-7\)
\(1010\)	\(-6\)
\(1011\)	\(-5\)
\(1100\)	\(-4\)
\(1101\)	\(-3\)
\(1110\)	\(-2\)
\(1111\)	\(-1\)