Représentation des nombres entiers

Les circuits et mémoires physiques sont des assemblages de transistors ne pouvant prendre que deux états. L'information y est donc stockée sous forme de chaîne de bit (binary digits, chiffres binaires, 0 ou 1). Ce qui impose par exemple une représentation des entiers (relatifs) en écriture binaire.

Rappelons le principe du système de numération positionnel en base 10 :

Par exemple : $$12345_{|10}=5*1+4*10+3*10^2+2*10^3+1*10^4$$

Plus généralement l'écriture en base $b$ d'un nombre : $$(a_pa_{p-1}\dots a_{0})_{|b}=\sum_{k=0}^p a_kb^k$$

Les entiers positifs

Q1 Passer d'une écriture en base 2 à la base 10 :

Q1a Combien vaut $x=01011101_{|2}$ en base 10 ?

Q1b Combien vaut $x=11111111_{|2}$ en base 10 ?

En python on peut utiliser la fonction int(ecriture binaire,2) pour contrôler :

# Conversion d'une écriture en base 2 vers la base 10
print("01011101 :",int("01011101",2))
print("11111111 :",int("11111111",2))

01011101 : 93
11111111 : 255

Q2 Passer d'une écriture en base 10 à la base 2 :

Q2a Quelle est l'écriture en base 2 du nombre treize ?

Q2b Connaissez-vous une méthode pour passer de l'écriture décimale d'un entier positif à son écriture binaire ? Si oui l'appliquer pour $n=135_{|10}$

Clic pour indice

*Penser à faire des divisions par 2 successives*

Il existe des fonctions pyhton pour faire ce travail. Testez vos résultats...

# fonction 'bin' qui donne l'écriture binaire d'un entier
print("Avec bin(135) :" ,bin(135))
# format ':b' qui donne l'écriture binaire d'un entier
print(f"Avec les f-strings : {135:b}")

Avec bin(135) : 0b10000111
Avec les f-strings : 10000111

Q3a Avec $N$ bits, quel est le plus grand nombre que l'on peut obtenir ?

Q3b Par quelle manipulation on peut obtenir le double d'un nombre écrit en base 2 ?

Q3c Comment fait-on pour savoir si un nombre écrit en base 2 est pair ? S'il est pair comment fait-on pour le diviser par 2 ?

Q4 (facultatif) En programmant votre technique de la question Q2, écrire votre propre fonction python dec2bin(value : int) -> list qui renvoie la liste des bits de l'écriture du nombre entier reçu en paramètre (on prendra soin de placer le bit de poids fort en position 0 dans la liste).

def dec2bin(value : int) -> list :
    """ Reçoit un entier positif et renvoie la liste des bits
    de son écriture binaire, avec le bit de poids fort en 
    position 0"""
    assert value == int(value) # on s'assure de recevoir un entier positif
    bits = []
    while value > 0 :
        bits.append(value%2)
        value = value // 2
    bits.reverse()
    return bits

print("Avec dec2bin(135) :",dec2bin(135))
print(f"Avec les f-strings : {135:b}")

Avec dec2bin(135) : [1, 0, 0, 0, 0, 1, 1, 1]
Avec les f-strings : 10000111

 II. Représentation en machine des entiers relatifs

On vient de voir un procédé mathématique qui permet d'écrire un nombre entier positif en n'utilisant que les symboles 0 et 1, ce qui est directement utilisable pour un codage en mémoire machine.

On aimerait trouver un moyen de stocker également des nombres entiers négatifs...

Remarque : En machine, pour représenter un nombre on fixe la longueur de la chaîne, disons à $N$ bits.

Une première idée : avec un bit de signe.

• On garde un bit sur les $N$ pour représenter le signe (positif ou négatif) et on code la valeur absolue du nombre sur les $N-1$ bits restant.
• Un problème : il y a du coup deux fois le nombre zéro (un positif et un négatif)
• On peut représenter les nombres compris entre $-(2^{N-1}-1)$ et $(2^{N-1}-1)$
• Plus embêtant : il faut deux algorithmes différents pour ajouter deux nombres de même signe et deux nombres de signes opposés.

Application numérique :

• Si $N=4$ on va de $-15$ à $+15$
• Si $N=8$ (un octet) on va de $-127$ à $+127$

Pour palier à ces inconvénients on a introduit la deuxième idée suivante :

Deuxième idée : le complément à 2 (ou plus précisément le complément à $2^N$)

• Les nombres entiers positifs ou nuls sont représentés en mettant le bit de poids fort à 0 et en utilisant les $N-1$ bits restants.
• Pour représenter un nombre entier $p<0$ on code le nombre $2^N-|p|=2^N+p$, c'est ce que l'on nomme le complément à 2

Remarque : il existe une méthode simple pour obtenir l'opposé d'un nombre représenté en complément à 2 :

• On inverse tous les bits ($0\rightarrow 1$ et $1\rightarrow 0$)
• On ajoute 1 au résultat en ignorant le bit supplémentaire si on dépasse le nombre de bits fixés.

Conséquences :

• Le premier bit (celui de poids fort) est toujours un bit de signe (0 pour positif, 1 pour négatif)
• 0 n'a qu'une seule représentation
• On représente les entiers de $-2^{N-1}$ à $2^{N-1}-1$ (donc un négatif de plus). Au passage on notera que si l'on applique la remarque précédente au nombre $-2^{N-1}$ (qui n'a pas d'opposé) on retombe sur lui-même.
• L'addition (ou la soustraction) est codée suivant un seul algorithme (voir Q5 ci dessous)

Vérifions sur un exemple pour comprendre la technique avec $N=4$:

• Prendre $x=0110_{|2}$ (qui est la représentation de six). Cherchons la représentation de "moins six".
• Pour cela on inverse les bits de $x$ pour obtenir $x'=1001_{|2}$.
• On ajoute 1 au résultat (poser l'addition en colonne...) : $x''=x'+1=1010_{|2}$.
• $x''$ est la représentation en complément à 2 de "moins six". On peut vérifier en posant l'addition que $x''+x=10000_{|2}=2^N$ (avec $N=4$).
• Refaire les mêmes étapes (inverser les bits et ajouter 1) sur $x''$ et vérifier que l'on retrouve $x$.

Q5 On fixe dans cette question $N=8$ (un octet).

Q5a Quelle est l'écriture binaire de -1?

Q5b Donner les représentations en complément à 2 des nombre 35, -35, 20 et -20 (on pourra vérifier les résultats avec la fonction python donnée dans la cellule suivante...)

Q5b Poser ensuite l'addition binaire de 35 + (-20) et vérifier que l'on obtient bien la représentation de 15

Q5d Poser alors l'addition binaire de (-35) + 20 et vérifier que l'on obtient aussi la représentation de -15

Q5e Quel est le plus grand entier positif que l'on peut représenter avec $N=8$? Quelle est son écriture binaire?

Q5f Quel est le plus petit entier négatif que l'on peut représenter avec $N=8$? Quelle est son écriture binaire?

Q5g Soit $x=1000\,0000_{|2}$. Quelle est l'écriture de $x$ en base 10 ? Appliquer la technique du complément à 2 pour déterminer l'écriture binaire de $-x$. Que constate-t-on ?

# Une fonction python qui permet de donner l'écriture d'un entier relatif
# en complément à 2, pour une taille N choisie arbitrairement

def two_complement_representation(value: int, nb_bits: int):
    """Return the two's complement of value with nb_bits bits"""
    assert -(2 ** (nb_bits-1)) <= value < 2 ** (nb_bits-1), \
        "Value " + str(value) + " should have been between " + \
        str(-(2 ** (nb_bits-1))) + \
        " and " + str(2 ** (nb_bits-1)-1)
    return ("{0:{fill}" + str(nb_bits) + "b}").format(value % (2 ** nb_bits), fill='0')

print("-1 :",two_complement_representation(-1,8))
print("35 :",two_complement_representation(35,8))
print("-35 :",two_complement_representation(-35,8))
print("0 :",two_complement_representation(0,8))
print("-128 :",two_complement_representation(-128,8))
print("127 :",two_complement_representation(127,8))

-1 : 11111111
35 : 00100011
-35 : 11011101
0 : 00000000
-128 : 10000000
127 : 01111111

Exercice

Un exercice pour essayer de bien maîtriser la notion de complément à 2.

Remarque : on fait le choix dans cet exercice de stocker les bits d'une représentation binaire dans une liste python (on aurait aussi pu travailler avec des chaînes de caractères...)

Q1 Écrire une fonction  add_bits(b1,b2,r0) qui renvoie le couple (b,r)qui est le résultat (avec retenue) de l'addition des deux bits b1 et b2 avec la retenue b0

def add_bits(b1,b2,r0):
    """ reçoit 2 bits b1 et b2, une retenue r0 et renvoie le couple (b,r)
    résultat de l'addition des bits b1, b2 et de la retenue r0"""
    b = (b1+b2+r0)%2
    r = (b1+b2+r0)//2
    return (b,r)

# version 2
def add_bits_bis(b1,b2,r0):
    """ reçoit 2 bits b1 et b2, une retenue r0 et renvoie le couple (b,r)
    résultat de l'addition des bits b1, b2 et de la retenue r0"""
    c = b1+b2+r0
    if c<= 1 :
        return (c,0)
    elif c==2 :
        return (0,1)
    else :
        return (1,1)

def test_add_bits():
    assert add_bits(0,0,0) == (0,0)
    assert add_bits(0,1,0) == (1,0)
    assert add_bits(0,1,1) == (0,1)
    assert add_bits(1,1,1) == (1,1)
    print("Tous les tests sont passés")

test_add_bits()

Tous les tests sont passés

Q2 Écrire une fonction add(L1,L2) qui réalise l'addition binaire de deux entiers positifs représentés par les listes L1 et L2 (attention s'assurer que les tailles des listes soient identiques, et on augmentera éventuellement la taille de 1 pour le résultat en cas de retenue...)

def add(L1,L2):
    """ reçoit deux listes représentant des entiers positifs et renvoie la 
    liste donnant la somme"""
    assert len(L1)==len(L2)
    L=[]
    L1.reverse()
    L2.reverse()
    retenue = 0
    for b1,b2 in zip(L1,L2) :
        b,retenue = add_bits(b1,b2,retenue)
        L.append(b)
    if retenue == 1 :
        L.append(retenue)
    L.reverse()
    return L

def test_add():
    assert(add([1,1,0],[0,0,1]))==[1,1,1]
    assert(add([0,1,1],[0,0,1]))==[1,0,0]
    assert(add([1,1,1],[0,0,1]))==[1,0,0,0]
    print("Tous les tests sont passés")

test_add()

Tous les tests sont passés

Q3 Écrire une fonction compla2(L : list,N : int) -> list qui reçoit une liste L représentant un entier relatif $x$ codé sur N bits et renvoie l'écriture de $-x$ avec la convention du complément à 2

def compla2(L : list,N : int = 8)-> list :
    assert len(L)==N , "problème de taille de liste"
    if sum(L)==0 :  # on traite 0 à part
        return L
    L2 = []
    for b in L :
        if b==0 :
            L2.append(1)
        else :
            L2.append(0)
    L3 = [0]*(N-1)+[1] # la liste représentant le nombre 1 sur N bits
    return add(L2,L3)

print(compla2([1,0,1,0],4))
print(compla2([0,0,0,0],4))
print(compla2([1,0,0,0],4))

[0, 1, 1, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]

Q4 Écrire enfin une fonction python conv10to2Z(x : int, n : int) -> list qui prend un entier relatif $x$ et un entier $n$ strictement positif en arguments et retourne la liste de longueur $n$ contenant les bits de $x$ en binaire avec la convention du complément à 2 (elle fait la même chose que two_complement_representation croisée précédemment)

def conv10to2Z(x : int, n : int) -> list :
    assert x>=-2**(n-1) and x<2**(n-1), "on doit avoir 2^(n-1) <= x < 2^(n-1)"
    # on ecrit abs(x) en base 2
    L = dec2bin(abs(x))
    for _ in range(n-len(L)):
            L.insert(0,0) # on ajoute des 0 pour obtenir une taille n

    if x>=0 :
        return L
    else :
        return compla2(L,n)

print("1 :",conv10to2Z(1,8))
print("-1 :",conv10to2Z(-1,8))
print("0 :",conv10to2Z(0,8))
print("-35 :",conv10to2Z(-35,8))
print("35 :",conv10to2Z(35,8))

1 : [0, 0, 0, 0, 0, 0, 0, 1]
-1 : [1, 1, 1, 1, 1, 1, 1, 1]
0 : [0, 0, 0, 0, 0, 0, 0, 0]
-35 : [1, 1, 0, 1, 1, 1, 0, 1]
35 : [0, 0, 1, 0, 0, 0, 1, 1]