mercredi 7 mai 2014

complément à 2

Dans cet article j'explique ce qu'est le complément à 2 (Two's complement) et pourquoi il est utilisé pour représenter les entiers en binaire.

Lorsque nous représentons les nombres en visuel, pour représenter les nombres négatifs nous les précédons simplement du symbole'-' comme dans -35. Mais comment sont-il représentés en mémoire d'ordinateur, c'est à dire en binaire, puisque tout n'est qu'une suite de zéro et un?

Puisqu'un nombre ne peut-être que soit positif, soit négatif un seul bit peut servir à indiquer son signe. On pourrait simplement par exemple réserver le bit le plus significatif pour cette fonction. Supposons des nombres de 8 bits et réservons le bit 7 pour le signe. On aurait alors que 5 serait représenté par 00000101 et -5 par 10000101. Avec 8 bits on pourrait donc représenter tous les entiers entre -127 et 127.

Pour faire les opérations arithmétiques on mettrait simplement de côté le bit de signe et l'opération serait effectuée sur les 7 autres bits. Supposons qu'on voudrait additionner 5 et -9 on s'y prendrais comment? En fait il faudrait soustraire 9-5 et changer le signe du résultat pour obtenir -4. Mais comment concevoir un soustracteur d'entiers avec des portes logique?

C'est ici que le complément à 2 interviens en simplifiant grandement le problème. Pour obtenir ce complément on procède comme suit.

  1. Inverser chaque bit du nombre binaire.
  2. Ajouter 1 au nombre résultant
  3. Le bit de débordement est rejeté
exemple: le complément à 2 de 5 (00000101) est 11111010+1 = 11111011

Le complément à 2 a des propriétés intéressantes par exemple si on recommence l'opération on obtient le nombre original:
11111011 -> 00000100+1= 00000101. Tout entier obtenu par complément à 2 est donc considéré comme l'inverse de ce nombre en signe et tout nombre dont le bit le plus fort est 1 est considéré comme la représentation négative de l'entier. Donc pour les entiers de 8 bits les nombre 00000000 à 01111111 (0 à 127) sont considérés comme entiers positifs. Si on fait le complément à 2 de ces 128 entiers ont obtient 00000000 à 10000001 (0 à -127).

Il y a 2 cas particuliers 0 et -128 en effet si on fait le complément à 2 de 0 on obtient 0 lui-même et celui de -128 11111111 abouti à lui-même aussi. Donc l'étendue (domaine) des entiers binaire en complément à 2 pour 8 bits est de -128 à 127. Ainsi avec le système des compléments à 2 les entiers ont toujours un représentant de plus du côté négatif.

Poursuivons notre exploration de ce système pour en percevoir toutes les propriétés intéressantes. Fabriquer un additionneur de nombre binaires avec des portes logiques est simple mais fabriquer un soustracteur serait beaucoup plus complexe. Et les 2 circuits seraient complexes s'il fallait tenir compte du signe des nombres. En effet comme on la vue plus haut additionner un nombre positif et un nombre négatif revient en fait à soustraire en conservant le signe du nombre de plus grande magnitude.

Heureusement la représentation en complément à 2 nous évite ces complications. le fait est que si on veut soustraire un nombre d'un autre il suffit d'additionner son complément à 2. Je veux soustraire 5 de 9. Je produit simplement avec la fonction NOT le complément à 1 de 5 et je lui additionne 1 pour obtenir 11111011 j'additionne ça à 9, 00001001 et j'obtiens 00000100 avec un bit de débordement à 1.

 9 00001001
+
-5 11111011 (en fait le complément à 2 de 5)



   00000100 C=1

Et si on additionne un entier positif avec un entier négatif on obtient le bon résultat sans avoir à se soucier des signes. Prenons par exemple -3 + 7 = 4

-3 11111101
+
 7 00000111



   00000100 C=1

Dans ces 2 exemples C est le bit de débordement (carry bit).

Donc dans les faits les ordinateurs n'effectuent que des additions. Et un bit C à 1 indique que l'addition a débordée lorqu'on additionne 2 nombres positif. Un bit C à zéro lors d'une soustraction indique qu'il y a eu emprunt c'est à dire que le nombre soustrait était plus grand que l'autre. Dans le deuxième exemple on a additionner -3 à 7 et le bit de débordement est à 1 parce que la magnitude de -3 est plus petite que la magnitude de 7. C'est conforme à ce qu'on aurait obtenu si on avait voulu soustraire 3 de 7. si on avait additionner -9 + 5 on aurait obtenu:

-9 11110111
+
 5 00000101



   11111100 C=0

Ici le bit C est à zéro conformément au fait que si on soustrait 9 de 5 on doit faire un emprunt. Ce qui n'était pas le cas dans le premier exemple ou c'était 5 qui était soustrait de 9.

Voilà comment le complément à 2 permet de faire des additions et soustractions sur des nombres signés en utilisant simplement un additionneur.

Notez que ce système de complément à la base numérique est valide dans toutes les bases. Vous pouvez le vérifier sur papier avec la base décimale. Dans ce cas il s'agit évidement de trouver le complément à 10. Supposons que nous travaillions avec des nombres de 2 chiffres (0 à 99). Les nombres de 0 à 49 sont considérés comme positifs et les nombres de 50 à 99 comme négatifs. Pour obtenir le complément à 10 on procède comme suis:

  1. soustraire de 9 chaque digit.
  2. additionner 1 au résultat.
  3. jeter le débordement à 100 s'il y lieu.
exemple: 32 donne 9-3=6 et 9-2=7 et donc 67+1 = 68. Essayons 48 - 32 -> 48 + 68 = 116. On jette le digit de débordement on obtient bien 16.

Aucun commentaire:

Enregistrer un commentaire