Vous êtes sur une version archivée de lyceum.fr de l'année 2021/2022. Revenir au présent.

Chapitre 2: Représentation des entiers relatifs

Programme Officiel
Contenus Capacités attendues Commentaires
Représentation binaire d'un entier relatif Évaluer le nombre de bits nécessaires à l'écriture en base 2 d'un entier, de la somme ou du produit de deux nombres entiers. Utiliser le complément à 2. Il s'agit de décrire les tailles courantes des entiers (8, 16, 32 ou 64 bits). Il est possible d'évoquer la représentation des entiers de taille arbitraire de Python.
Lien vers le programme complet

Jusqu'à maintenant, nous avons appris à représenter des entiers naturels en représentation binaire ou hexadécimale.

Ainsi en utilisant des mots binaires de n bits, on peut coder 2n2^{n} nombres entiers.

Par exemple sur un octet, soit 8 bits, on peut coder 2n2^{n} valeurs soit dans le cas des entiers naturels des nombres de 0 à 255.

Cependant dans de nombreux programmes, il est nécessaire d'utiliser d'autres types de nombres comme les entiers relatifs ou les réels.

Méthode naïve: utilisation d'un bit de signe

La façon la plus simple de procéder serait de réserver le bit de poids fort pour le signe(0 pour positif et 1 pour négatif), et de garder le rester pour la représentation de la valeur absolue du nombre.

Avec un codage utilisant des mots de n bits, on pourrait représenter des nombres entre −2n−1+1-2^{n-1}+1 et 2n−1−12^{n-1}-1.

Par exemple, avec un codage sur 3 bits, des nombres entre -3 et 3:

Représentation binaire Valeur décimale
000 +0
001 +1
010 +2
011 +3
100 -0
101 -1
110 -2
111 -3

Malheureusement cette représentation possède deux inconvénients. Le premier (mineur) est que le nombre zéro (0) possède deux représentations. L'autre inconvénient (majeur) est que cette représentation impose de modifier l'algorithme d'addition ; si un des nombres est négatif, l'addition binaire usuelle donne un résultat incorrect. Voir l'article de Wikipedia pour plus de détails

Notation en complément à deux

Cette méthode permet de remédier aux problèmes évoqués ci-dessus.

On utilise toujours un bit de signe tout à gauche:

  • les entiers positifs sont codés normalement,
  • par contre on ajoute 2n2^n aux entiers négatifs.

Méthode d'encodage

L'entier négatif xx est codé comme s'il s'agissait de l'entier x+2nx + 2^{n} ou n est la taille du mot.

Il est possible d'appliquer un algorithme simple pour réaliser cette addition en binaire (cette méthode sera désignée comme 2e méthode par la suite).

  • On inverse les bits de l'écriture binaire de sa valeur absolue.
  • On ajoute 1 au résultat (les dépassements sont ignorés).

Avec ce codage utilisant des mots de n bits, on pourrait représenter des nombres entre −2n−1-2^{n-1} et 2n−1−12^{n-1}-1.

[Article Wikipedia sur le complément à deux]{.cite-source}

Utilisons cet encodage sur 3 bits.

−110=?2-1_{10} = ?_{2}
1ère méthode
−1=>−1+23=710=1112-1 => -1 + 2^3 = 7_{10} = 111_2
2e méthode
  1. La valeur −1-1 a pour valeur absolue 11 codé 001 sur 3 bits.
  2. On inverse les bits: 110
  3. On ajoute 1: 111

Les deux méthodes donnent le même résultat:

−110=1112-1_{10} = 111_{2}

Tableau de valeurs

Avec un codage sur 3 bits, on peut coder des nombres entre −23−1=−4-2^{3-1}=-4 et −23−1−1=3-2^{3-1}-1=3.

Représentation binaire Valeur décimale
000 +0
001 +1
010 +2
011 +3
100 -4
101 -3
110 -2
111 -1

On peut alors vérifier avec cette notation que l'algorithme d'addition utilisé pour les entiers naturels donne des résultats corrects avec cette représentation(voir les exercices[./exo]).

Méthode de décodage

Pour connaitre le nombre que représente un entier négatif, on effectue la démarche inverse:

  • On lui retranche 1 puis,
  • on inverse tous ces bits,
  • On convertit en base 10, et on ajoute le signe -.

Ce qui revient à lui soustraire 2n2^n.

Toujours en travaillant sur 3 bits:

1102=?10110_2 = ?_{10}

1ère méthode

1102=610=>6−23=−210110_2 = 6_{10} => 6 - 2^3 = -2_{10}

2e méthode

  1. On retranche 1: 110 - 1 = 101
  2. On inverse les bits: 010
  3. On convertit en base 10: 0102=210010_2 = 2_{10} donc c'est −2-2.

Les deux méthodes donnent le même résultat:

1102=−210110_2 = -2_{10}