Représentation des nombres entiers en informatique

I) Représentation des entiers naturels dans une base b
    1) Théorème et définition
    2) Remarques
    3) Exemples
II) Conversion d'un nombre entier vers une base b par des divisions euclidiennes successives
    1) Théorème
    2) Exemple
    3) Algorithmes
III) Conversion d'un nombre entier en base b vers la base 10
    1) Méthode
    2) Utilisation de l'algorithme de Horner
    3) Algorithmes
IV) Conversion de la base 16 vers la base 2 et inversement
V) Représentation des nombres entiers en informatique
    1) Représentation des nombres entiers positifs (ou encore entiers non signés)
    2) Représentation des nombres entiers positifs ou négatifs  (ou encore entiers signés) par la méthode du complément à 2
    3) Calcul rapide pour les nombres négatifs
    4) Problèmes résultant de le représentation des entiers                 

I) Représentation des entiers naturels dans une base b

1) Théorème et définition

  Soient N , b N avec b 2 . Alors N   s'écrit de façon unique N = a n b n + a n - 1 b n - 1 + ... + a 2 b 2 + a 1 b + a 0 avec a i { 0 , ... , b - 1 } .

  Les entiers a n , a n - 1 , ... , a 0 sont alors les chiffres (ou les digits) de N en base b et on note N = ( a n a n - 1 ... a 0 ) b ou N = a n a n - 1 ... a 0 .

2) Remarques

    (1) L'écriture usuelle d'un entier N est son écriture en base 10. En base 10, N = 237 s'écrit N = 237 car 237 = 2 10 2 + 3 10 + 7 . Les chiffres de N en base 10 sont 2, 3, 7. On n'écrit  pas N = ( 237 ) 10 , mais tout simplement N = 237.

    (2) En base b >10, on utilise les lettres A,B, C,... pour désigner les chiffres 10, 11, 12,...

3) Exemples

- En base 2, N = 13 s'écrit N =1101 car 13 = 1 2 3 + 1 2 2 + 0 2 + 1 . Les chiffres de N en base 2 sont 1, 1, 0, 1.
- En base 16, N = 100 s'écrit N = 64 car 100 = 6×16 + 4. Les chiffres de N en base 16 sont 6, 4 .
- En base 16, N = 200 s'écrit N = C8 car 200 = 12×16 + 8 . Les chiffres de N en base 16 sont C, 8 .
- En base 36, N = 10 6 s'écrit N = LFLS car 10 6 = 21 36 3 + 15 36 2 + 21 36 + 28 . Les chiffres de N en base 36 sont L, F, L, S.

II) Conversion d'un nombre entier vers une base b par des divisions euclidiennes successives

1) Théorème

Les chiffres (de droite à gauche) de l'écriture de N en base b sont les restes successifs r 0 , r 1 , r 2 , ... des divisions par b suivantes jusqu'à avoir un quotient q n nul:
    (1) on divise N par b    : N = q 1 b + r 0
    (2) on divise q 1 par b : q 1 = q 2 b + r 1
    (3) on divise q 2 par b : q 2 = q 3 b + r 2
    Etc...    
    (x) On divise q n - 1 par b : q n - 1 = 0 b + r n
Alors N = ( r n r n - 1 ... r 0 ) b

  En effet:  La suite ( q n ) des quotients successifs est une suite strictement décroissante d'entiers.  Donc il existe un plus petit entier n ∈ N * tel que q n = 0 . Alors l'écriture de N en base b est N = r n r n - 1 ... r 1 .
  Car N = q 1 b + r 0 = ( q 2 b + r 1 ) b + r 0 = q 2 b 2 + r 1 b + r 0 = ( q 3 b + r 2 ) b 2 + r 1 b + r 0 = q 3 b 3 + q 2 b 2 + r 1 b + r 0 = ...= r n b n + r n - 1 b n - 1 + ... + r 2 b 2 + r 1 b + r 0 avec r i { 0 , ... , b - 1 } . Par définition, N = ( r n r n - 1 ... r 0 ) b

2) Exemple

46 = 15x3 + 1
15 = 5x3 + 0
5 = 1x3 + 2
1 = 0x3 + 1

Donc 46 =15x3 + 1 = (5x3 + 0)x3 + 1 =  ((1x3 + 2)x3 + 0)x3 + 1 =   1 x3 3 + 2 x3 2 + 0 x3 1 + 1 x3 0   = ( 1201 ) 3 en base 3 .

3) Algorithme de conversion en base b

a) Calcul de la liste des chiffres “bruts” de l'écriture de n en base b

def base_b(n,b):
    """ Calcul itératif de l'écriture de l'entier n en base b"""
    digits = []
    while n > 0:
        digits.append(n % b)        # On ajoute le chiffre en fin de liste
        n = n // b
    digits.reverse()                    # La liste est à l'envers, on la remet à l'endroit
    return digits

Par exemple:

base_b(46,3) = [1, 2, 0, 1]
base_b(1000000,36) = [21, 15, 21, 28]

b) Terminaison, correction, complexité, finalisation de l'écriture

Voir le TD: Arithmétique - Changement de base

III) Conversion d'un nombre entier en base b vers la base 10

1) Méthode

  Si  N = ( a n a n - 1 ... a 0 ) b , alors N = Σ k = 0 n a k b k . Bien sûr, ceci n'est correct que si les a i sont les chiffres de N en base b (c'est à dire a i { 0 , ... , b - 1 } ) et pas les lettres A,B,C,... Si l'entier N est écrit à l'aide de lettres pour les chiffres 10, il faudra déjà convertir ces lettres en nombres (10, 11, 12, ...).

2) Utilisation de l'algorithme de Horner

  Cet algorithme permet de calculer de manière élégante et efficace la valeur P(x) d'un polynôme P(X) en un réel x.
Si P ( X ) = Σ k = 0 n a k X k , alors on peut remarquer que P ( x ) = ( ... ( ( ( a n x + a n - 1 ) x + a n - 2 ) x + a n - 3 ) x + ... + a 1 ) x + a 0 .
Par exemple a x 3 + b x 2 + c x + d = ( ( ( a x + b ) x + c ) x + d   . On peut utiliser cet algorithme pour le calcul de N qui est un “polynôme” de “variable” b.

3) Algorithmes

Voir le TD: Arithmétique - Changement de base

IV) Conversion de la base 16 vers la base 2 et inversement

  Les bases 2 et 16 sont les bases utilisées en informatique. C'est très facile de passer d'une base à l'autre car 16 = 2 4 .
  Pour passer de l'écriture hexadécimale (en base 16) à l'écriture binaire (en base 2), chaque chiffre hexadécimal est convertit en un bloc de 4 bits en base 2.
Par exemple: 3→0011 et A→1010.

  Pour passer de l'écriture  binaire à l'écriture hexadécimale, on découpe le nombre en blocs de 4 bits depuis la droite, chacun de ces blocs donnera un chiffre en hexadécimal.
Par exemple     n = 101111100101011 →   10 1111 0010 1011 → 2F2B.   

V) Représentation des nombres entiers en informatique

1) Représentation des nombres entiers positifs (ou encore entiers non signés)

  La base 2 est naturellement utilisée pour représenter les entiers naturels. L'écriture en base 2 de N est la représentation informatique de N.
  Les valeurs usuelles, adaptées aux processeurs, sont les entiers codés sur 32 bits (4 octets) ou 64 bits (8 octets).
  Si l'on code un entier sur n bits, on peut écrire tous les entiers compris entre 0 = ( 00 ... 0 ) 2   et 2 n - 1 = ( 11 .. 1 ) 2 .
    • 8 bit (1 octet) permettent de représenter les entiers de l'intervalle {0,... ,255}
    • 32 bits (4 octets) permettent de représenter les entiers de l'intervalle {0,... ,4 294 967 295}
    • 64 bits (8 octets) permettent de représenter les entiers de l'intervalle {0,... ,18 446 744 073 709 551 615}

2) Représentation des nombres entiers positifs ou négatifs  (ou encore entiers signés) par la méthode du complément à 2

  Il y a diverses possibilités, mais celle qui est maintenant normalisée et adoptée par tous est celle appelée “complément à 2”. Elle est compatible avec l'addition de deux entiers de signes opposés. Voici son principe:

  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.

3) Calcul rapide pour les nombres négatifs

  L'opérateur binaire NOT inverse les valeurs des bits (NOT 0 = 1 et NOT 1 = 0). Il est facile de vérifier que pour un entier x positif écrit sur n bits en base 2,   NOT x = 2 n - 1 - x (car x + NOT x = ( 11 ... 1 ) 2 = 2 n - 1 ).
  On a alors, si x < 0 ,   y = 2 n - x = 2 n - 1 - x + 1 = NOT x + 1 . Donc:

Pour un entier signé x < 0 écrit avec n bits, c'est à dire si x { - 2 n - 1 , ... , - 1 } , on a x = NOT x + 1 .

Avec n = 8 et x = - 100 : on a x = 100 = ( 01100100 ) 2 , donc NOT |x| = ( 10011011 ) 2 et -100 = NOT |x| + 1 “=” 10011100 .

4) Problèmes résultant de le représentation des entiers

  L'ensemble des entiers représentés (naturels ou relatifs) sur un nombre fini d'octets est un ensemble fini. En cas de dépassement de la valeur de l'entier maximum (ou minimum) représentable, une erreur d'overflow ou un résultat erroné se produit.
  Certains langages, comme Python (à partir de Python 3), représentent les entiers sur un nombre variable d'octets et permettent ainsi de travailler de -∞ à +∞.

© 2014 - Eric Obermeyer      Powered by