Le complément à deux : comment représenter les entiers relatifs ? #

Les entiers relatifs #

Entiers naturels : entiers positifs ou nuls (0, 1, 2 etc.)
Entiers relatifs : entiers de n’importe quel signe (…, -2, -1, 0, 1,…)

Le problème du signe : #

Un signe n’est pas un nombre… On ne peut pas l’encoder directement en binaire.

Le principe est d’attribuer au bit de poids fort (premier bit) le signe du nombre.

Si le bit de poids fort est 0, le nombre est positif,

Si le bit de poids fort est 1, le nombre est négatif.

Nombres encodés sur un octet #

Contrainte immédiate : #

Il faut que la machine sache quelle est la taille du nombre !

Sinon :

Comment déterminer “le bit de poids fort” ?
Comment savoir où s’arrête le nombre ?

Dans tout ce document, on encodera nos nombres entiers sur 8 bits.

Approche naïve : binaire signé #

Essayons avec cette simple règle :

Pour encoder un entier sur 8 bits,

On détermine la représentation binaire de sa valeur absolue
Ensuite on remplit de 0 à gauche.

Signe

Si le nombre est positif, on garde le bit de poids fort à 0,
Sinon, on met le bit de poids fort à 1.

Ce qui fait donc :

Binaire signé sur un octet

1 bit de signe (0: positif, 1, négatif),

7 bits pour la valeur absolue.

On peut donc représenter de 1 111 1111 à 0 111 1111 soit de -127 à 127.

Que dire des nombres : 1 000 0000 et 0 000 0000 ?

Ils valent tous deux 0… on les note -0 et +0.

Premier exemple : 27


27 = 0b11011

On complète sur 8 bits :
27 = 0001 1011

27 > 0 on garde le premier bit à 0

La représentation en binaire signé sur un octet de 27 est 0 001 1011

Autre exemple : -9


La valeur absolue de -9 est 9.

9 = 0b1001

On complète sur 8 bits :
9 = 0000 1001

-9 < 0 on remplace le premier bit par -1 :

-9 = 1 000 1001

La représentation en binaire signé sur un octet de -9 est 1 000 1001

Jusqu’ici tout va bien…

Et soudain, c’est le drame… #

Essayons d’ajouter ces exemples :

Vérifions que $27 + (-9) = 18$

   0001 1011
+  1000 1001
------------
=  1010 0100

… mais 1 010 0100 = -36 en binaire signé sur un octet…

Le binaire signé ne permet pas de réaliser les additions habituelles

Exercice 1 #

On suppose toujours nos entiers encodés sur un octet.

Donner la représentation binaire signé de 12, de -100 et de -88.
Réaliser l’addition binaire bit à bit 12 + (-100).
Comparer avec le résultat obtenu.

Avec le binaire signé, on ne peut plus réaliser d’opération naturelle sur les entiers. On a maintenant deux objectifs :

Représenter les entiers relatifs,
Conserver le même algorithme pour l’addition

Le complément à deux #

On doit encore travailler avec une taille fixe

On choisit à nouveau 8 bits par simplicité.

Entiers positifs #

Coder l’entier en binaire comme d’habitude,
Compléter l’octet avec des 0 devant.

Entiers négatifs #

Coder la valeur absolue du nombre en binaire,
Compléter l’octet avec des 0 devant,
Échanger tous les bits ($1 \leftrightarrow 0$),
Ajouter 1.

Signe du complément à deux #

Si le bit de poids fort est 0, le nombre est positif
Si le bit de poids fort est 1, le nombre est négatif

Exemple 1 : 27


1. coder l'entier en binaire comme d'habitude,
    27 = 0b11011
2. compléter l'octet avec des 0 devant.
    27 = 0b 0001 1011

Le complément à 2 sur un octet de 27 est 0b 0001 1011

Exemple 2 : -9


1. coder la valeur absolue du nombre :
    9 = 0b1001
2. compléter l'octet :
    0b 0000 1001
3. échanger tous les bits :
    0b 1111 0110
4. ajouter 1 :
    0b 1111 0111

Le complément à 2 sur un octet de $-9$ est 0b 1111 0111

Complément à 2, méthode rapide #

La méthode précédente se code facilement, elle est plus pénible à la main.

La méthode rapide : complément à 2 sur un octet de $n$ :

Si l’entier est négatif :

donner la représentation binaire de la valeur absolue

Compléter à gauche jusqu’à avoir la taille voulue

de droite à gauche, conserver tous les bits jusqu’au premier 1 inclus

changer tous les bits à gauche

Exemple $n = -108$

Valeur absolue :

$|n| = 108 = 64 + 32 + 8 + 4$

Représentation binaire :

$|n| = 108$ = 110 1100
Compléter :

$|n| = 108$ = 0110 1100
Conserver les 0 à droite jusqu’au premier 1 inclus, changer tous les bits à gauche.

$n = -108$ = 10010 100

La représentation en complément à 2 sur un octet de $-108$ est 1001 0100.

Vérifions : $27 + (-9)$

  0001 1011
+ 1111 0111
-----------
= 0001 0010

On a bien 18 = 0b10010

Remarque la dernière retenue (tout à gauche) disparait.

Exercice 2 #

Donner les compléments de à 2 sur un octet de 12, -100 et de -88.

Exercice 3 #

Réaliser l’addition binaire des compléments à 2 des nombres 12 et -100.
Vérifier qu’on retrouve bien le résultat précédent pour -88.

Du complément à deux au décimal #

Si l’entier est positif (son premier bit est 0) #

On fait comme d’habitude.

Exemple : 0b 0001 1011

$1 \times 1 + 1\times 2 + 1\times 8 + 1\times 16 = 27$

Si l’entier est négatif (son premier bit est 1) #

Échanger tous les bits $0 \leftrightarrow 1$,
Ajouter 1,
Convertir en décimal normalement,
Changer le signe.

Exemple : 0b 1111 0111, en complément à 2 sur 8 bits,

1. On échange tous les bits,
    0b 0000 1000
2. On ajoute 1,
    0b 0000 1001
3. On converti en binaire comme d'habitude,
    0b 1001 = 1 * 1 + 1 * 8 = 9
4. On change le signe.
    0b 1111 0111 = -9

Du complément à 2 au le décimal, méthode rapide. #

Si le nombre est positif, comme d’habitude.

Si le nombre est négatif :

De droite à gauche, conserver tous jusqu’au premier 1 inclus,

Échanger tous les bits à gauche de ce 1,

Convertir en décimal normalement,

Changer le signe,

Exemple : 0b 1010 1000, en complément à 2 sur 8 bits

De droite à gauche, conserver tous jusqu’au premier 1 inclus,
0000 et 1000 qui sera conservé
Échanger tous les bits à gauche de ce 1,
0101 1000
Convertir en décimal normalement,
0101 1000 = $8 + 16 + 64 = 88$
Changer le signe :
en complément à 2 sur un octet $n =$ 1010 1000 $=-88$

Exercice 4 #

Donner les notations décimales des compléments à deux sur un octet suivants :

a = 0b1111 1111
b = 0b1000 0000
c = 0b0111 1111
d = 0b1010 0011
Calculer a + b et c + d en binaire et vérifier le résultat.

Propriétés #

Table de valeurs #

La table de valeur est remarquable, en particulier les “petits” nombres négatifs sont remplis de 1.

 bit
 de
signe
    0 1 1 1 1 1 1 1 =  127
    0      ...      =  ...
    0 0 0 0 0 0 1 0 =    2
    0 0 0 0 0 0 0 1 =    1
    0 0 0 0 0 0 0 0 =    0
    1 1 1 1 1 1 1 1 =   -1
    1 1 1 1 1 1 1 0 =   -2
    1      ...      =  ...
    1 0 0 0 0 0 0 1 = -127
    1 0 0 0 0 0 0 0 = -128

Combien d’entiers relatifs sur un octet ? #

Sur 8 bits en complément à deux, on peut encoder de $-128$ à $127$,

Combien d’entiers relatifs sur avec `n` bits ? #

Sur $n$ bits on peut encoder de $-2^{n-1}$ à $2^{n-1} - 1$.

Exercice 5 #

Combien d’entiers positifs peut-on encoder en binaire sur 32 bits ?
Combien d’entiers peut-on encoder en complément à 2 sur 32 bits ?
Expliquer.

Complément à 2 : résumé #

Le complément à 2 sur $n$ bits permet de représenter des entiers positifs et négatifs,

Le signe du nombre est donné par le premier bit,

L’addition usuelle fonctionne aussi avec les entiers négatifs.

Cette méthode permet d’encoder sur $n$ bits les entiers de $-2^{n-1}$ à $2^{n-1} - 1$

La méthode rapide pour encoder un entier en complément à 2 sur un octet :

s’il est positif, on l’écrit en binaire et on complète l’octet avec des 0 à gauche,

s’il est négatif,

on écrit sa valeur absolue en binaire qu’on complète à gauche,

on conserve tous les 0 à droite jusqu’au premier 1 inclus,

on inverse tous les bits à gauche de ce premier 1.

Pour décoder on fait le contraire

Python et le complément à 2. #

Les opérations précédentes imposent de choisir une taille maximale pour les entiers

Dans Python les entiers ont une taille arbitraire, il ne peut afficher nativement le complément à deux.

>>> bin(12)
'0b1100'
>>> bin(-12)
'-0b1100'

Pour obtenir le complément à 2, il faut le programmer.

Dans de nombreux langages, on distingue les entiers positifs des négatifs et différentes tailles sont proposées.

Cours