Représentation des entiers en complément à 2.

I) Présentation

1) Objectif

  On travaille sur la représentation des entiers signés par la méthode du complément à 2 sur n bits, puis on vérifie et on démontre que leur addition peut se faire dans tous les cas bit à bit.

2) Définition de la représentation par complément à 2

  On dispose de n bits, donc de 2 n valeurs différentes, pour représenter les entiers x de l'intervalle    I n = { - 2 n - 1 , ... , 2 n - 1 - 1 } . Cet intervalle I n , presque centré en 0, contient bien 2 n entiers.
Si par exemple n = 8 , I n = { - 128 , + 127 } .
     (1) Si x 0 , c'est à dire si x { 0 , 1 , ... , 2 n - 1 - 1 } , on écrit  en base 2   x = ( 0 a n - 2 a n - 3 ... a 0 ) 2 , avec a i ∈ {0,1}.
  Cette écriture est la représentation de x en complément à 2 sur n bits.

    (2) Si x < 0, c'est à dire si x { - 2 n - 1 , ... , - 1 } , on calcule y = 2 n - x , (alors 2 n - 1 y 2 n - 1 , on écrit en base 2 y = ( 1 a n - 2 ... a 0 ) 2 avec a i ∈ {0,1} et la représentation de x en complément à 2 sur n bits est l'écriture de y .

Par exemple avec n = 8 et x = 100 . Comme 100 = 64 + 32 + 4 = ( 01100100 ) 2 , on aura donc 100 = 01100100
Avec   n = 8 et x = - 100 , on aura   y = 256 - 100 = 156 = 128 + 16 + 8 + 4 = ( 10011100 ) 2 , donc - 100 = 10011000 .

II) Algorithmes

Q1) Ecrire une fonction fonction conversion_base2(n) calculant la liste des chiffres de l'écriture de n en base 2 par la méthodes des divisions euclidiennes successives. Par exemple, conversion_base2(11111) = [1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1].

Q2)  Ecrire une fonction complement_2(x, n) calculant sous la forme d'une liste de 0 ou de 1 la représentation informatique de l'entier relatif x sur n bits par la méthode du complément à deux, avec un message d'erreur si ce n'est pas possible.

Par exemple:
    complement_2(2014, 16) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0]
    complement_2(-10000, 16) = [1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
    complement_2(1000,10) → L'entier 1000 n'est pas représentable sur 10 bits

Q3) Ecrire une fonction complement_2_reciproque(s), où s est une liste de 0 et de 1, calculant l'entier relatif x dont la représentation par la méthode du complément à 2 est la liste s.

Par exemple:
    complement_2_reciproque([0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1]) = 1987
    complement_2_reciproque([1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]) = - 888

Q4) Ecrire une fonction somme_bit_a_bit(x, y), avec x et y deux listes de même longueur de 0 ou de 1 (représentant deux nombres X et Y en base 2) et calculant la liste z = x + y de 0 ou 1 de même longueur. Cette liste z doit être calculée (comme pour une addition usuelle) en parcourant les listes x et y de droite à gauche, en tenant compte des retenues éventuelles sauf (éventuellement) celle provenant du calcul de x[0] + y[0] . On ne doit pas repasser par X et Y ou Z pour faire ce calcul, mais uniquement travailler sur les listes x et y.

Par exemple, avec n = 4:
    si x = [0, 0, 1, 1] et y = [1, 0, 1, 1] alors z = [1, 1, 1, 0]
    si x = [0, 1, 1, 0] et y = [1, 0, 1, 1] alors z = [ 0, 0, 0, 1]

  Dans la suite on vérifie d'abord expérimentalement (Q5) puis théoriquement que l'addition d'entiers codés par la méthode du complément à 2 d'entiers signés se fait dans tous les cas (si les entiers sont dans la bonne plage) par une simple addition bit à bit, comme dans la question précédente.

Q5) Ecrire une fonction addition(a, b, n) (avec n N * et a, b ∈   I n = { - 2 n - 1 , ... , 2 n - 1 - 1 } ):
    • calculant et affichant x = complement_2(a, n) et y = complement_2(b, n)
    • calculant z = somme_bit_a_bit(x, y)
    • calculant et affichant c =  complement_2_reciproque(z), et comparant c à a + b

Vérifier sur des exemples que:
    • lorsque a et b sont de signes contraires, alors  c = a + b et l'addition est correcte
    • lorsque a et b sont de même signe et que a + b ∈ I n , alors  c = a + b et l'addition est correcte.

En déduire que, dans tous les cas:  c ≠ a + b ⇔ x[0] = y[0] = 1 - z[0]

Par exemple:

addition(-83, 13, 8) renvoie:
a = -83 = [1, 0, 1, 0, 1, 1, 0, 1]
b = 13 = [0, 0, 0, 0, 1, 1, 0, 1]
c = -70 = [1, 0, 1, 1, 1, 0, 1, 0]
a + b = -83 + 13 = -70 = c

addition(100, 120, 8) renvoie:
a = 100 = [0, 1, 1, 0, 0, 1, 0, 0]
b = 120 = [0, 1, 1, 1, 1, 0, 0, 0]
c = -36 = [1, 1, 0, 1, 1, 1, 0, 0]
a + b = 100 + 120 != -36 = c

On justifie théoriquement ce que l'on constate par les tests.

Q6)  Soient n N * et a, b ∈   I n = { - 2 n - 1 , ... , 2 n - 1 - 1 } . On note:
    • x = complement_2(a, n) et y = complement_2(b, n)
    • z = somme_bit_a_bit(x, y) et c =  complement_2_reciproque(z)
  Q6a) Prouver que si a et b sont positifs et a + b ∈ I n , alors c = a + b.
  Q6b) Prouver que si a et b sont négatifs et a + b ∈ I n , alors c = a + b.
  Q6c)  Prouver que si a et b sont de mêmes signes et a + b ∉ I n , alors c ≠ a + b.
  Q6d) Prouver que si a et b sont de signes contraires, alors c = a + b.
  Q6e) En déduire que, dans tous les cas:  c ≠ a + b ⇔ x[0] = y[0] = 1 - z[0]

   L'addition de deux entiers a et b peut être faite quels que soient les signes de a et de b avec la même procédure.  C'est tout l'intérêt de la méthode de représentation en complément à 2.

Q7) Si l'on veut pouvoir additionner deux entiers signés quelconques de n bits (en base 2), quelle est la plus petite valeur de N  telle que l'addition par la méthode du complément à 2 sur N bits soit toujours correcte ?
Calculer (en base 10) la plage P centrée en 0 d'entiers relatifs pour lesquels l'addition par la méthode du complément à 2 sur 64 bits soit toujours correcte.

© 2014 - Eric Obermeyer      Powered by      Corrigé