2 - Encodage des grands entiers naturels
Nous avons vu comment stoker un entier naturel dont la valeur est comprise entre 0 et 255.
Oui, mais... Comment stocker un entier valant plus que 255 ?
Documents de cours : open document ou pdf
Exercices corrigés complémentaires de cours : exos
1 - Entiers naturels
Encodage des entiers naturels : unsigned integers
Les entiers naturels sont les entiers positifs.
Ils appartiennent à l'ensemble noté ℕ.
Comment les encoder ? Simplement en utilisant ce que nous avons déjà vu avec le binaire : un bit encode 1, le suivant 2, le suivant 4 ...
Dans la plupart des langages, cet encodage est nommé unsigned : le nombre n'est pas signé, on ne peut pas représenter de nombre négatif.
Pour rappel, voici des exemples sur un octet (8 bits) :
Votre nombre binaire M :
| Nombre M = | ||||||||
| Les bits codent | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| On obtient donc |
D'ou la valeur de M en base 10 : M = = .
Avec un octet, on dispose de 8 bits. On peut donc encoder des nombres entiers allant de 0 à 28-1, donc de 0 à 255.
Avec deux octets, on dispose de 16 bits. On peut donc encoder des nombres entiers allant de 0 à 216-1, donc de 0 à 65 535.
Dans cette partie, nous allons voir quelques fonctions Python qui vont nous permettre de travailler facilement sur ces réprésentations binaires.
01° Utiliser le convertisseur ci-dessus pour trouver la valeur du plus grand entier naturel encodable avec 8 bits : 1111 1111 .
- Quelle formule permet de connaitre la valeur maximale encodable par 8 bits ?
- Donner la valeur en base 10 de 0000 1111 2
- Donner la valeur en base 10 de 0000 1001 2.
...CORRECTION...
On peut voir que (1111 1111)2 = (255)10
La formule permettant de retrouver cette valeur est 28 - 1.
0000 1111 2 = (8+4+2+1) 10 = 15 10, qu'on notera juste 15.
0000 1001 2 = (8+1) 10 = 9 10, qu'on notera juste 9.
Si on veut encoder des valeurs supérieures à 255, il suffit donc de rajouter des bits supplémentaires à gauche. Ces bits pèseront donc
- 256 pour 28,
- 512 pour 29,
- 1024 pour 210,
- ...
02° Quels sont les entiers naturels encodables avec les deux suites de 9 bits suivantes :
- 1 0000 0000
- 1 0000 0001
...CORRECTION...
Premier cas : seul le bit de poids fort est activé. Le nombre vaut donc 25610.
| Nombre M = | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Les bits codent | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| On obtient donc | 256 |
Deuxième cas : seuls les bits de poids faible et de poids fort sont activés.
Comme nous avons 9 bits, il s'agit des bits de poids 256 et 1.
| Nombre M = | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Les bits codent | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| On obtient donc | 256 | 1 |
On encode donc le nombre 256 + 1, soit 25710.
Vérifions cela avec Python :
Fonction native bin()
La fonction native bin() a besoin d'un paramètre de type integer contenant le nombre à traiter et répond par un string contenant les valeurs des bits à utiliser.
bin(number:int) -> str
>>> bin(255)
'0b11111111'
Python précise avec 0b que ce string est une représentation d'un encodage binaire. Si vous voulez supprimer les deux premiers caractères d'un string, vous pouvez rajouter [2:] à sa suite. L'interpréteur Python va comprendre que vous ne voulez récupérer que les caractères d'indice 2 et plus. Il ne fournit donc pas les caractères d'indice 0 et 1.
[2:] peut se comprendre comme un raccourci équivalent à
range(2, len(s)) où s est la variable contenant le string.
>>> bin(255)[2:]
'11111111'
Notez bien que l'interpréteur omet 0b.
[2:] permet donc bien de supprimer les deux premiers caractères.
>>> bin(255)[2:]
'11111111'
>>> bin(256)[2:]
'100000000'
>>> bin(257)[2:]
'100000001'
Si vous voulez savoir combien de bits sont nécessaires, il suffit d'utiliser la fonction native len() sur le string obtenu.
Soit en deux opérations (n'oubliez pas 0b sinon votre string va comporter deux caractères en trop !) :
>>> s = bin(257)[2:]
>>> len(s)
9
Soit en une seule opération globale :
>>> len(bin(257)[2:])
9
03° Lancer les instructions suivantes dans une console Python :
>>> bin(255)
'0b11111111'
>>> bin(256)
'0b100000000'
>>> bin(257)
'0b100000001'
Question
- Qu'est-ce qui indique clairement que la réponse de la fonction native bin() est de type string ?
- Dans cette réponse, qu'est-ce qui indique qu'il s'agit d'un contenu affiché en binaire ?
...CORRECTION...
La présence de guillemets simples autour de la réponse permet de voir qu'il s'agit d'un string.
>>> bin(255)
'0b11111111'
Ce string contient les valeurs des différents bits. On le différencie des autres strings par le fait qu'il commence par 0b.
>>> bin(255)
'0b11111111'
On peut également travailler dans l'autre sens : fournir un nombre sous forme binaire et voir sa valeur en décimal.
Binaire en Python
On peut fournir un entier naturel sous forme binaire en transmettant la valeur binaire précédée du suffixe 0b.
>>> nombre = 0b11
>>> nombre
3
04° Utiliser le code ci-dessous qui enregistre une valeur sous forme binaire dans une variable nombre. On affiche ensuite le contenu.
>>> nombre = 0b100000001
>>> nombre
257
Comme vous pouvez le voir, Python est configuré pour afficher les nombres en base 10 quelque soit la façon dont ils ont été fournis.
Pour obtenir un nombre si on dispose d'un string ? Il suffit d'utiliser la fonction native int() qui tente de convertir le contenu que vous allez lui fournir en integer, en entier.
Nous avons déjà rencontré la fonction native int(). Ci-dessous, vous noterez qu'on lui transmet parfois un deuxième argument : 2, pour indiquer qu'elle doit tenter de décoder ce qu'on lui donne comme un nombre en base 2, du binaire.
05° Utiliser le code suivant qui vous montre plusieurs tentatives possibles de conversion en entier. Comme vous pouvez le voir, si on fournit un string, il faut indiquer à l'interpréteur la base avec laquelle décoder.
>>> int('0b11', 2)
3
>>> int('11', 2)
3
2 - Plusieurs octets
Alors, comment décoder une série de 4 octets A B C D ?
Par exemple :
- A = 0000 0001 2
- B = 0000 0010 2
- C = 0000 0011 2
- D = 0000 0100 2
En mémoire, nous avons donc la suite de bits suivante :
0000 0001 0000 0010 0000 0011 0000 0100
Cas de l'encodage sur un seul octet
Si on sait qu'il s'agit de nombres entiers naturels et qu'ils sont encodés sur un seul octet, c'est facile : on fait des paquets de 8 bits. Les nombres sont
- A = 0000 0001 2 = 1 en décimal
- B = 0000 0010 2 = 2 en décimal
- C = 0000 0011 2 = 3 en décimal
- D = 0000 0100 2 = 4 en décimal
Facile.
Cas de l'encodage sur deux octets
Explications
Comment décoder l'entier encodé par la suite de deux octets ci-dessous ?
- A = 0000 0111 et
- B = 0111 0000
Tentons de l'expliquer en plaçant la suite 0000 0111 0111 0000 de 16 bits de A B dans un tableau de façon à visualiser les poids respectifs des cases :
| Nombre M = | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| Poids | 32768 | 16384 | 8192 | 4096 | 2048 | 1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
On obtient donc N = 1024 + 512 + 256 + 64 + 32 + 16 = 1904.
De façon concise N = 0000 0111 0111 0000 2 = 1904 10.
Il fallait bien plus qu'un octet puisque la valeur est supérieure à 255.
C'est facile à comprendre, mais long à décoder puisqu'il faut rechercher le poids de toutes les cases. Voyons comment faire plus rapide avec les puissances de 2 :
| Nombre M = | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| Poids | 215 | 214 | 213 | 212 | 211 | 210 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
Il suffit d'utiliser quelques formules sur les exposants et les fonctions exponentielles :
2a+b = 2a * 2b
Quelques exemples pour montrer que cela fonctionne :
- 26 = 24 * 22, ce qui donne 64 = 16 * 4
- 28 = 28 * 20, ce qui donne 256 = 256 * 1
- 29 = 28 * 21, ce qui donne 512 = 256 * 2
- 210 = 28 * 22, ce qui donne 1024 = 256 * 4
- ...
| Nombre M = | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| Poids | 28 * 27 | 28 * 26 | 28 * 25 | 28 * 24 |
28 * 23 | 28 * 22 | 28 * 21 | 28 * 20 |
1 * 27 | 1 * 26 | 1 * 25 | 1 * 24 |
1 * 23 | 1 * 22 | 1 * 21 | 1 * 20 |
| On obtient donc | Octet de poids fort Y | Octet de poids faible Z | ||||||||||||||
On voit qu'on peut simplifier la lecture des 16 bits en les séparant en deux simples lectures d'octets indépendants Y et Z. Il suffit de multiplier le premier octet par 28 qui vaut 256.
| Nombre M = | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| Poids | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
| On obtient donc | Premier octet Y valant 4 + 2 + 1 = 7 | Deuxième octet Z valant 64 + 32 + 16 = 112 | ||||||||||||||
Et voilà.
| Nombre M = | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| Poids | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| On obtient donc | Y = 7 | Z = 112 | ||||||||||||||
Avec cette façon de faire, on obtient donc N = 256 * 7 + 1 * 112 = 1904.
Encodage d'un entier non signé sur 2 octets
Interprétation à l'aide d'une suite de 16 bits
Avec une séquence de 2 octets, on dispose de 16 bits.
On dispose donc de 216 valeurs, soit 65536.
- La plus petite valeur est 0.
- La plus grande valeur est 65535 calculée à l'aide de 216-1
On peut donc représenter des nombres variant de 0 à 65535.
Pour obtenir la valeur, il suffit de trouver le poids réel des 16 bits puis de faire la somme des bits activés.
Facile, mais long.
Interprétation à l'aide d'une suite de 2 octets
Soit un nombre N encodé comme une suite de deux octets N = Y Z .
L'octet le plus à droite, Z est l'octet de poids faible. Il encode un nombre entre 0 et 255 dont le poids est 1.
L'octet le plus à gauche, Y est l'octet de poids fort. Il encode un nombre entre 0 et 255 dont le poids est 256.
On trouve donc le nombre N exprimé en base 10 en calculant ceci :
N = Y * 256 + Z.
On travaille donc en base 256 en réalité :
- chaque case contient un nombre compris entre 0 et 255 dans chaque case
- chaque case possède un poids lié à une puissance de 256 : 2560 pour la case de poids faible, 2561 pour la case située à sa gauche.
- La seule différence avec une "vraie" base : on ne formule pas les 256 symboles de chiffres, mais on pourrait.
Un peu plus loin...
On peut recevoir des pièces jointes directement encodées sous forme de suite de caractères avec la base 64.
06° En considérant un encodage sur 2 octets d'entiers naturels, déterminer les valeurs encodées par les suites d'octets suivantes :
- Nombre A : 1 2 ( ou en version binaire 0000 0001 0000 0010 )
- Nombre B : 3 4 ( ou en version binaire 0000 0011 0000 0100 )
...CORRECTION...
- Nombre A =
1* 256 +2= 258 - Nombre B :
3* 256 +4= 772
07° En considérant un encodage sur 2 octets d'entiers naturels, déterminer les valeurs encodées par les suites d'octets suivantes :
- Nombre C : 5 130 ( ou en version binaire 0000 0101 1000 0010 )
- Nombre D : 130 5 ( ou en version binaire 1000 0010 0000 0101 )
Question supplémentaire : l'ordre des octets reçus a-t-il un impact sur le nombre décodé ?
...CORRECTION...
- Nombre C =
5* 256 +130= 1410 - Nombre D :
130* 256 +5= 33285
On voit donc bien que l'ordre des octets est important. On ne donne pas le même sens à 5 130 et à 130 5 .
08° En considérant un encodage sur 2 octets d'entiers naturels, déterminer les valeurs encodées par les suites d'octets suivantes :
- Nombre E : 0 65 ( ou en version binaire 0000 0000 0100 0001 )
- Nombre F : 65 0 ( ou en version binaire 0100 0001 0000 0000 )
Question supplémentaire : si on veut exprimer l'entier 10 en l'encodant avec deux octets, l'octet ne comportant que des 0 doit-il être à gauche ou à droite ? Ecrire la suite de 16 bits obtenue.
...CORRECTION...
- Nombre E =
0* 256 +65= 65 - Nombre F :
65* 256 +0= 16640
Si on veut écrire 10 sur deux octets, on écrit donc 0 10 pour que le deuxième octet compte bien juste pour 10 : 0*256 + 10*1.
La suite de bits est donc : 0000 0000 0000 1010
Cas de l'encodage sur quatre octets
Sur 4 octets, c'est donc le même principe. Regardons.
Encodage d'un entier non signé sur 4 octets
Interprétation directe à l'aide d'une suite de 32 bits
Avec une suite de 4 octets, on dispose de 32 bits.
On dispose donc de 232 valeurs différentes (4 294 967 296, un peu plus que 4 milliards) :
- Valeur minimale de 0
- Valeur maximale de 4 294 967 295 obtenue en calculant 232-1
Pour obtenir la valeur, il suffit de trouver le poids réel des 16 bits puis de faire la somme des bits activés.
Facile, mais long.
Interprétation à l'aide d'une suite de 4 octets
Soit un nombre N encodé comme une suite de quatre octets N = W X Y Z .
On peut donc travailler comme sur une base 256 :
- Z contient un nombre compris entre 0 et 255 et son poids est 2560, soit 1.
- Y contient un nombre compris entre 0 et 255 et son poids est 2561, soit 256.
- X contient un nombre compris entre 0 et 255 et son poids est 2562, soit 65536.
- W contient un nombre compris entre 0 et 255 et son poids est 2563, soit 16777216.
On trouve donc le nombre N exprimé en base 10 en calculant ceci :
N = W*16777216 + X*65536 + Y*256 + Z
On peut le comprendre en l'exprimant en respectant plus la notion de base 256 ou base 2 :
Poids des cases exprimés en base 10, 256 et 2 :
| Nombre N = | W | X | Y | Z |
| Le poids de cette case est | 16777216 | 65536 | 256 | 1 |
| Le poids de cette case est | 2563 | 2562 | 2561 | 2560 |
| Le poids de cette case est | 224 | 216 | 28 | 20 |
09° En considérant un entier naturel N encodé sur 4 octets, déterminer la valeur encodée par la suite d'octets suivante :
N = 1 2 3 4
Pour information, cela donne la suite de bits suivante en mémoire :
0000 0001 0000 0010 0000 0011 0000 0100
...CORRECTION...
Il suffit de réaliser le calcul suivant :
N = 1*256**3 + 2*256**2 + 3*256**1 + 4
N = 16 909 060
Vous auriez pu également passer par les puissances de 2.
N = 1*2**24 + 2*2**16 + 3*2**8 + 4
10° En considérant un entier naturel N encodé sur 4 octets, déterminer la valeur encodée par la suite d'octets suivante :
N = 10 20 255 0
...CORRECTION...
Il suffit de réaliser le calcul suivant :
N = 10*256**3 + 20*256**2 + 255*256**1 + 0
N = 169 148 160
11° En considérant un entier naturel N encodé sur 4 octets, déterminer la valeur encodée par la suite d'octets suivante :
N = 255 255 255 255
Question supplémentaire : comparer votre résultat à 232-1. Justifiez l'égalité.
...CORRECTION...
Il suffit de réaliser le calcul suivant :
N = 255*256**3 + 255*256**2 + 255*256**1 + 255
N = 4 294 967 295
Nous venons de remplir tous les octets. Cela forme donc une suite de 32 bits. Or, la valeur maximale encodable avec 32 bits est 232-1.
12° Combien d'octets faut-il pour encoder un entier naturel valant 6 milliards :
- 1 octet
- 2 octets
- 4 octets
- 8 octets
...CORRECTION...
Nous venons de voir qu'avec 4 octets, on peut encoder un peu plus de 4 milliards.
Pour 6 milliards, il faudra donc 8 octets, 4 ou moins est insuffisant.
Affirmation pour les questions 13-14-15 : dans un tableau statique, toutes les cases doivent contenir le même nombre d’octets.
13° Quelle place mémoire doit-on réserver si on veut créer un tableau de 100 cases pouvant contenir des valeurs allant jusqu'à 200 ?
...CORRECTION...
Un octet suffit pour chaque case (avec un octet, on peut encoder des valeurs entre 0 et 255).
Il faut 100 cases donc 100 octets.
14° Quelle place mémoire doit-on réserver si on veut créer un tableau de 100 cases pouvant contenir des valeurs allant jusqu'à 65535 ?
...CORRECTION...
65535 est la valeur maximale encodable avec deux octets.
Il faut 100 cases donc 100*2 = 200 octets.
15° Quelle place mémoire doit-on réserver si on veut créer un tableau de 100 cases pouvant contenir des valeurs allant jusqu'à 4 milliards ?
...CORRECTION...
Nous avons vu qu'avec 4 octets, on peut encoder une valeur maximale un peu plus grande que 4 milliards.
Il faut 100 cases donc 100*4 = 400 octets.
3 - Dépassement
A partir du moment où on a demandé une place mémoire pour stocker notre entier, l'ordinateur va donc reserver cette place. Par exemple deux octets.
Mais il fait attention à un cas de figure particulier : on additionne deux entiers de 2 octets chacun mais le résultat final ne tient pas sur deux octets : il en faudrait au moins un troisième.
Par exemple :
- 65534 tient bien sur 2 octets (puisqu'on peut encoder un nombre entre 0 et 65535)
- 100 tient bien sur 2 octets (puisqu'on peut encoder un nombre entre 0 et 65535)
- Mais 65534 + 100 vaut 65634. Et c'est supérieur à 65535 ! Il faudrait donc plus de 2 octets pour le stocker.
Addition de nombre binaire bit à bit
Nous avons vu comment incrémenter de 1 un nombre dans l'activité précédente : on additionne notre nombre et un autre nombre ne comportant qu'un bit activé celui du bit de poids faible.
Avec deux nombres différent de 1, c'est pareil, si ce n'est qu'on travaille sur tous les bits à la fois. Attention aux retenues donc.
Pour rappel, en binaire, on obtient ceci
- 0 + 0 = 0
- 0 + 1 = 1 ce qui veut dire que le successeur de 0 est 1 en binaire
- 1 + 0 = 1
- 1 + 1 = 10 ce qui veut dire que le successeur de 1 est 10 en binaire
- 1 + 1 + 1 = 11
Rien de surprenant si vous regardez bien.
- 0 + 0 = 0 veut dire en décimal 0+0 = 0
- 0 + 1 = 1 veut dire en décimal 0+1 = 1
- 1 + 0 = 1 veut dire en décimal 1+0 = 1
- 1 + 1 = 10 veut dire en décimal 1+1 = 2
- 1 + 1 + 1 = 11 veut dire en décimal 1+1+1 = 3
Regardons comment effectuer l'addition de deux nombres exprimés en binaire, colonne par colonne (c'est à dire bit à bit)
Exemple (animation)
On remarquera que calculer en base 2 ou en base 10 ne change rien au résultat.
>>> 0b0101010101010101
21845
>>> 0b0100100100100100
18724
>>> 0b1001111001111001
40569
>>> 21845+18724
40569
Même exemple mais en pas à pas
...exemple pas à pas...
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | ||||||||||||||||
| N = A + B | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | ||||||||||||||||
| N = A + B | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | |||||||||||||||
| N = A + B | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | ||||||||||||||
| N = A + B | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | +1 | |||||||||||||
| N = A + B | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
Au final
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| Retenue ? | +1 | +1 | +1 | |||||||||||||
| N = A + B | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
16° Réaliser l'addition suivante sur votre copie. Le contenu du tableau est éditable.
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Retenue ? | ||||||||||||||||
| N = A + B |
...CORRECTION...
| Nombre A | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Retenue ? | +1 | +1 | +1 | +1 | ||||||||||||
| N = A + B | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 |
17° Réaliser l'addition suivante sur votre copie. Le contenu du tableau est éditable.
Quel est le problème ?
| Nombre A | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Retenue ? | ||||||||||||||||
| N = A + B |
...CORRECTION...
| Nombre A | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| Nombre B | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| Retenue ? | +1 | +1 | +1 | +1 | ||||||||||||
| 1 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 |
Le problème est donc qu'on pourrait écraser le contenu du bit situé à gauche. Or ce contenu est peut être utilisé et censé coder quelque chose. Il s'agit d'un dépassement.
Et même si on n'écrase rien et qu'on garde uniquement le bon nombre d'octets, on obtient ainsi un retour à 0.
EXEMPLE à un octet :
- 1111 1110 +1 donne 1111 1111
- 1111 1111 +1 donne 0000 0000 !
C'est bien ce qui s'est passé avec notre robot fou.
Dépassement
Lorsqu'on travaille avec des entiers naturels dont l'encodage est lié à une taille fixe d'octets, il est possible que la somme de deux entiers donne un résulat faux. Quand ?
On parle de dépassement lorsque la somme réelle devrait donner un résultat supérieur à la valeur maximale encodable avec ce nombre d'octets.
Un premier exemple
Un entier A sur un octet contient 250. Un autre entier B contient 10. La somme de A + B provoquerait un dépassement puisqu'on ne peut pas stocker 260 sur un seul octet !
Un autre exemple
- On encode le nombre A = 16384 sur deux octets : 64 0
- On encode le nombre B = 49152 sur deux octets : 192 0
- Si on calcule de tête A + B = 16384 + 49152, cela donne 65536. Cela veut dire qu'un système traitant les entiers sur 2 octets ne parviendra pas à obtenir le bon résultat : avec deux octets, on ne peut travailler correctement que jusqu'à 65535 !
En effet, on peut obtenir 16384 en calculant 64 * 256 + 0.
La suite des 16 bits donne donc 01000000 00000000
En effet, on peut obtenir 49152 en calculant 192 * 256 + 0.
La suite des 16 bits donne donc 11000000 00000000
A cause du dépassement du résultat sur 2 octets, on obtiendrait donc 16384 + 49152 = 0.
Un autre exemple
Sur 2 octets, 16384 + 49154 = 2.
Dépassement avec Python ?
Des choses assez désagréables peuvent arriver avec ce type de débordement. En Python, c'est transparent puisque c'est l'interpréteur qui se charge de réserver la place mémoire. Si la place n'est plus suffisante, Python va simplement déménager le contenu pour qu'il ai plus de place.
Python est un langage qui gère la taille nécessaire pour l'utilisateur. S'il faut 8 octets, il en prendra 8. Ou 16, ou 32...
Par contre, avec Arduino, qui est une version légère de C++, c'est possible. C'est à cause d'un dépassement de ce type que le robot de l'activité 1 retournait à une vitesse de 0.
La vitesse maximale 1111 1111 était encodée sur un octet (byte) et devenait 1 0000 0000 .
Détection de dépassement sur les entiers naturels
Dépassement à cause d'addition
L'un des moyens de détecter si la somme C = (A+B) de deux entiers A et B a provoqué un dépassement ou pas est de vérifier qu'on ai bien :
- C > A
- C > B
Si l'une des assertions ci-dessus est fausse, c'est bien que le résultat n'est pas bon !
Par exemple, 16384 + 49154 donnant 2 est un dépassement facilement détectable par un système informatique.
Dépassement à cause de multiplication
Sur deux octets, 400 * 500 donne 3392 plutôt que 200000. C'est un dépassement, mais on ne peut pas le découvrir en comparant juste les valeurs 400 et 500 à la valeur obtenue 3392 puisqu'elle est bien plus grande que 400 et 500...
Comment faire alors ?
C'est assez simple également mais il faut y penser.
On évalue C = A*B par l'ordinateur puis on vérifie ensuite que (si B est différent de 0), l'assertion C // B == A est bien correcte, ou pas.
Exemple avec 400*500 qui donne 3392 sur deux octets.
- B vaut 500, c'est bien différent de 0.
- On évalue C // B qui donne donc 3392 // 500, on obtient 6.
- Comme 6 ne vaut pas A (400), on peut en déduire que la multiplication n'a pas fonctionné et qu'il y a eu un problème de dépassement.
18° On considère la multiplication de A = 16000 par B = 2000 sur 16 bits. On obtient C = 18432. Expliquez comment on peut détecter le dépassement sans faire le calcul direct.
Question supplémentaire : quelle est la plus grande valeur encodable avec 16 bits ?
...CORRECTION...
On a B = 2000 qui est donc bien différent de 0.
Si on calcule C // A, on obtient 18432 // 16000, soit 1 puisque c'est une division euclidienne.
Nous avons donc eu un dépassement.
Remarque
Pour simuler un mauvais fonctionnement, trouver la mauvaise valeur obtenue sur 2 octets, il suffit de faire ce calcul :
>>> (16000*2000) % 65536
18432
Pourquoi 65536 ? Tout simplement car il s'agit du nombre de cas possibles avec 2 octets (16 bits) : 216 ou 2562.
>>> (16000*2000) % (2**16)
18432
19° On considère la multiplication de A = 16000 par B = 2000 sur 32 bits. On obtient C = 32 000 000.
- Expliquez comment on peut détecter s'il y a eu dépassement, ou pas, sans faire le calcul direct B*C et comparer avec C.
- Simuler ensuite le résultat du calcul sur 24 bits (3 octets) comme ci-dessous. Le calcul de C est-il bon ? Donner l’explication, pas votre avis.
>>> (16000*2000) % (2**24)
...CORRECTION...
On a B = 2000 qui est donc bien différent de 0.
Si on calcule C // A, on obtient 32 000 000 // 16000, soit 2000 puisque c'est une division euclidienne.
Nous n'avons donc pas eu de dépassement et 32 000 000 est le bon résultat.
Avec 3 octets, on a 24 bits (3*8). La valeur maximale est donc 224-1, soit 16 777 215.
Nous aurions donc eu un mauvais résultat dû à un dépassement puisque le vrai résultat de 32 millions est supérieur à la capacité maximale de 16 777 215 avec 24 bits.
On aurait alors obtenu :
>>> (16000*2000) % (2**24)
15222784
20° Voici un exercice de synthèse final.
On veut multiplier les entiers A et B suivants dont on vous donne l'encodage sur 4 octets.
Questions
- Donner la valeur de A encodé par les 4 octets suivants : 200 50 0 250 .
- Donner la valeur de B encodé par les 4 octets suivants : 5 10 20 150 .
- Expliquer s'il y a eu dépassement en considérant la valeur C = A * B évalué par un programme si C = 556014204.
- Donner le résultat C = A * B en le réalisant sur la console Python. Vérifier s’il y a eu dépassement après avoir vérifié que Python calcule C = 283 968 746 947 877 500.
...CORRECTION...
A = 200*256**3 + 50*256**2 + 0*256 + 250
A = 3 358 720 250
B = 5*256**3 + 10*256**2 + 20*256 + 150
B = 84 546 710
On peut effectuer la vérification puisque B n'est pas nul. On doit vérifier que C//B donne bien A.
C // B = 556014204 // 84546710 = 6
On n'obtient pas A. Nous avons donc subi une erreur de calcul à cause d'un dépassement.
Voici comment le vérifier avec Python :
>>> C = 3358720250 * 84546710
>>> C
283968746947877500
>>> C // 84546710
3358720250
Puisqu'on obtient bien A en réalisant C // B, on peut en déduire qu'il n'y a pas eu dépassement avec Python.
4 - FAQ
J'ai vu qu'en C ou en Java, il y a plein de types d'intégers.
En fonction du nombre d'octets voulus pour le stockage, il existe souvent plusieurs types d'integers. Selon les langages de programmation, les noms et les tailles correspondantes sont variables.
Dans la plupart des langages, il existe des integers qu'on nomme :
- byte : en Arduino, on stocke un entier sans signe (non signé) sur un seul octet. On peut donc encoder des nombres allant de 0 à 255. En Java, il se nomme unsigned byte.
- unsigned short : 2 octets (16 bits) en Java, au moins 2 octets en C (valeur exacte fonction du processeur).
- unsigned int : 4 octets (32 bits) en Java, au moins 2 octets en C (valeur exacte fonction du processeur).
- unsigned long : 8 octets (64 bits) en Java, au moins 4 octets en C (valeur exacte fonction du processeur).
- unsigned long long : au moins 8 octets en C (valeur exacte fonction du processeur).
En Python, c'est plus facile pour l'utilisateur : il n'y a que le type int. C'est l'interpréteur qui se charge de choisir le nombre d'octets nécessaires pour toutes nouvelles affectations.
En Javascript, c'est encore plus simple : il n'y a même pas de type int et float mais uniquement un type number !
J'ai entendu parler de big endian et little endian... C'est quoi ce truc ?
Un problème technique arrive lorsqu'on veut stocker puis relire un contenu composé de plusieurs octets : il faut savoir dans quel ordre on les recoit !
On nomme cela le boutisme.
- En gros boutisme ou big endian, l'octet de poids fort est écrit en premier et donc lu ensuite en premier.
- En petit boutisme ou little endian, l'octet de poids faible est écrit en premier et donc lu ensuite en premier.
Imaginons qu'on veuille stocker 25800 en mémoire.
N = 100*256 + 200 = 25800
On doit stocker 100 en tant qu'octet de poids fort et 200 en tant qu'octet de poids faible.
En gros boutisme
L'octet de poids fort 100 devra apparaître en premier lors de la lecture : 100 200 .
En petit boutisme
L'octet de poids faible 200 devra apparaître en premier lors de la lecture : 200 100 .
Activité publiée le 22 09 2019
Dernière modification : 29 09 2019
Auteur : ows. h.