Codage des entiers relatifs

Principe

Les entiers relatifs sont les nombres qui peuvent représenter des valeurs entières positives, négatives ou nulles.

Les mathématiciens représentent l’ensemble des entiers relatifs avec le symbole ℤ.

Ces nombres accompagné d’un signe ( ‘+’ ou ‘-’) sont aussi souvent appelés nombres signés.

Le principe de base pour représenter ces nombres est de coder son signe en plus de sa valeur dans la représentation binaire.

1ère tentative (erronée) de représentation

Une 1ère idée serait de prendre 1 bit, par exemple le MSB — c.-à-d. le bit le plus à gauche — pour coder le signe (0 pour le ‘+’ et 1 pour le ‘-’) puis de coder la valeur absolue du nombre dans le reste des bits.

Ex. pour représenter -5|10 sur 8 bits
         [1][000 0101]
signe ‘-’ ↲      ↳  5|10 codé sur 7 bits

Cependant, cette représentation présente plusieurs inconvénients :

  • elle autorise une double représentation du 0 (→ 0000 0000|2 et 1000 0000|2 sur 8 bits)

  • cette double représentation du 0 fait perdre une possibilité de coder un autre nombre. Par exemple, sur 8 bits on peut coder avec cette méthode uniquement 255 valeurs de -127 à +127 alors qu’avec 8 bits on peut théoriquement représenter 28 = 256 valeurs

  • et SURTOUT, elle mène à des résultats faux pour l’addition arithmétique quand un des 2 nombres est négatif.

    Ex. : 73|10 + -5|10
      0100 10101 → 73|10 (1)
+ 1000 01 01 → -5|10
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
  1100 11 10 → -77|10 ⇒ FAUX (68|10 attendu)
    1 noter la présence d’une retenue. En effet, en binaire, 0+0=0, 0+1=1, 1+1=0 et 1+1=10|2

Complément à 2

Pour remédier aux inconvénients de la méthode de représentation précédente, la majorité des langages de programmation vont utiliser une réprésentation dîte en complément à 2 notée 𝒞2(n) en math.

Dans cette représentation :

  • les nombres positifs sont représentés de manière usuelle

  • les nombre négatifs sont codés de la manière suivante :

    • on code en 1er la valeur absolue du nombre de manière usuelle

    • on remplace tous les 0 par des 1 et tous les 1 par des 0. C’est ce qu’on appelle le complément à 1 (noté 𝒞1(n) en math)

    • on ajoute 1 à la valeur obtenue

Ex. pour coder sur 8 bits le nombre -5|10 avec la représentation en complément à 2

  1. codage de la valeur absolue de -5

    |-5| → 0000 0101

  2. complément à 1 du résultat précédent

    𝒞1(0000 0101) = 1111 1010

  3. ajout de 1 au résultat précédent

      1111 1010
+ 0000 0001
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
  1111 1011

Donc, au final, -5|10 se code 1111 1011|2 en complément à 2.

On peut alors vérifier qu’avec cette représentation :

  • le 0 n’a qu’une seule représentation sur un nombre de bits donné :

    • +0 sur 8 bits donne : 0000 0000

    • -0 donne : 1 0000 0000 (→ 9 bits). Mais comme on désire un codage sur 8 bits, le 9ème bit est simplement ignoré et on retombe bien sur 0000 0000.

  • on va pouvoir représenter autant de valeurs que le nombre de bits choisi pour les représenter le permet. Ainsi, sur 8 bits on va pouvoir coder 28 = 256 valeurs, de -128|10 (→ 1000 0000|2) à +127|10 (→ 0111 1111|2)

  • l’addition d’un nombre positif et négatif donne le bon résultat

    Ex. : 73|10 + -5|10 = 68|10
        1 10111010 110101
+      1 1 1 1 1 0 11
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
     1 0 1 0 0 0 1 00 (1)
    1 Sur 8 bits (← 9ème bit ignoré), 0100 0100|2 = 68|10 ce qui est bien le résultat attendu

🞄  🞄  🞄