Aller au contenu principal

Sous-sections de Représentation et manipulation des nombres par un ordinateur

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Écrire un entier dans une base

Objectif

Comprendre comment un ordinateur, qui ne manipule que des 0 et des 1, écrit un nombre entier, et savoir passer de l’écriture en base 10 à l’écriture en base 2 ou en base 16, à la main puis avec Python.

Q15.

Un tee-shirt porte l’inscription : « Il y a 10 sortes de personnes : celles qui comprennent le binaire et les autres. » Combien de sortes de personnes la phrase énumère-t-elle vraiment ? Que peut bien valoir « 10 » pour que la phrase soit juste ?

Réponse

La phrase énumère deux sortes de personnes. Elle n’est juste que si « 10 » vaut deux. C’est le cas lorsque 10 est écrit en base 2, comme on va le voir : (10)2=2(10)_2 = 2. Le même assemblage de chiffres ne désigne pas le même nombre selon la base dans laquelle on l’écrit.

Ce que l’on fait sans y penser : la base 10

Un ordinateur est fait de circuits électroniques qui ne connaissent que deux états : le courant passe ou ne passe pas. On note ces deux états 0 et 1. Une information qui ne peut prendre que ces deux valeurs s’appelle un bit (de l’anglais binary digit, chiffre binaire). Pour écrire n’importe quel nombre avec seulement deux chiffres, l’ordinateur utilise la même idée que nous avec nos dix chiffres. Commençons donc par regarder de près ce que nous faisons tous les jours.

Dans le nombre 2026, les deux chiffres 2 n’ont pas la même valeur. Le premier compte pour deux milliers, le second pour deux unités. La valeur d’un chiffre dépend de sa position dans l’écriture :

2026=2×1000+0×100+2×10+6×1=2×103+0×102+2×101+6×1002026 = 2 \times 1000 + 0 \times 100 + 2 \times 10 + 6 \times 1 = 2 \times 10^3 + 0 \times 10^2 + 2 \times 10^1 + 6 \times 10^0

En base 10, on dispose de dix chiffres, de 0 à 9. Chaque position vaut dix fois plus que celle qui est à sa droite. On dit que le chiffre des milliers a un poids de 10310^3.

Q16.

Écrire 7305 sous la forme d’une somme de chiffres multipliés par des puissances de 10. Pourquoi a-t-on besoin d’un chiffre 0 dans cette écriture ?

Réponse

7305=7×103+3×102+0×101+5×1007305 = 7 \times 10^3 + 3 \times 10^2 + 0 \times 10^1 + 5 \times 10^0.

Le 0 indique qu’il n’y a aucune dizaine. Sans lui, on écrirait 735, qui est un autre nombre : le 0 sert à garder chaque chiffre à sa place.

Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

La base 2 : compter avec deux chiffres

Du binaire vers le décimal

En base 2, on ne dispose que de deux chiffres, 0 et 1. Chaque position vaut deux fois plus que celle qui est à sa droite. Les poids sont donc, de droite à gauche, 20=12^0 = 1, 21=22^1 = 2, 22=42^2 = 4, 23=82^3 = 8, 24=162^4 = 16, etc. Pour éviter toute confusion, on note la base en indice : (1101)2(1101)_2 désigne l’écriture en base 2, et 11011101 seul désigne le nombre mille cent un.

Exemple résolu : que vaut (1101)2(1101)_2 ?

On écrit les poids au-dessus de chaque chiffre, en partant de la droite :

poids 23=82^3 = 8 22=42^2 = 4 21=22^1 = 2 20=12^0 = 1
chiffre 1 1 0 1

On additionne les poids des positions où se trouve un 1 :

(1101)2=1×8+1×4+0×2+1×1=13(1101)_2 = 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 13

Les chiffres 0 ne comptent pas : ils servent seulement à garder les autres à leur place, comme en base 10.

Q17.

En utilisant la même méthode, déterminer la valeur décimale de :

  1. (10)2(10)_2 ;
  2. (101010)2(101010)_2 ;
  3. (11111111)2(11111111)_2.
Réponse
  1. (10)2=1×2+0×1=2(10)_2 = 1 \times 2 + 0 \times 1 = 2 : c’est le « 10 » du tee-shirt.
  2. (101010)2=32+8+2=42(101010)_2 = 32 + 8 + 2 = 42.
  3. (11111111)2=128+64+32+16+8+4+2+1=255(11111111)_2 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255.

Python sait faire ce calcul. La fonction int, qui convertit une chaîne en entier, accepte un deuxième argument : la base dans laquelle la chaîne est écrite. On peut aussi écrire directement un nombre en binaire dans un programme en le faisant précéder de 0b.

Q18.

Dans la console de Thonny, vérifier les réponses de la question précédente :

>>> int("101010", 2)
>>> int("11111111", 2)
>>> 0b101010
Réponse
>>> int("101010", 2)
42
>>> int("11111111", 2)
255
>>> 0b101010
42

Du décimal vers le binaire

Pour passer dans l’autre sens, on cherche à répondre à la question : quels poids faut-il additionner pour obtenir le nombre ? Une méthode systématique consiste à diviser le nombre par 2, encore et encore. On a déjà rencontré cette idée dans le Doc. 2,4 : n % 10 donnait le chiffre des unités de n en base 10, et n // 10 retirait ce chiffre. En base 2, on fait la même chose avec 2 à la place de 10.

Exemple résolu : écrire 13 en base 2

On effectue des divisions euclidiennes successives par 2, jusqu’à obtenir un quotient nul :

division quotient (n // 2) reste (n % 2) ce que donne le reste
13=2×6+113 = 2 \times 6 + 1 6 1 chiffre des unités (202^0)
6=2×3+06 = 2 \times 3 + 0 3 0 chiffre de poids 212^1
3=2×1+13 = 2 \times 1 + 1 1 1 chiffre de poids 222^2
1=2×0+11 = 2 \times 0 + 1 0 1 chiffre de poids 232^3

Le premier reste obtenu est le chiffre de droite. On lit donc les restes de bas en haut : 13=(1101)213 = (1101)_2. On vérifie : 8+4+1=138 + 4 + 1 = 13.

Q19.

Écrire 42 puis 100 en base 2 par la méthode des divisions successives. Vérifier ensuite avec la fonction bin de Python : bin(42) et bin(100).

Réponse

Pour 42, les restes successifs sont 0, 1, 0, 1, 0, 1 (quotients 21, 10, 5, 2, 1, 0). Lus de bas en haut : 42=(101010)242 = (101010)_2.

Pour 100, les restes successifs sont 0, 0, 1, 0, 0, 1, 1 (quotients 50, 25, 12, 6, 3, 1, 0). Lus de bas en haut : 100=(1100100)2100 = (1100100)_2.

>>> bin(42)
'0b101010'
>>> bin(100)
'0b1100100'

La fonction bin retourne une chaîne de caractères qui commence par '0b', pour rappeler que c’est une écriture en base 2.

Q20.

Un élève écrit 13 en base 2 et obtient (1011)2(1011)_2. Il a pourtant fait toutes les divisions sans erreur. Quelle erreur a-t-il commise ? Comment aurait-il pu la repérer lui-même ?

Réponse

Il a lu les restes de haut en bas, dans l’ordre où il les a obtenus. Or le premier reste est le chiffre des unités, qui s’écrit à droite. Il pouvait repérer l’erreur en vérifiant son résultat : (1011)2=8+2+1=11(1011)_2 = 8 + 2 + 1 = 11, et non 13. Vérifier une conversion en faisant la conversion inverse est un bon réflexe.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

La base 16 : une écriture plus courte du binaire

Les écritures binaires sont vite très longues : il faut 8 chiffres pour écrire 255, et 11 pour écrire 2026. Pour les écrire de façon plus compacte, les informaticiens utilisent la base 16, appelée hexadécimale.

En base 16, il faut seize chiffres. On utilise les chiffres de 0 à 9, puis les lettres A, B, C, D, E et F pour les valeurs de 10 à 15 :

base 16 0 1 2 3 4 5 6 7 8 9 A B C D E F
base 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Les poids sont maintenant des puissances de 16 : 160=116^0 = 1, 161=1616^1 = 16, 162=25616^2 = 256, etc. Par exemple :

(2A)16=2×16+10×1=42(\text{2A})_{16} = 2 \times 16 + 10 \times 1 = 42

En Python, un nombre écrit en base 16 commence par 0x, et la fonction hex donne l’écriture hexadécimale d’un entier.

Q21.
  1. Déterminer la valeur décimale de (FF)16(\text{FF})_{16} et de (7E3)16(\text{7E3})_{16}.
  2. Vérifier avec Python : 0xFF, int("7E3", 16) et hex(42).
Réponse
  1. (FF)16=15×16+15=255(\text{FF})_{16} = 15 \times 16 + 15 = 255 et (7E3)16=7×256+14×16+3=1792+224+3=2019(\text{7E3})_{16} = 7 \times 256 + 14 \times 16 + 3 = 1792 + 224 + 3 = 2019.
  2. >>> 0xFF
    255
    >>> int("7E3", 16)
    2019
    >>> hex(42)
    '0x2a'
    Python écrit les lettres en minuscules : 0x2a et 0x2A désignent le même nombre.

Passer du binaire à l’hexadécimal

Le grand intérêt de la base 16 vient de ce que 16=2416 = 2^4. Un chiffre hexadécimal, qui va de 0 à 15, correspond exactement à un paquet de 4 chiffres binaires, qui vont de (0000)2=0(0000)_2 = 0 à (1111)2=15(1111)_2 = 15.

Exemple résolu : écrire (10101101)2(10101101)_2 en base 16

On découpe l’écriture binaire en paquets de 4 bits, en partant de la droite : 1010  11011010 \; 1101.

On convertit chaque paquet séparément : (1010)2=8+2=10(1010)_2 = 8 + 2 = 10, soit A, et (1101)2=8+4+1=13(1101)_2 = 8 + 4 + 1 = 13, soit D.

On obtient (10101101)2=(AD)16(10101101)_2 = (\text{AD})_{16}. Aucune division n’a été nécessaire.

Q22.
  1. Écrire (11110000)2(11110000)_2 en base 16.
  2. Écrire (3C)16(\text{3C})_{16} en base 2.
  3. Pour écrire (110101)2(110101)_2 en base 16, un élève découpe 1101  011101 \; 01 et obtient (D1)16(\text{D1})_{16}. Que lui répondre ?
Réponse
  1. 1111  00001111 \; 0000 donne F et 0 : (11110000)2=(F0)16(11110000)_2 = (\text{F0})_{16}.
  2. 3 s’écrit 00110011 et C (12) s’écrit 11001100 : (3C)16=(00111100)2=(111100)2(\text{3C})_{16} = (00111100)_2 = (111100)_2. Chaque chiffre hexadécimal doit donner exactement 4 bits, en complétant à gauche par des 0.
  3. Il faut découper en partant de la droite : 11  010111 \; 0101, ce qui donne 3 et 5, donc (35)16(\text{35})_{16}. Vérification : (110101)2=32+16+4+1=53(110101)_2 = 32 + 16 + 4 + 1 = 53 et (35)16=3×16+5=53(\text{35})_{16} = 3 \times 16 + 5 = 53. Son résultat (D1)16=209(\text{D1})_{16} = 209 est faux, car il a donné aux bits de gauche un poids trop faible.
Où rencontre-t-on la base 16 ?

En HTML, une couleur s’écrit souvent sous la forme #FF8000 : trois nombres en base 16, de 00 à FF, donnent les quantités de rouge, de vert et de bleu. Ici, rouge 255, vert 128 et bleu 0 donnent de l’orange.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Programmer les conversions

Les fonctions int, bin et hex font déjà les conversions. Les programmer soi-même oblige à comprendre exactement ce qu’elles font.

Du binaire vers le décimal

Une chaîne de caractères se parcourt comme un tuple : for chiffre in "1101": donne successivement les caractères "1", "1", "0" et "1", de gauche à droite.

Plutôt que de calculer chaque puissance de 2, on peut lire les chiffres de gauche à droite en appliquant une règle simple : à chaque nouveau chiffre, on multiplie le résultat par 2 (tout ce qui a déjà été lu monte d’une position), puis on ajoute le chiffre.

Q23.

Compléter le tableau d’évolution de la variable n lorsqu’on lit la chaîne "1101" en appliquant la règle n = 2 * n + int(chiffre), avec n égal à 0 au départ.

étape chiffre lu n
départ 0
1
2
3
4
Réponse
étape chiffre lu n
départ 0
1 "1" 2×0+1=12 \times 0 + 1 = 1
2 "1" 2×1+1=32 \times 1 + 1 = 3
3 "0" 2×3+0=62 \times 3 + 0 = 6
4 "1" 2×6+1=132 \times 6 + 1 = 13

On retrouve (1101)2=13(1101)_2 = 13. Le premier 1 lu a été multiplié trois fois par 2 : il compte bien pour 23=82^3 = 8.

Q24.

Écrire la fonction recompose dont la spécification est :

def recompose(binaire: str) -> int:
    """
    Retourne l'entier dont binaire est l'écriture en base 2.

    >>> recompose("1101")
    13
    >>> recompose("11111111")
    255
    >>> recompose("0")
    0
    """
Réponse
def recompose(binaire: str) -> int:
    n = 0
    for chiffre in binaire:
        n = 2 * n + int(chiffre)
    return n

chiffre est une chaîne d’un caractère : il faut la convertir avec int avant de l’additionner. Sans cette conversion, Python signale une erreur TypeError, car on ne peut pas additionner un entier et une chaîne.

Du décimal vers le binaire

Q25.

On veut écrire la fonction decompose, qui traduit en Python la méthode des divisions successives :

def decompose(n: int) -> str:
    """
    Retourne l'écriture en base 2 de l'entier positif n.

    >>> decompose(13)
    '1101'
    >>> decompose(42)
    '101010'
    >>> decompose(0)
    '0'
    """
  1. Le nombre de divisions n’est pas connu à l’avance. Quelle boucle faut-il utiliser ? Quelle est sa condition d’arrêt ?
  2. Chaque reste doit être placé à gauche des chiffres déjà obtenus. Si bits est la chaîne déjà construite, quelle instruction ajoute le reste n % 2 à sa gauche ?
  3. Écrire la fonction. Attention au cas n = 0.
Coup de pouce
  1. Reprendre le tableau de l’exemple résolu pour 13 : on s’arrête quand le quotient devient nul.
  2. Une chaîne se construit par concaténation avec + ; l’ordre des deux morceaux compte.
  3. Que fait la boucle quand n vaut 0 dès le départ ?
Réponse
  1. Une boucle while, puisqu’on ne sait pas d’avance combien de divisions seront nécessaires. On continue tant que n > 0.
  2. bits = str(n % 2) + bits. Écrire bits + str(n % 2) placerait les restes dans l’ordre où on les obtient, c’est-à-dire à l’envers.
  3. def decompose(n: int) -> str:
        if n == 0:
            return "0"
        bits = ""
        while n > 0:
            bits = str(n % 2) + bits
            n = n // 2
        return bits
    Lorsque n vaut 0, la condition n > 0 est fausse dès le premier test : sans le cas particulier, la fonction retournerait la chaîne vide.

Dans un ordinateur, les nombres sont rangés dans des cases de taille fixe. Une case de 8 bits s’appelle un octet. Pour écrire 13 sur un octet, on complète à gauche par des 0 : 0000110100001101. Ces 0 ne changent pas la valeur, comme 0042 vaut toujours 42.

Q26.

Écrire la fonction octet, qui doit utiliser decompose :

def octet(n: int) -> str:
    """
    Retourne l'écriture en base 2 de l'entier n sur 8 bits.
    Précondition : 0 <= n <= 255.

    >>> octet(13)
    '00001101'
    >>> octet(255)
    '11111111'
    """
Réponse
def octet(n: int) -> str:
    assert 0 <= n <= 255, "n doit être compris entre 0 et 255"
    bits = decompose(n)
    while len(bits) < 8:
        bits = "0" + bits
    return bits

On peut aussi écrire return "0" * (8 - len(bits)) + bits : l’opérateur * répète une chaîne. L’assertion vérifie la précondition ; les entiers plus grands que 255 ne tiennent pas sur un octet, comme on le verra dans le Doc. 4,2.

Vers la base 16

La méthode des divisions successives marche dans n’importe quelle base : pour la base 16, on divise par 16. Il reste une difficulté : un reste peut valoir de 0 à 15, et il faut l’écrire avec un seul chiffre. On range les seize chiffres hexadécimaux dans une chaîne, à la bonne place :

CHIFFRES = "0123456789ABCDEF"

Comme pour un tuple, CHIFFRES[13] est le caractère d’indice 13, c’est-à-dire "D".

Q27.

Écrire la fonction decompose_16 en s’inspirant de decompose :

def decompose_16(n: int) -> str:
    """
    Retourne l'écriture en base 16 de l'entier positif n.

    >>> decompose_16(42)
    '2A'
    >>> decompose_16(255)
    'FF'
    >>> decompose_16(2019)
    '7E3'
    """
Réponse
CHIFFRES = "0123456789ABCDEF"

def decompose_16(n: int) -> str:
    if n == 0:
        return "0"
    resultat = ""
    while n > 0:
        resultat = CHIFFRES[n % 16] + resultat
        n = n // 16
    return resultat

Seules trois choses changent par rapport à decompose : on divise par 16, et le reste devient un caractère grâce à CHIFFRES[n % 16] au lieu de str(n % 2).

Q28.

Sans écrire de nouvelle fonction, expliquer comment modifier decompose_16 pour obtenir l’écriture d’un entier en base 8. Quels caractères de CHIFFRES seraient alors utilisés ?

Réponse

Il suffit de remplacer 16 par 8 dans les deux divisions. Les restes vont alors de 0 à 7 : seuls les caractères "0" à "7" de CHIFFRES sont utilisés. On pourrait même écrire une seule fonction qui prend la base en paramètre.

Vérifier ses acquis 4 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • expliquer que la valeur d’un chiffre dépend de sa position, en base 10 comme en base 2 ou 16 ;
  • calculer la valeur décimale d’une écriture en base 2 ou en base 16 à l’aide des poids ;
  • écrire un entier en base 2 par la méthode des divisions successives, en lisant les restes dans le bon ordre ;
  • passer de la base 2 à la base 16, et inversement, par paquets de 4 bits ;
  • utiliser int(..., 2), int(..., 16), bin, hex et les préfixes 0b et 0x ;
  • programmer les conversions de la base 2 vers la base 10 et de la base 10 vers les bases 2 et 16.

Dans le Doc. 4,2, on se demande combien de bits il faut pour écrire un entier donné, et ce qui se passe quand un résultat ne tient plus dans la place prévue.

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Combien de bits pour un entier ?

Objectif

Savoir combien de bits il faut pour écrire un entier, une somme ou un produit, et comprendre ce qui se passe lorsqu’un résultat ne tient plus dans la place que la machine lui a réservée.

Le 4 juin 1996, la fusée Ariane 5 explose 37 secondes après son premier décollage. L’enquête montre qu’un programme de navigation a voulu ranger une vitesse dans une case mémoire de 16 bits. La valeur était trop grande pour cette case : le calculateur a produit une erreur, et la fusée a perdu le contrôle de sa trajectoire.

Q11.

Avant toute recherche : combien de nombres entiers différents peut-on écrire avec 3 bits ? Écrire toutes les possibilités. Quel est le plus grand ?

Réponse

Avec 3 bits, on peut écrire 8 nombres : 000, 001, 010, 011, 100, 101, 110 et 111, c’est-à-dire les entiers de 0 à 7. Le plus grand est (111)2=4+2+1=7(111)_2 = 4 + 2 + 1 = 7.

Ce que l’on peut écrire avec nn bits

Chaque bit a deux valeurs possibles. Ajouter un bit double donc le nombre de possibilités : à chaque écriture déjà possible, on peut ajouter un 0 ou un 1 devant. Avec 1 bit, on a 2 possibilités ; avec 2 bits, 2×2=42 \times 2 = 4 ; avec 3 bits, 2×2×2=82 \times 2 \times 2 = 8.

À retenir

Avec nn bits, on peut écrire 2n2^n nombres différents. Pour les entiers positifs, ce sont les entiers de 00 à 2n−12^n - 1.

Un octet est un groupe de 8 bits : il permet d’écrire les entiers de 0 à 28−1=2552^8 - 1 = 255.

Les processeurs manipulent les entiers dans des cases de taille fixe, le plus souvent de 8, 16, 32 ou 64 bits.

Q12.

Compléter le tableau en calculant les puissances de 2 avec Python, par exemple 2 ** 16 - 1.

taille nombre d’octets plus grand entier positif
8 bits
16 bits
32 bits
64 bits
Réponse
taille nombre d’octets plus grand entier positif
8 bits 1 28−1=2552^8 - 1 = 255
16 bits 2 216−1=65 5352^{16} - 1 = 65 \, 535
32 bits 4 232−1=4 294 967 2952^{32} - 1 = 4 \, 294 \, 967 \, 295
64 bits 8 264−1=18 446 744 073 709 551 6152^{64} - 1 = 18 \, 446 \, 744 \, 073 \, 709 \, 551 \, 615

Chaque fois qu’on double le nombre de bits, le plus grand entier est à peu près élevé au carré : le nombre de chiffres décimaux double.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Combien de bits pour écrire un entier donné ?

Pour savoir combien de bits sont nécessaires pour écrire un entier NN, on cherche la plus petite puissance de 2 strictement supérieure à NN.

Exemple résolu : combien de bits pour 614 ?

On encadre 614 entre deux puissances de 2 consécutives : 29=512≤614<1024=2102^9 = 512 \leq 614 < 1024 = 2^{10}.

Avec 9 bits, on ne peut pas dépasser 29−1=5112^9 - 1 = 511 : c’est trop peu. Avec 10 bits, on va jusqu’à 210−1=10232^{10} - 1 = 1023 : cela suffit. Il faut donc 10 bits pour écrire 614.

Q13.

Combien de bits faut-il pour écrire 255 ? 256 ? 1000 ? 2026 ? Vérifier avec Python : len(bin(2026)) - 2 donne le nombre de chiffres de l’écriture binaire de 2026. Pourquoi faut-il retirer 2 ?

Réponse
  • 27=128≤255<256=282^7 = 128 \leq 255 < 256 = 2^8 : 8 bits.
  • 28=256≤256<512=292^8 = 256 \leq 256 < 512 = 2^9 : 9 bits. Un seul de plus que 255, et il faut un bit de plus.
  • 29=512≤1000<1024=2102^9 = 512 \leq 1000 < 1024 = 2^{10} : 10 bits.
  • 210=1024≤2026<2048=2112^{10} = 1024 \leq 2026 < 2048 = 2^{11} : 11 bits.

bin(2026) retourne '0b11111101010' : les deux premiers caractères 0b ne sont pas des chiffres, il faut les retirer du compte.

Q14.

Écrire la fonction nb_bits, sans utiliser bin, en cherchant la première puissance de 2 strictement supérieure à n :

def nb_bits(n: int) -> int:
    """
    Retourne le nombre de bits nécessaires pour écrire
    l'entier n en base 2.
    Précondition : n >= 1.

    >>> nb_bits(614)
    10
    >>> nb_bits(255)
    8
    >>> nb_bits(256)
    9
    >>> nb_bits(1)
    1
    """
Coup de pouce

Utiliser deux variables : le nombre de bits k et la puissance 2 ** k. Tant que la puissance n’est pas strictement supérieure à n, on ajoute un bit.

Réponse
def nb_bits(n: int) -> int:
    assert n >= 1, "n doit être supérieur ou égal à 1"
    k = 1
    while 2 ** k <= n:
        k += 1
    return k

On part de 1 bit. Tant que 2k≤n2^k \leq n, les kk bits ne suffisent pas, et on en ajoute un. Une autre méthode consiste à compter les divisions par 2 nécessaires pour atteindre 0, comme dans la fonction decompose du Doc. 4,1.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

La taille d’une somme et d’un produit

Poser une addition en binaire

On additionne en base 2 comme en base 10, en posant l’opération et en propageant les retenues de droite à gauche. La seule différence est qu’en base 2, on obtient une retenue dès que la somme atteint 2 : 1+1=(10)21 + 1 = (10)_2, on pose 0 et on retient 1.

Exemple résolu : calculer (0110)2+(0111)2(0110)_2 + (0111)_2
retenues 1 1
0 1 1 0
++ 0 1 1 1
1 1 0 1

Colonne de droite : 0+1=10 + 1 = 1. Deuxième colonne : 1+1=(10)21 + 1 = (10)_2, on pose 0 et on retient 1. Troisième colonne : 1+1+1=(11)21 + 1 + 1 = (11)_2, on pose 1 et on retient 1. Dernière colonne : 0+0+1=10 + 0 + 1 = 1.

On vérifie en base 10 : 6+7=13=(1101)26 + 7 = 13 = (1101)_2.

Q15.

Poser les additions suivantes en binaire, puis vérifier en base 10 :

  1. (1011)2+(0110)2(1011)_2 + (0110)_2 ;
  2. (11111111)2+(00000001)2(11111111)_2 + (00000001)_2.
Réponse
  1. (1011)2+(0110)2=(10001)2(1011)_2 + (0110)_2 = (10001)_2. En base 10 : 11+6=17=16+111 + 6 = 17 = 16 + 1.
  2. (11111111)2+(00000001)2=(100000000)2(11111111)_2 + (00000001)_2 = (100000000)_2. Toutes les colonnes produisent une retenue. En base 10 : 255+1=256=28255 + 1 = 256 = 2^8. Le résultat compte 9 chiffres : il ne tient plus sur un octet.

Combien de bits pour le résultat ?

Q16.

On additionne puis on multiplie deux entiers qui tiennent chacun sur 8 bits.

  1. Quel est le plus grand résultat possible pour la somme ? pour le produit ?
  2. Combien de bits faut-il, au plus, pour écrire la somme ? pour le produit ? Utiliser la fonction nb_bits.
  3. Reprendre les mêmes questions avec deux entiers de 4 bits.
Réponse
  1. Le plus grand entier sur 8 bits est 255. La plus grande somme est 255+255=510255 + 255 = 510, le plus grand produit 255×255=65 025255 \times 255 = 65 \, 025.
  2. nb_bits(510) vaut 9 et nb_bits(65025) vaut 16. Il faut 9 bits pour la somme et 16 bits pour le produit.
  3. Le plus grand entier sur 4 bits est 15. 15+15=3015 + 15 = 30 s’écrit sur 5 bits et 15×15=22515 \times 15 = 225 sur 8 bits.
Q17.

En s’appuyant sur ces exemples, proposer une règle qui donne le nombre de bits d’une somme, puis d’un produit, de deux entiers de nn bits. Justifier la règle pour la somme.

Coup de pouce

Comparer 2×(2n−1)2 \times (2^n - 1) à 2n+12^{n+1}.

Réponse

La somme de deux entiers de nn bits tient sur n+1n + 1 bits, et leur produit sur 2n2n bits.

Justification pour la somme : chaque entier est au plus égal à 2n−12^n - 1, donc la somme est au plus égale à 2×(2n−1)=2n+1−22 \times (2^n - 1) = 2^{n+1} - 2, qui est inférieur à 2n+12^{n+1}. Elle s’écrit donc avec au plus n+1n + 1 bits. Plus généralement, la somme d’un entier de nn bits et d’un entier de mm bits tient sur max⁡(n,m)+1\max(n, m) + 1 bits, et leur produit sur n+mn + m bits.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Quand le résultat ne tient plus : le dépassement de capacité

Une case mémoire de 8 bits ne peut pas contenir de neuvième bit. Lorsqu’un calcul produit un résultat trop grand, le bit en trop est perdu : seuls les 8 bits de droite sont conservés. On parle de dépassement de capacité (en anglais overflow).

Q18.

On calcule 200+100200 + 100 avec des entiers rangés sur 8 bits.

  1. Écrire 200, 100 et 300 en base 2 avec Python.
  2. Que reste-t-il de 300 si l’on ne garde que les 8 bits de droite ? Quelle valeur la machine obtient-elle ?
  3. Vérifier que cette valeur est égale à 300 % 256. Expliquer pourquoi.
Réponse
  1. bin(200) donne '0b11001000', bin(100) donne '0b1100100' et bin(300) donne '0b100101100', qui compte 9 bits.
  2. On perd le bit de gauche, qui vaut 28=2562^8 = 256. Il reste (00101100)2=32+8+4=44(00101100)_2 = 32 + 8 + 4 = 44. La machine affirme que 200+100=44200 + 100 = 44.
  3. 300 % 256 vaut bien 44 : supprimer le bit de poids 282^8 revient à retirer 256, c’est-à-dire à prendre le reste de la division par 256.

C’est ce qui s’est passé sur Ariane 5 : la valeur à ranger dépassait la capacité d’une case de 16 bits. Ce type d’erreur ne se voit pas à la lecture du programme : il n’apparaît que pour certaines valeurs.

Q19.

Dans la console, calculer 2 ** 100, puis 2 ** 100 + 1. Python signale-t-il un dépassement de capacité ? Combien de bits faut-il pour écrire 2 ** 100 ?

Réponse
>>> 2 ** 100
1267650600228229401496703205376
>>> 2 ** 100 + 1
1267650600228229401496703205377

Python ne signale aucune erreur et le calcul est exact. Il faut 101 bits pour écrire 21002^{100}, qui s’écrit 1 suivi de cent 0 en base 2.

En Python, les entiers sont de taille arbitraire : Python utilise autant de bits qu’il en faut, tant que la mémoire de l’ordinateur le permet. Ce n’est pas le cas de la plupart des langages, ni du processeur lui-même, qui travaille sur des cases de 32 ou 64 bits.

Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Ajouter ou retirer un zéro à droite

En base 10, ajouter un 0 à droite d’un nombre le multiplie par 10 : 42 devient 420.

Q20.
  1. Que vaut (1101)2(1101)_2 ? Que vaut (11010)2(11010)_2, obtenu en ajoutant un 0 à droite ?
  2. Prévoir ce que donne l’ajout de trois 0 à droite. Vérifier avec int("1101000", 2).
  3. Que se passe-t-il quand on retire le chiffre de droite de (1101)2(1101)_2 ? Quelle opération Python donne directement ce résultat ?
Réponse
  1. (1101)2=13(1101)_2 = 13 et (11010)2=16+8+2=26(11010)_2 = 16 + 8 + 2 = 26 : ajouter un 0 à droite multiplie par 2, car chaque chiffre monte d’une position et voit son poids doubler.
  2. Trois 0 multiplient par 23=82^3 = 8 : 13×8=10413 \times 8 = 104, et int("1101000", 2) vaut bien 104.
  3. On obtient (110)2=6(110)_2 = 6 : retirer le chiffre de droite revient au quotient de la division par 2. En Python, 13 // 2 vaut 6. C’est exactement le calcul effectué à chaque étape de la méthode des divisions successives.

Ces opérations s’appellent des décalages : décaler vers la gauche de kk positions multiplie par 2k2^k, et décaler vers la droite divise par 2k2^k (division entière). Les processeurs les effectuent beaucoup plus vite qu’une multiplication quelconque.

Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • expliquer qu’avec nn bits on écrit 2n2^n nombres, les entiers de 00 à 2n−12^n - 1 ;
  • citer les tailles courantes des entiers (8, 16, 32 et 64 bits) et le plus grand entier positif d’un octet ;
  • déterminer le nombre de bits nécessaires pour écrire un entier, à la main et avec une fonction ;
  • poser une addition en binaire en propageant les retenues ;
  • évaluer le nombre de bits d’une somme (n+1n + 1) et d’un produit (2n2n) de deux entiers de nn bits ;
  • expliquer ce qu’est un dépassement de capacité et calculer le résultat obtenu par la machine ;
  • savoir que les entiers de Python sont de taille arbitraire ;
  • multiplier ou diviser par une puissance de 2 en décalant l’écriture binaire.

Dans le Doc. 4,3, on se demande comment écrire un entier négatif avec seulement des 0 et des 1. L’addition binaire et le dépassement de capacité y joueront un rôle inattendu.

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Représenter les entiers relatifs

Objectif

Comprendre comment un ordinateur écrit un entier négatif avec seulement des 0 et des 1, et utiliser pour cela le complément à 2.

Q13.

La mémoire d’un ordinateur ne contient que des 0 et des 1 : il n’y a pas de case pour le signe « −- ». Proposer une idée pour écrire −5-5 sur 4 bits.

Réponse

L’idée la plus fréquente consiste à réserver un bit pour le signe : par exemple 0 pour « positif » et 1 pour « négatif », suivi de l’écriture binaire de 5. Sur 4 bits, cela donne 11011101 : un bit de signe, puis 101101. C’est l’idée étudiée dans la première partie. Toute autre proposition cohérente est acceptable à ce stade.

Une fausse bonne idée : le bit de signe

Essayons l’idée la plus naturelle. Sur 4 bits, on réserve le bit de gauche au signe (0 pour un nombre positif, 1 pour un nombre négatif) et les 3 autres bits à la valeur absolue. Ainsi, +3+3 s’écrit 00110011 et −3-3 s’écrit 10111011.

Q14.

Avec cette convention sur 4 bits :

  1. Écrire +5+5 et −5-5.
  2. Écrire +0+0 et −0-0. Que remarque-t-on ?
  3. Poser l’addition binaire des écritures de +5+5 et de −3-3, en ne gardant que 4 bits. Quel nombre obtient-on ? Quel nombre devrait-on obtenir ?
Réponse
  1. +5+5 s’écrit 01010101 et −5-5 s’écrit 11011101.
  2. +0+0 s’écrit 00000000 et −0-0 s’écrit 10001000 : le nombre zéro a deux écritures différentes. Il faudrait que la machine sache que ces deux codes représentent le même nombre, par exemple pour tester une égalité.
  3. 0101+1011=100000101 + 1011 = 10000 ; en gardant 4 bits, il reste 00000000, c’est-à-dire 0. Or 5+(−3)=25 + (-3) = 2, qui devrait s’écrire 00100010. L’addition binaire que l’on sait poser ne fonctionne plus.

Cette convention aurait donc un coût : il faudrait un circuit électronique pour additionner les nombres positifs et un autre, plus compliqué, pour les nombres de signes différents. On cherche une écriture des entiers négatifs avec laquelle l’addition binaire ordinaire donne directement le bon résultat.

Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

L’idée du compteur kilométrique

Un vieux compteur kilométrique de voiture n’affiche que 4 chiffres. Lorsqu’il indique 9999 et que la voiture parcourt encore un kilomètre, il affiche 0000 : le chiffre 1 de 10000 n’a pas de place pour s’afficher. C’est le dépassement de capacité du Doc. 4,2.

Q15.

Sur ce compteur à 4 chiffres, quel nombre faut-il ajouter à 0001 pour revenir à 0000 ? Quel nombre « joue le rôle » de −1-1 ? Et de −2-2 ?

Réponse

0001+9999=100000001 + 9999 = 10000, qui s’affiche 0000. Sur ce compteur, ajouter 9999 revient à retirer 1 : 9999 joue le rôle de −1-1. De même, 9998 joue le rôle de −2-2, puisque 0002+99980002 + 9998 s’affiche 0000.

Une case de 4 bits se comporte exactement comme ce compteur, mais en base 2. Après 11111111 vient 00000000, car (1111)2+1=(10000)2(1111)_2 + 1 = (10000)_2 et le cinquième bit est perdu. On peut donc décider que l’écriture de −1-1 est celle qui, ajoutée à 00010001, donne 00000000.

Q16.
  1. Quelle écriture sur 4 bits, ajoutée à 00010001, donne 00000000 (en perdant la retenue finale) ? Quel entier positif représente-t-elle habituellement ?
  2. Même question pour l’écriture de −2-2, qui ajoutée à 00100010 doit donner 00000000.
  3. En observant ces deux exemples, quel entier positif pp faut-il écrire pour représenter un entier négatif −x-x sur 4 bits ? Compléter le tableau.
entier −1-1 −2-2 −3-3 −4-4 −5-5 −6-6 −7-7 −8-8
entier positif pp
écriture sur 4 bits
Coup de pouce

Sur le compteur kilométrique, −1-1 était représenté par 10000−110000 - 1. Sur 4 bits, le rôle de 1000010000 est joué par (10000)2=24=16(10000)_2 = 2^4 = 16.

Réponse
  1. 11111111, car 0001+1111=100000001 + 1111 = 10000, qui donne 00000000 sur 4 bits. Habituellement, 11111111 représente 15.
  2. 11101110, car 0010+1110=100000010 + 1110 = 10000. Habituellement, 11101110 représente 14.
  3. On écrit p=16−xp = 16 - x, c’est-à-dire 24−x2^4 - x :
entier −1-1 −2-2 −3-3 −4-4 −5-5 −6-6 −7-7 −8-8
entier positif pp 15 14 13 12 11 10 9 8
écriture sur 4 bits 1111 1110 1101 1100 1011 1010 1001 1000
Q17.

Avec cette nouvelle convention, poser l’addition des écritures de 55 et de −3-3 sur 4 bits, en perdant la retenue finale. Le résultat est-il juste ?

Réponse

55 s’écrit 01010101 et −3-3 s’écrit 11011101. 0101+1101=100100101 + 1101 = 10010, et il reste 00100010 sur 4 bits, c’est-à-dire 2. Le résultat est juste : l’addition binaire ordinaire fonctionne, sans aucun circuit supplémentaire.

On écrit donc les entiers positifs de 0 à 7 comme d’habitude, de 00000000 à 01110111, et les entiers négatifs de −8-8 à −1-1 par les écritures de 10001000 à 11111111. On remarque que le bit de gauche, appelé bit de poids fort, vaut 0 pour les entiers positifs ou nuls et 1 pour les entiers négatifs. On retrouve l’idée du bit de signe, mais sans ses défauts : zéro n’a qu’une seule écriture, 00000000.

À retenir

Sur nn bits, on peut écrire les entiers relatifs compris entre −2n−1-2^{n-1} et 2n−1−12^{n-1} - 1 :

  • un entier xx positif ou nul (0≤x≤2n−1−10 \leq x \leq 2^{n-1} - 1) s’écrit comme d’habitude ;
  • un entier −x-x négatif (1≤x≤2n−11 \leq x \leq 2^{n-1}) s’écrit comme l’entier positif 2n−x2^n - x.

Le bit de poids fort vaut 1 pour les entiers négatifs et 0 pour les autres. Sur 8 bits, on écrit les entiers de −128-128 à 127127.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Le complément à 2 : une méthode rapide

Calculer 2n−x2^n - x puis le convertir en binaire est un peu long. On observe sur le tableau de la partie précédente une méthode plus rapide, que l’on appelle le complément à 2.

Exemple résolu : écrire −5 sur 8 bits
  1. On écrit la valeur absolue 5 sur 8 bits : 0000010100000101.
  2. On inverse tous les bits (les 0 deviennent des 1 et les 1 des 0). On obtient le complément à 1 : 1111101011111010.
  3. On ajoute 1 : 11111010+1=1111101111111010 + 1 = 11111011.

On vérifie avec la règle de la partie précédente : 28−5=2512^8 - 5 = 251, et 251=128+64+32+16+8+2+1=(11111011)2251 = 128 + 64 + 32 + 16 + 8 + 2 + 1 = (11111011)_2.

Q18.

Écrire sur 8 bits, à l’aide du complément à 2 : −1-1, −56-56 et −128-128. Vérifier chaque résultat en calculant 28−x2^8 - x.

Réponse
  • −1-1 : 0000000100000001, inversé 1111111011111110, plus 1 : 1111111111111111. Vérification : 256−1=255=(11111111)2256 - 1 = 255 = (11111111)_2.
  • −56-56 : 56=32+16+856 = 32 + 16 + 8 s’écrit 0011100000111000, inversé 1100011111000111, plus 1 : 1100100011001000. Vérification : 256−56=200=128+64+8256 - 56 = 200 = 128 + 64 + 8.
  • −128-128 : 128128 s’écrit 1000000010000000, inversé 0111111101111111, plus 1 : 1000000010000000. Vérification : 256−128=128256 - 128 = 128. Le complément à 2 de 1000000010000000 est lui-même : −128-128 n’a pas d’opposé sur 8 bits, puisque +128+128 ne s’y écrit pas.

Pour lire un octet qui commence par 1, on applique la même méthode : le complément à 2 d’un entier négatif donne l’écriture de sa valeur absolue.

Q19.

Quels entiers relatifs les octets suivants représentent-ils ? 0111111101111111, 1111000011110000 et 1000000110000001.

Réponse
  • 0111111101111111 commence par 0 : c’est un entier positif, 64+32+16+8+4+2+1=12764 + 32 + 16 + 8 + 4 + 2 + 1 = 127.
  • 1111000011110000 commence par 1 : il est négatif. Inversé : 0000111100001111, plus 1 : 00010000=1600010000 = 16. Il représente −16-16.
  • 1000000110000001 commence par 1. Inversé : 0111111001111110, plus 1 : 01111111=12701111111 = 127. Il représente −127-127.
Q20.

Un élève affirme que −5-5 s’écrit 1000010110000101 sur 8 bits, « parce que le 1 de gauche indique le signe ». Expliquer son erreur en calculant la somme de son écriture et de celle de 55.

Réponse

Il utilise le bit de signe de la partie 1. Avec son écriture, 00000101+10000101=1000101000000101 + 10000101 = 10001010, qui n’est pas 0000000000000000 : la somme de 55 et de son « opposé » ne donne pas 0. Avec le complément à 2, 00000101+11111011=10000000000000101 + 11111011 = 100000000, et il reste bien 0000000000000000 sur 8 bits. Le bit de poids fort indique le signe, mais les autres bits ne sont pas ceux de la valeur absolue.

Q21.

Écrire −5-5 sur 4 bits puis sur 8 bits. Pourquoi faut-il toujours préciser le nombre de bits avant de parler de complément à 2 ?

Réponse

Sur 4 bits, −5-5 s’écrit 10111011 ; sur 8 bits, 1111101111111011. Le même entier n’a pas la même écriture : on calcule 24−5=112^4 - 5 = 11 dans un cas, 28−5=2512^8 - 5 = 251 dans l’autre. Inversement, l’écriture 10111011 représente −5-5 sur 4 bits, mais 1111 si on la lit comme l’octet 0000101100001011. Une écriture binaire ne veut rien dire tant qu’on n’a pas précisé le nombre de bits et la convention utilisée.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Programmer le complément à 2

Les fonctions suivantes, écrites dans le Doc. 4,1, sont à recopier en tête du programme :

def decompose(n: int) -> str:
    if n == 0:
        return "0"
    bits = ""
    while n > 0:
        bits = str(n % 2) + bits
        n = n // 2
    return bits

def octet(n: int) -> str:
    bits = decompose(n)
    while len(bits) < 8:
        bits = "0" + bits
    return bits

def recompose(binaire: str) -> int:
    n = 0
    for chiffre in binaire:
        n = 2 * n + int(chiffre)
    return n
Q22.

Écrire la fonction complement_a_1, qui inverse tous les bits d’une chaîne :

def complement_a_1(bits: str) -> str:
    """
    Retourne la chaîne obtenue en remplaçant chaque 0 de bits
    par 1 et chaque 1 par 0.

    >>> complement_a_1("00000101")
    '11111010'
    >>> complement_a_1("1011")
    '0100'
    """
Réponse
def complement_a_1(bits: str) -> str:
    resultat = ""
    for bit in bits:
        if bit == "0":
            resultat = resultat + "1"
        else:
            resultat = resultat + "0"
    return resultat

On parcourt la chaîne bit par bit, et on construit le résultat dans le même ordre, en ajoutant à droite.

Ajouter 1 à une chaîne binaire demande de propager des retenues : on le programmera dans le Doc. 4,4. Pour l’instant, on utilise la règle de la partie 2 : sur 8 bits, l’entier négatif −x-x s’écrit comme l’entier positif 28−x2^8 - x.

Q23.

Écrire la fonction relatif_vers_octet, qui doit utiliser la fonction octet :

def relatif_vers_octet(n: int) -> str:
    """
    Retourne l'écriture sur 8 bits de l'entier relatif n,
    en complément à 2.
    Précondition : -128 <= n <= 127.

    >>> relatif_vers_octet(5)
    '00000101'
    >>> relatif_vers_octet(-5)
    '11111011'
    >>> relatif_vers_octet(-128)
    '10000000'
    """
Réponse
def relatif_vers_octet(n: int) -> str:
    assert -128 <= n <= 127, "n doit être compris entre -128 et 127"
    if n >= 0:
        return octet(n)
    else:
        return octet(2 ** 8 + n)

Si n vaut −5-5, alors 2 ** 8 + n vaut 256−5=251256 - 5 = 251 : on écrit bien 28−x2^8 - x avec x=5x = 5. Erreur fréquente : écrire 2 ** 8 - n, qui donne 261261 car n est déjà négatif.

Q24.

Écrire la fonction octet_vers_relatif, qui fait le travail inverse. Choisir la méthode : on peut utiliser recompose et la règle 28−x2^8 - x, ou complement_a_1.

def octet_vers_relatif(bits: str) -> int:
    """
    Retourne l'entier relatif écrit sur 8 bits par bits,
    en complément à 2.

    >>> octet_vers_relatif("01111111")
    127
    >>> octet_vers_relatif("11110000")
    -16
    >>> octet_vers_relatif("10000000")
    -128
    """
Coup de pouce

Commencer par regarder le bit de poids fort bits[0]. S’il vaut "1", l’octet lu comme un entier positif vaut p=28−xp = 2^8 - x : comment retrouver −x-x à partir de pp ?

Réponse
def octet_vers_relatif(bits: str) -> int:
    p = recompose(bits)
    if bits[0] == "1":
        return p - 2 ** 8
    else:
        return p

Si p=28−xp = 2^8 - x, alors −x=p−28-x = p - 2^8. Pour "11110000", p=240p = 240 et 240−256=−16240 - 256 = -16. Avec le complément à 1, on écrirait -(recompose(complement_a_1(bits)) + 1) dans le cas négatif.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • expliquer pourquoi un simple bit de signe ne convient pas (deux zéros, addition fausse) ;
  • écrire un entier négatif sur nn bits comme l’entier positif 2n−x2^n - x ;
  • utiliser le complément à 2 (inverser les bits, puis ajouter 1) pour écrire un entier négatif ou pour lire un octet qui commence par 1 ;
  • donner la plage des entiers relatifs écrits sur nn bits, de −2n−1-2^{n-1} à 2n−1−12^{n-1} - 1, et en particulier de −128-128 à 127127 sur 8 bits ;
  • expliquer pourquoi il faut toujours préciser le nombre de bits ;
  • programmer le complément à 1 et les conversions entre un entier relatif et son octet.

Dans le Doc. 4,4, on programme l’addition de deux octets. On pourra alors ajouter 1 à un complément à 1, et vérifier que l’addition fonctionne aussi pour les entiers négatifs.

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Booléens et addition binaire

Objectif

Dresser la table de vérité d’une expression booléenne, découvrir le ou exclusif, et s’en servir pour programmer l’addition binaire de deux octets, comme le fait un circuit du processeur.

Q12.

Un processeur additionne deux bits aa et bb. Combien de cas différents peut-il rencontrer ? Pour chacun, écrire le résultat de a+ba + b en base 2. Combien de bits faut-il pour écrire ce résultat ?

Réponse

Il y a quatre cas : 0+0=00 + 0 = 0, 0+1=10 + 1 = 1, 1+0=11 + 0 = 1 et 1+1=(10)21 + 1 = (10)_2. Le dernier résultat demande deux bits : un chiffre des unités, appelé somme, et une retenue. Un circuit d’addition doit donc produire deux bits de sortie à partir de deux bits d’entrée.

Tables de vérité

Un bit et un booléen sont deux façons de voir la même information : 1 correspond à True (vrai) et 0 à False (faux). En Python, int(True) vaut 1 et bool(0) vaut False.

Les opérateurs and, or et not ont été rencontrés dans le Doc. 2,3. Une expression booléenne qui dépend de deux variables aa et bb ne peut prendre que quatre combinaisons de valeurs d’entrée. On peut donc décrire complètement son comportement dans un tableau qui donne sa valeur pour chaque combinaison : sa table de vérité.

Exemple résolu : table de vérité de « a and b »

On écrit toutes les combinaisons des entrées, dans l’ordre où l’on compte en binaire (00, 01, 10, 11), puis la valeur de l’expression :

aa bb a and b
0 0 0
0 1 0
1 0 0
1 1 1

a and b n’est vrai que si les deux entrées sont vraies.

Python peut produire ces tables à l’aide de deux boucles imbriquées :

for a in (False, True):
    for b in (False, True):
        print(int(a), int(b), int(a and b))
Q13.
  1. Dresser à la main la table de vérité de a or b et celle de not a.
  2. Vérifier la table de a or b en modifiant le programme ci-dessus.
Réponse
  1. Tables de a or b et de not a :

    aa bb a or b
    0 0 0
    0 1 1
    1 0 1
    1 1 1
    aa not a
    0 1
    1 0

    a or b est vrai dès qu’au moins une des entrées est vraie.

  2. Il suffit de remplacer a and b par a or b dans le print.

Q14.

Dresser les tables de vérité de not (a and b) et de (not a) or (not b). Que constate-t-on ? Reformuler ce résultat par une phrase en français, en partant de : « Il est faux que aa et bb soient tous les deux vrais… ».

Réponse
aa bb not (a and b) (not a) or (not b)
0 0 1 1
0 1 1 1
1 0 1 1
1 1 0 0

Les deux tables sont identiques : les deux expressions sont équivalentes. « Il est faux que aa et bb soient tous les deux vrais » signifie « au moins l’un des deux est faux ». Cette équivalence est une des lois de De Morgan. Erreur fréquente : croire que not (a and b) équivaut à (not a) and (not b), qui ne vaut 1 que sur la première ligne.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Le ou exclusif

Dans la langue courante, « ou » a deux sens. « Fromage ou dessert » au restaurant signifie qu’on ne peut pas avoir les deux. L’opérateur or de Python, lui, est vrai aussi quand les deux entrées sont vraies : c’est un ou inclusif.

Le ou exclusif, noté xor (de l’anglais exclusive or), est vrai lorsqu’une seule des deux entrées est vraie, mais pas les deux.

Q15.
  1. Dresser la table de vérité du ou exclusif.
  2. Pour deux booléens, le ou exclusif peut s’écrire a != b. Expliquer pourquoi.
  3. Écrire une expression qui donne le ou exclusif en n’utilisant que and, or et not. Vérifier sa table de vérité avec Python.
Coup de pouce

Traduire mot à mot : « aa ou bb est vrai, et il est faux que aa et bb soient vrais tous les deux ».

Réponse
  1. aa bb aa xor bb
    0 0 0
    0 1 1
    1 0 1
    1 1 0
  2. Le ou exclusif est vrai exactement quand les deux entrées sont différentes, c’est-à-dire quand a != b.
  3. (a or b) and not (a and b). On peut aussi écrire (a and not b) or (not a and b). On vérifie avec :
    for a in (False, True):
        for b in (False, True):
            print(int(a), int(b), int((a or b) and not (a and b)))

En Python, l’opérateur ^ calcule le ou exclusif de deux entiers égaux à 0 ou 1 : 1 ^ 1 vaut 0 et 1 ^ 0 vaut 1.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Additionner deux bits avec des opérateurs booléens

Q16.

Compléter la table de l’addition de deux bits aa et bb, en séparant le résultat en deux bits : la somme (chiffre des unités) et la retenue. Comparer les deux colonnes de sortie aux tables de vérité déjà rencontrées.

aa bb somme retenue
0 0
0 1
1 0
1 1
Réponse
aa bb somme retenue
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

La colonne « somme » est la table du ou exclusif, et la colonne « retenue » est celle de and : somme =a= a xor bb et retenue =a= a and bb. Un circuit qui réalise ces deux opérations s’appelle un demi-additionneur.

Pour additionner deux nombres de plusieurs bits, chaque colonne reçoit en plus la retenue rr venue de la colonne de droite. Il faut donc additionner trois bits. On peut démontrer que :

  • la somme vaut aa xor bb xor rr ;
  • la retenue sortante vaut 1 lorsqu’au moins deux des trois bits valent 1.
Q17.

Vérifier ces deux règles sur la ligne a=1a = 1, b=1b = 1, r=1r = 1, puis sur la ligne a=1a = 1, b=0b = 0, r=1r = 1, en comparant avec le calcul a+b+ra + b + r écrit en base 2.

Réponse
  • 1+1+1=3=(11)21 + 1 + 1 = 3 = (11)_2 : somme 1, retenue 1. Règles : 11 xor 1=01 = 0, puis 00 xor 1=11 = 1 ; trois bits valent 1, donc retenue 1. C’est bien le cas.
  • 1+0+1=2=(10)21 + 0 + 1 = 2 = (10)_2 : somme 0, retenue 1. Règles : 11 xor 0=10 = 1, puis 11 xor 1=01 = 0 ; deux bits valent 1, donc retenue 1. C’est bien le cas.
Q18.

Écrire la fonction additionne_bits, qui retourne un tuple :

def additionne_bits(a: int, b: int, r: int) -> tuple[int, int]:
    """
    Retourne la somme et la retenue de l'addition des trois
    bits a, b et r (chacun égal à 0 ou à 1).

    >>> additionne_bits(0, 1, 0)
    (1, 0)
    >>> additionne_bits(1, 1, 0)
    (0, 1)
    >>> additionne_bits(1, 1, 1)
    (1, 1)
    """
Réponse
def additionne_bits(a: int, b: int, r: int) -> tuple[int, int]:
    somme = a ^ b ^ r
    if a + b + r >= 2:
        retenue = 1
    else:
        retenue = 0
    return (somme, retenue)

On accepte aussi somme = (a + b + r) % 2 et retenue = (a + b + r) // 2 : ce sont le chiffre des unités et le quotient de la division par 2, comme dans la méthode des divisions successives.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Additionner deux octets

On additionne deux octets comme on pose l’addition à la main (Doc. 4,2) : de la droite vers la gauche, en reportant la retenue d’une colonne sur la suivante. La retenue qui sort de la colonne de gauche est perdue, puisque le résultat est rangé sur 8 bits.

Pour parcourir les indices de droite à gauche, on utilise range avec trois arguments : range(7, -1, -1) produit 7, 6, 5, …, 0.

Q19.

Écrire la fonction addition, qui doit utiliser additionne_bits :

def addition(bits1: str, bits2: str) -> str:
    """
    Retourne la somme sur 8 bits des octets bits1 et bits2.
    La retenue finale est perdue.

    >>> addition("00000110", "00000111")
    '00001101'
    >>> addition("11111111", "00000001")
    '00000000'
    """
Coup de pouce
  1. Avant la boucle : un résultat vide et une retenue nulle.
  2. Dans la boucle, pour l’indice i : convertir bits1[i] et bits2[i] en entiers, appeler additionne_bits, déballer le tuple obtenu.
  3. Chaque nouveau chiffre se place à gauche du résultat déjà construit.
Réponse
def addition(bits1: str, bits2: str) -> str:
    resultat = ""
    retenue = 0
    for i in range(7, -1, -1):
        somme, retenue = additionne_bits(int(bits1[i]), int(bits2[i]), retenue)
        resultat = str(somme) + resultat
    return resultat

Le déballage somme, retenue = ... met à jour la retenue, qui servira à la colonne suivante. À la fin de la boucle, la dernière retenue n’est écrite nulle part : c’est le dépassement de capacité du Doc. 4,2. Erreur fréquente : écrire resultat + str(somme), qui donne le résultat à l’envers.

Q20.

Dans le Doc. 4,3, 55 s’écrit 0000010100000101 et −5-5 s’écrit 1111101111111011 sur 8 bits.

  1. Prévoir le résultat de addition("00000101", "11111011"), puis vérifier.
  2. Calculer addition("00000011", "11111011"). Quel entier relatif ce résultat représente-t-il ? Le calcul est-il juste ?
Réponse
  1. Le résultat est '00000000' : la retenue finale est perdue, et 5+(−5)=05 + (-5) = 0.
  2. Le résultat est '11111110'. Il commence par 1 : complément à 1 00000001, plus 1 : 00000010, donc il représente −2-2. Et 3+(−5)=−23 + (-5) = -2 : la même fonction additionne correctement les entiers positifs et les entiers négatifs écrits en complément à 2. C’est la raison pour laquelle les ordinateurs utilisent cette représentation.
Q21.

Recopier la fonction complement_a_1 du Doc. 4,3, puis écrire en une ligne la fonction complement_a_2 :

def complement_a_2(bits: str) -> str:
    """
    Retourne le complément à 2 de l'octet bits.

    >>> complement_a_2("00000101")
    '11111011'
    >>> complement_a_2("11111011")
    '00000101'
    """
Réponse
def complement_a_1(bits: str) -> str:
    resultat = ""
    for bit in bits:
        if bit == "0":
            resultat = resultat + "1"
        else:
            resultat = resultat + "0"
    return resultat

def complement_a_2(bits: str) -> str:
    return addition(complement_a_1(bits), "00000001")

Le deuxième exemple montre que le complément à 2 du complément à 2 redonne l’octet de départ : l’opposé de −5-5 est bien 55.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Un détail qui compte : l’évaluation séquentielle

Dans le Doc. 2,3, on a vu que Python évalue a and b de gauche à droite et s’arrête dès que le résultat est connu : si a est faux, b n’est même pas évalué. De même, si a est vrai, a or b est vrai sans que b soit évalué. La table de vérité ne dit rien de cet ordre, mais il change le comportement d’un programme.

Q22.

On exécute x = 0 dans la console. Prévoir le résultat de chacune des deux expressions, puis vérifier :

>>> x != 0 and 10 / x > 1
>>> 10 / x > 1 and x != 0

D’après leurs tables de vérité, ces deux expressions devraient être équivalentes. Pourquoi ne le sont-elles pas dans un programme ?

Réponse
>>> x != 0 and 10 / x > 1
False
>>> 10 / x > 1 and x != 0
ZeroDivisionError: division by zero

Dans la première expression, x != 0 est faux : Python n’évalue pas 10 / x et retourne False. Dans la seconde, Python commence par 10 / x et la division par zéro provoque une erreur avant que la condition x != 0 soit examinée. Les tables de vérité décrivent les valeurs, pas l’ordre des calculs : on place en premier la condition qui protège la seconde.

Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • associer les bits 0 et 1 aux booléens False et True ;
  • dresser la table de vérité d’une expression booléenne, à la main et avec deux boucles imbriquées ;
  • reconnaître deux expressions équivalentes en comparant leurs tables de vérité ;
  • définir le ou exclusif et l’écrire avec !=, ^ ou les opérateurs and, or et not ;
  • expliquer que la somme de deux bits est un ou exclusif et la retenue un and ;
  • programmer l’addition de deux octets en propageant la retenue, et constater qu’elle fonctionne aussi en complément à 2 ;
  • expliquer pourquoi l’ordre des opérandes de and et de or peut éviter une erreur.

Dans le Doc. 4,5, on quitte les entiers pour les nombres à virgule, et on découvre pourquoi 0.1 + 0.2 n’est pas égal à 0.3.

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Les nombres flottants

Objectif

Comprendre pourquoi un ordinateur ne peut écrire la plupart des nombres à virgule que de façon approchée, et en tirer une règle de programmation : ne jamais tester l’égalité de deux flottants.

Q12.

Sans utiliser l’ordinateur, prévoir ce qu’affiche Python pour l’instruction 0.1 + 0.2 == 0.3. Vérifier ensuite dans la console, puis afficher 0.1 + 0.2.

Réponse
>>> 0.1 + 0.2 == 0.3
False
>>> 0.1 + 0.2
0.30000000000000004

Presque tout le monde prévoit True. Le résultat n’est pas une erreur de Python : il vient de la façon dont l’ordinateur écrit 0,1 et 0,2. Cette activité explique pourquoi.

Les nombres à virgule sont représentés en Python par le type float. Le mot vient de l’anglais floating point, « virgule flottante ». Pour comprendre ce qui se passe, il faut d’abord savoir écrire un nombre à virgule en base 2.

Des chiffres après la virgule en base 2

En base 10, les chiffres après la virgule ont pour poids 10−1=1/1010^{-1} = 1/10, 10−2=1/10010^{-2} = 1/100, etc. : 0,375=3/10+7/100+5/1000\text{0,375} = 3/10 + 7/100 + 5/1000.

En base 2, on prolonge de la même façon les poids vers la droite de la virgule, en divisant chaque fois par 2 :

poids 212^1 202^0 , 2−12^{-1} 2−22^{-2} 2−32^{-3}
valeur 2 1 , 1/2=0,51/2 = \text{0,5} 1/4=0,251/4 = \text{0,25} 1/8=0,1251/8 = \text{0,125}

Par exemple, (0,101)2=1/2+0/4+1/8=0,5+0,125=0,625(\text{0,101})_2 = 1/2 + 0/4 + 1/8 = \text{0,5} + \text{0,125} = \text{0,625}.

Q13.

Calculer la valeur décimale de (0,11)2(\text{0,11})_2, de (0,01)2(\text{0,01})_2 et de (10,1)2(\text{10,1})_2.

Réponse
  • (0,11)2=0,5+0,25=0,75(\text{0,11})_2 = \text{0,5} + \text{0,25} = \text{0,75}.
  • (0,01)2=0,25(\text{0,01})_2 = \text{0,25}.
  • (10,1)2=2+0,5=2,5(\text{10,1})_2 = 2 + \text{0,5} = \text{2,5}.
Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Écrire un nombre à virgule en base 2

Pour la partie entière, on utilise la méthode des divisions successives (Doc. 4,1). Pour la partie après la virgule, on fait l’inverse : on multiplie par 2. Chaque multiplication fait passer un chiffre binaire devant la virgule.

Exemple résolu : écrire 0,625 en base 2

On multiplie par 2. La partie entière du résultat donne le chiffre suivant ; on continue avec la partie après la virgule :

calcul chiffre obtenu on continue avec
0,625×2=1,25\text{0,625} \times 2 = \text{1,25} 1 0,25\text{0,25}
0,25×2=0,5\text{0,25} \times 2 = \text{0,5} 0 0,5\text{0,5}
0,5×2=1\text{0,5} \times 2 = 1 1 00 : on s’arrête

Les chiffres se lisent cette fois de haut en bas : 0,625=(0,101)2\text{0,625} = (\text{0,101})_2. On retrouve le résultat de la partie 1.

Q14.

Écrire 0,25\text{0,25} puis 0,75\text{0,75} en base 2 par la méthode des multiplications successives.

Réponse
  • 0,25×2=0,5\text{0,25} \times 2 = \text{0,5} (0), puis 0,5×2=1\text{0,5} \times 2 = 1 (1) : 0,25=(0,01)2\text{0,25} = (\text{0,01})_2.
  • 0,75×2=1,5\text{0,75} \times 2 = \text{1,5} (1), puis 0,5×2=1\text{0,5} \times 2 = 1 (1) : 0,75=(0,11)2\text{0,75} = (\text{0,11})_2.
Q15.

Appliquer la méthode à 0,1\text{0,1}. Effectuer au moins six multiplications. Que remarque-t-on ?

Coup de pouce

Après quelques étapes, on retombe sur un nombre déjà rencontré. Que va-t-il se passer ensuite ?

Réponse
calcul chiffre on continue avec
0,1×2=0,2\text{0,1} \times 2 = \text{0,2} 0 0,2\text{0,2}
0,2×2=0,4\text{0,2} \times 2 = \text{0,4} 0 0,4\text{0,4}
0,4×2=0,8\text{0,4} \times 2 = \text{0,8} 0 0,8\text{0,8}
0,8×2=1,6\text{0,8} \times 2 = \text{1,6} 1 0,6\text{0,6}
0,6×2=1,2\text{0,6} \times 2 = \text{1,2} 1 0,2\text{0,2}
0,2×2=0,4\text{0,2} \times 2 = \text{0,4} 0 0,4\text{0,4}

On retombe sur 0,2\text{0,2}, déjà rencontré à la deuxième ligne : les calculs vont se répéter sans fin. On obtient 0,1=(0,000110011001100...)2\text{0,1} = (\text{0,000110011001100}...)_2, avec le motif 00110011 répété indéfiniment. L’écriture de 0,1\text{0,1} en base 2 est infinie, alors qu’elle est très courte en base 10.

Q16.

En base 10, on sait déjà qu’un nombre simple peut avoir une écriture infinie : 1/3=0,333...1/3 = \text{0,333}...

  1. Écrire 1/31/3 en base 2 en partant de 1/3×2=2/31/3 \times 2 = 2/3. Travailler avec des fractions.
  2. Proposer une explication : pourquoi 0,25\text{0,25} et 0,625\text{0,625} ont-ils une écriture finie en base 2, mais pas 0,1\text{0,1} ?
Réponse
  1. 1/3×2=2/31/3 \times 2 = 2/3 (0), 2/3×2=4/3=1+1/32/3 \times 2 = 4/3 = 1 + 1/3 (1), puis on retombe sur 1/31/3 : 1/3=(0,010101...)21/3 = (\text{0,010101}...)_2, écriture infinie.
  2. 0,25=1/4\text{0,25} = 1/4 et 0,625=5/8\text{0,625} = 5/8 : ce sont des fractions dont le dénominateur est une puissance de 2. En les multipliant plusieurs fois par 2, on finit par tomber sur un entier, et l’algorithme s’arrête. 0,1=1/10\text{0,1} = 1/10 a un dénominateur qui contient le facteur 5 : multiplier par 2 ne peut pas faire disparaître ce facteur, et la partie après la virgule ne devient jamais nulle. C’est la même raison qui rend 1/31/3 infini en base 10 : 3 ne divise aucune puissance de 10.
Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Ce que l’ordinateur range vraiment

Un flottant Python est rangé sur 64 bits. Le nombre est écrit en base 2 sous une forme qui rappelle l’écriture scientifique : des chiffres significatifs, appelés mantisse, multipliés par une puissance de 2. Le nombre de chiffres de la mantisse est limité. Une écriture binaire infinie, comme celle de 0,1\text{0,1}, doit donc être coupée : l’ordinateur range le nombre le plus proche de 0,1\text{0,1} qu’il sait écrire, mais pas 0,1\text{0,1} lui-même.

Q17.

Python arrondit l’affichage des flottants pour qu’il soit lisible. On peut demander davantage de chiffres avec une f-string (Doc. 2,2). Exécuter :

>>> f"{0.1:.20f}"
>>> f"{0.25:.20f}"
>>> f"{0.1 + 0.2:.20f}"
>>> f"{0.3:.20f}"

Expliquer à l’aide de ces résultats pourquoi 0.1 + 0.2 == 0.3 vaut False.

Réponse
>>> f"{0.1:.20f}"
'0.10000000000000000555'
>>> f"{0.25:.20f}"
'0.25000000000000000000'
>>> f"{0.1 + 0.2:.20f}"
'0.30000000000000004441'
>>> f"{0.3:.20f}"
'0.29999999999999998890'

0,25\text{0,25} est rangé exactement, car son écriture binaire est finie. 0,1\text{0,1} et 0,2\text{0,2} sont rangés avec une petite erreur. Ces erreurs s’additionnent, et le résultat de l’addition n’est pas le flottant le plus proche de 0,3\text{0,3} : la machine compare deux nombres réellement différents.

Q18.

Prévoir, puis vérifier : 0.5 + 0.25 == 0.75. Le résultat contredit-il la règle « il ne faut pas tester l’égalité de deux flottants » ?

Réponse

Le résultat est True : 0,5\text{0,5}, 0,25\text{0,25} et 0,75\text{0,75} s’écrivent exactement en base 2, le calcul est donc exact. Cela ne contredit pas la règle : dans un programme, on ne sait pas en général si les valeurs manipulées ont une écriture binaire finie. Un test d’égalité peut fonctionner pour certaines valeurs et échouer pour d’autres, ce qui est le pire des cas pour trouver une erreur.

Ces petites erreurs peuvent avoir des conséquences graves. Le 25 février 1991, pendant la guerre du Golfe, une batterie de missiles Patriot n’a pas intercepté un missile Scud, qui a tué 28 soldats à Dhahran, en Arabie saoudite. L’horloge du système comptait le temps en dixièmes de seconde, et la valeur 0,1\text{0,1} était rangée sur 24 bits, donc tronquée : à chaque dixième de seconde, l’horloge prenait un retard d’environ 0,000 000 095\text{0,000} \, 000 \, 095 s.

Q19.

La batterie fonctionnait sans interruption depuis 100 heures. Combien de dixièmes de seconde l’horloge avait-elle comptés ? Quel était alors son retard ? Un Scud vole à environ 1 6761 \, 676 m/s : quelle distance parcourt-il pendant ce retard ?

Réponse

100 h correspondent à 100×3600=360 000100 \times 3600 = 360 \, 000 s, soit 3 600 0003 \, 600 \, 000 dixièmes de seconde.

A.N. Retard : 3 600 000×0,000 000 095≈0,343 \, 600 \, 000 \times \text{0,000} \, 000 \, 095 \approx \text{0,34} s.

A.N. Distance : 1 676×0,34≈5701 \, 676 \times \text{0,34} \approx 570 m.

Le système cherchait le missile à plus d’un demi-kilomètre de sa position réelle. Une erreur minuscule, répétée des millions de fois, est devenue énorme.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Programmer avec des flottants

Q20.

On considère le programme suivant :

x = 0
while x != 1:
    x = x + 0.1
  1. Combien d’itérations l’auteur de ce programme pensait-il faire ?
  2. Expliquer pourquoi la boucle ne s’arrête jamais. Ne pas l’exécuter telle quelle ; pour le vérifier, exécuter plutôt :
x = 0
for i in range(10):
    x = x + 0.1
print(x, x == 1)
Réponse
  1. Il pensait faire 10 itérations : 10×0,1=110 \times \text{0,1} = 1.
  2. Le second programme affiche 0.9999999999999999 False. Après 10 additions, x n’est pas égal à 1 à cause des erreurs d’arrondi accumulées. À l’itération suivante, x dépasse 1 et ne lui sera plus jamais égal : la condition x != 1 reste vraie indéfiniment. C’est une boucle infinie.

Pour comparer deux flottants, on ne teste pas leur égalité. On vérifie que leur écart est très petit, par exemple inférieur à 10−910^{-9}. La fonction abs donne la valeur absolue d’un nombre, et 10−910^{-9} s’écrit 1e-9 en Python.

Q21.

Écrire la fonction sont_proches dont la spécification est :

def sont_proches(a: float, b: float) -> bool:
    """
    Retourne True si l'écart entre a et b est strictement
    inférieur à 1e-9, False sinon.

    >>> sont_proches(0.1 + 0.2, 0.3)
    True
    >>> sont_proches(0.3, 0.31)
    False
    """
Réponse
def sont_proches(a: float, b: float) -> bool:
    return abs(a - b) < 1e-9

La valeur absolue rend le test indépendant de l’ordre de a et b. Erreur fréquente : écrire a - b < 1e-9, qui retourne True dès que a est plus petit que b, même de beaucoup. La bibliothèque standard propose une fonction semblable : math.isclose.

Q22.

Réécrire la boucle de la question précédente pour qu’elle effectue exactement 10 itérations et que x prenne les valeurs 0,1\text{0,1} ; 0,2\text{0,2} ; … ; 11 aussi précisément que possible. Justifier le choix.

Coup de pouce

Les entiers, eux, sont toujours exacts en Python. Quelle variable pourrait compter les itérations sans erreur ?

Réponse
for i in range(1, 11):
    x = i / 10

Le compteur i est un entier : il est exact, et la boucle fait exactement 10 itérations. On calcule x à partir de i à chaque tour, au lieu d’ajouter 0.1 au résultat précédent : chaque valeur de x ne subit qu’un seul arrondi, et les erreurs ne s’accumulent pas. Par exemple, 3 / 10 donne 0.3, alors que trois additions de 0.1 donnent 0.30000000000000004.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • calculer la valeur décimale d’un nombre à virgule écrit en base 2 ;
  • écrire un nombre comme 0,25\text{0,25}, 0,1\text{0,1} ou 1/31/3 en base 2 par la méthode des multiplications successives ;
  • expliquer pourquoi certains nombres, comme 0,1\text{0,1}, ont une écriture binaire infinie et ne sont rangés en machine que de façon approchée ;
  • expliquer pourquoi 0.1 + 0.2 == 0.3 vaut False ;
  • éviter de tester l’égalité de deux flottants, et comparer leur écart à une petite valeur ;
  • préférer un compteur entier à l’accumulation de flottants pour contrôler une boucle.

Le Doc. 4,6 propose des exercices qui mêlent toutes les représentations étudiées dans ce chapitre.

Physique, Chimie et Informatique > 1ère Spécialité NSI > Représentation et manipulation des nombres par un ordinateur

Exercices

Objectif

S’entraîner sur toutes les représentations des nombres étudiées dans le chapitre, en choisissant soi-même la méthode adaptée à chaque situation.

Les exercices mélangent volontairement les notions des Doc. 4,1 à 4,5. Avant de calculer, il faut chaque fois se demander : s’agit-il d’un entier positif, d’un entier relatif ou d’un nombre à virgule ? Sur combien de bits ? Les exercices 1 à 5 se font sans ordinateur ; la console sert ensuite à vérifier les réponses.

Exercice 1 : quelle méthode ?

Q9.

Pour chaque demande, indiquer la méthode utilisée, puis répondre.

  1. Écrire 200 en base 2 sur 8 bits.
  2. Quel entier relatif l’octet 1100100011001000 représente-t-il en complément à 2 ?
  3. Combien de bits faut-il pour écrire 1000 ?
  4. Écrire (7F)16(\text{7F})_{16} en base 2, puis en base 10.
  5. Écrire 0,375\text{0,375} en base 2.
Réponse
  1. Divisions successives par 2 : les restes lus de bas en haut donnent 200=(11001000)2200 = (11001000)_2. L’écriture tient exactement sur 8 bits.

  2. L’octet commence par 1 : il est négatif. Complément à 2 : inversé 0011011100110111, plus 1 : 00111000=5600111000 = 56. Il représente −56-56. On peut aussi calculer 200−256=−56200 - 256 = -56.

    Les réponses 1 et 2 montrent que le même octet 1100100011001000 représente 200 ou −56-56 selon la convention choisie.

  3. Encadrement par des puissances de 2 : 29=512≤1000<1024=2102^9 = 512 \leq 1000 < 1024 = 2^{10}, il faut 10 bits.

  4. Paquets de 4 bits : 7 donne 01110111 et F donne 11111111, donc (7F)16=(01111111)2(\text{7F})_{16} = (01111111)_2. En base 10 : 7×16+15=1277 \times 16 + 15 = 127, le plus grand entier positif d’un octet en complément à 2.

  5. Multiplications successives par 2 : 0,375×2=0,75\text{0,375} \times 2 = \text{0,75} (0), 0,75×2=1,5\text{0,75} \times 2 = \text{1,5} (1), 0,5×2=1\text{0,5} \times 2 = 1 (1). Donc 0,375=(0,011)2\text{0,375} = (\text{0,011})_2, écriture finie car 0,375=3/8\text{0,375} = 3/8.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 2 : des couleurs en hexadécimal

En HTML, la couleur #2E8B57 est formée de trois nombres écrits en base 16 sur deux chiffres chacun : 2E pour le rouge, 8B pour le vert et 57 pour le bleu.

Q10.
  1. Combien de bits occupe chacun des trois nombres ? Combien de valeurs différentes peut-il prendre ?
  2. Convertir les trois nombres en base 10.
  3. Combien de couleurs différentes peut-on écrire de cette façon ? Donner le résultat sous la forme d’une puissance de 2.
Réponse
  1. Deux chiffres hexadécimaux correspondent à 2×4=82 \times 4 = 8 bits, c’est-à-dire un octet : 28=2562^8 = 256 valeurs, de 0 à 255.
  2. (2E)16=2×16+14=46(\text{2E})_{16} = 2 \times 16 + 14 = 46, (8B)16=8×16+11=139(\text{8B})_{16} = 8 \times 16 + 11 = 139 et (57)16=5×16+7=87(\text{57})_{16} = 5 \times 16 + 7 = 87. C’est un vert assez sombre.
  3. Une couleur occupe 3×8=243 \times 8 = 24 bits : on peut écrire 224=16 777 2162^{24} = 16 \, 777 \, 216 couleurs.
Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 3 : vrai ou faux ?

Q11.

Dire si chaque affirmation est vraie ou fausse, et justifier en une phrase, avec un exemple ou un calcul.

  1. La somme de deux entiers positifs écrits sur 16 bits tient toujours sur 16 bits.
  2. Le produit de deux entiers positifs écrits sur un octet tient toujours sur deux octets.
  3. Sur 8 bits, l’opposé de chaque entier relatif peut lui aussi s’écrire sur 8 bits.
  4. En Python, 0.5 + 0.5 == 1 vaut True.
  5. Ajouter un 0 à droite de l’écriture binaire d’un entier positif le multiplie par 10.
Réponse
  1. Faux : la somme tient sur 17 bits. Par exemple, 65 535+1=65 536=21665 \, 535 + 1 = 65 \, 536 = 2^{16}, qui demande 17 bits.
  2. Vrai : le produit de deux entiers de 8 bits tient sur 8+8=168 + 8 = 16 bits. Le plus grand produit est 255×255=65 025<65 536=216255 \times 255 = 65 \, 025 < 65 \, 536 = 2^{16}.
  3. Faux : sur 8 bits, on écrit les entiers de −128-128 à 127127. L’opposé de −128-128 est 128128, qui ne s’écrit pas sur 8 bits.
  4. Vrai : 0,5=(0,1)2\text{0,5} = (\text{0,1})_2 s’écrit exactement en base 2, et le calcul est exact. Cela ne signifie pas qu’on peut tester l’égalité de deux flottants en général.
  5. Faux : ajouter un 0 à droite multiplie par 2 en base 2. Par exemple, (101)2=5(101)_2 = 5 et (1010)2=10(1010)_2 = 10.
Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 4 : un dépassement de capacité

Un programme range des entiers relatifs sur 8 bits, en complément à 2. Il calcule 100+50100 + 50.

Q12.
  1. Écrire 100 et 50 sur 8 bits, puis poser leur addition.
  2. Quel entier relatif l’octet obtenu représente-t-il ?
  3. Expliquer pourquoi le résultat est faux, alors qu’aucune retenue n’a été perdue.
Coup de pouce

Quel est le plus grand entier relatif que l’on peut écrire sur 8 bits ?

Réponse
  1. 100=(01100100)2100 = (01100100)_2 et 50=(00110010)250 = (00110010)_2. Leur somme est (10010110)2(10010110)_2.
  2. L’octet commence par 1 : il est négatif. 150−256=−106150 - 256 = -106. La machine affirme que 100+50=−106100 + 50 = -106.
  3. Le résultat exact, 150, est plus grand que 127, le plus grand entier relatif écrit sur 8 bits. Il ne peut pas être représenté : c’est un dépassement de capacité. Il ne se manifeste pas ici par une retenue perdue, mais par un bit de poids fort qui passe à 1, ce qui change le signe du résultat. L’addition de deux nombres positifs qui donne un résultat négatif est le signe d’un dépassement.
Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 5 : tables de vérité

Q13.
  1. Dresser la table de vérité de a and (b or c), qui dépend de trois variables. Combien de lignes faut-il ?
  2. Dresser celle de (a and b) or (a and c). Que conclure ?
  3. Écrire le programme Python qui affiche la première table, et vérifier la réponse.
Réponse
  1. Avec trois variables, il y a 23=82^3 = 8 combinaisons, donc 8 lignes :

  2. aa bb cc a and (b or c) (a and b) or (a and c)
    0 0 0 0 0
    0 0 1 0 0
    0 1 0 0 0
    0 1 1 0 0
    1 0 0 0 0
    1 0 1 1 1
    1 1 0 1 1
    1 1 1 1 1

    Les deux colonnes sont identiques : les expressions sont équivalentes. On peut « développer » and sur or, comme on développe a×(b+c)a \times (b + c) en calcul.

  3. for a in (False, True):
        for b in (False, True):
            for c in (False, True):
                print(int(a), int(b), int(c), int(a and (b or c)))
Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 6 : programmer

Q14.

Le poids d’un entier positif est le nombre de chiffres 1 de son écriture binaire. Écrire la fonction poids sans utiliser bin, en s’inspirant de la méthode des divisions successives :

def poids(n: int) -> int:
    """
    Retourne le nombre de chiffres 1 de l'écriture en base 2
    de l'entier positif n.

    >>> poids(13)
    3
    >>> poids(255)
    8
    >>> poids(0)
    0
    """
Réponse
def poids(n: int) -> int:
    compteur = 0
    while n > 0:
        compteur = compteur + n % 2
        n = n // 2
    return compteur

Chaque reste n % 2 est un chiffre de l’écriture binaire, égal à 0 ou à 1 : en les additionnant, on compte les 1. Contrairement à decompose, il n’est pas nécessaire de construire la chaîne.

Q15.

On veut convertir une écriture hexadécimale en entier, sans utiliser int(..., 16).

  1. Écrire la fonction valeur_chiffre :
CHIFFRES = "0123456789ABCDEF"

def valeur_chiffre(c: str) -> int:
    """
    Retourne la valeur du chiffre hexadécimal c,
    c'est-à-dire son indice dans CHIFFRES.

    >>> valeur_chiffre("7")
    7
    >>> valeur_chiffre("B")
    11
    """
  1. En s’inspirant de la fonction recompose du Doc. 4,1, écrire la fonction hexa_vers_decimal :
def hexa_vers_decimal(hexa: str) -> int:
    """
    Retourne l'entier dont hexa est l'écriture en base 16.

    >>> hexa_vers_decimal("2E")
    46
    >>> hexa_vers_decimal("7E3")
    2019
    """
Coup de pouce
  1. Parcourir les indices de CHIFFRES et retourner l’indice dès que le caractère correspond.
  2. Dans recompose, on multipliait par 2 à chaque nouveau chiffre. Par combien faut-il multiplier en base 16 ?
Réponse
CHIFFRES = "0123456789ABCDEF"

def valeur_chiffre(c: str) -> int:
    for i in range(len(CHIFFRES)):
        if CHIFFRES[i] == c:
            return i

def hexa_vers_decimal(hexa: str) -> int:
    n = 0
    for c in hexa:
        n = 16 * n + valeur_chiffre(c)
    return n

Pour "7E3" : nn vaut successivement 77, puis 16×7+14=12616 \times 7 + 14 = 126, puis 16×126+3=201916 \times 126 + 3 = 2019.

Vérifier ses acquis 3 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Exercice 7 : une moyenne qui ne tombe pas juste

Un élève a écrit le programme suivant :

moyenne = (12.3 + 11.9 + 12.1) / 3
if moyenne == 12.1:
    print("La moyenne vaut 12,1")
else:
    print("La moyenne ne vaut pas 12,1")
Q16.
  1. Calculer la moyenne à la main. Quel message l’élève attend-il ?
  2. Exécuter le programme. Quel message s’affiche ? Expliquer.
  3. Corriger le programme.
Réponse
  1. 12,3+11,9+12,1=36,3\text{12,3} + \text{11,9} + \text{12,1} = \text{36,3} et 36,3/3=12,1\text{36,3} / 3 = \text{12,1} : il attend « La moyenne vaut 12,1 ».
  2. Le programme affiche « La moyenne ne vaut pas 12,1 ». moyenne vaut 12.100000000000001 : les nombres 12,3\text{12,3}, 11,9\text{11,9} et 12,1\text{12,1} n’ont pas d’écriture binaire finie, et les erreurs d’arrondi des calculs rendent le résultat légèrement différent du flottant 12.1.
  3. On compare l’écart à une petite valeur au lieu de tester l’égalité :
    moyenne = (12.3 + 11.9 + 12.1) / 3
    if abs(moyenne - 12.1) < 1e-9:
        print("La moyenne vaut 12,1")
    else:
        print("La moyenne ne vaut pas 12,1")
Vérifier ses acquis 2 questions

Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.

Bilan

À l’issue de cette activité, je sais…
  • identifier, devant une écriture binaire, la convention à utiliser (entier positif, complément à 2, nombre à virgule) et le nombre de bits ;
  • convertir un entier entre les bases 2, 10 et 16, et un nombre à virgule simple en base 2 ;
  • prévoir la taille d’une somme ou d’un produit, et reconnaître un dépassement de capacité, y compris en complément à 2 ;
  • dresser la table de vérité d’une expression de trois variables et comparer deux expressions ;
  • programmer des calculs sur l’écriture binaire ou hexadécimale d’un entier ;
  • corriger un programme qui teste l’égalité de deux flottants.