3 - Encodage des entiers relatifs
Nous avons vu que l'ordinateur stocke les données sous forme d'octets, un ensemble de 8 bits.
Nous avons vu qu'avec un octet (8 bits) :
- on obtient 28 (256) valeurs différentes.
- on peut donc stocker un entier naturel compris dans l'intervalle
[ 0 ; 255 ] - qu'on peut également écrire
[ 0 ; 256 [
Nous avons vu qu'avec deux octets (16 bits) :
- on obtient 216 (65536) valeurs différentes.
- on peut donc stocker un entier naturel compris dans l'intervalle
[ 0 ; 65535 ] - qu'on peut également écrire
[ 0 ; 65536 [
Mais comment stocker un entier relatif, un entier pouvant être positif ou négatif ?
Documents de cours : open document ou pdf
1 - Un encodage basique
Ensemble ℤ des entiers relatifs
L'ensemble des entiers relatifs est l'ensemble comprenant les entiers positifs et négatifs.
On note cet ensemble ℤ
Dans la plupart des langages, cet encodage est nommé signed. Cela veut dire que le nombre est signé.
Les nombres entiers -5 ou +5 ou 5 sont donc membres de ℤ.
La solution la plus "évidente" pour encoder des nombres positifs ou négatifs ?
Ne pas utiliser le bit de poids fort pour coder le nombre mais pour coder son signe :
0, c'est positif (comme avant du coup)1, c'est négatif.
Avec cette méthode
pour encoder les nombres (+1)10 ou (-1)10, on stocke 01 ou 11
pour encoder les nombres (+2)10 ou (-2)10, on stocke 010 ou 110
pour encoder les nombres (+3)10 ou (-3)10, on stocke 011 ou 111
C'est simple mais ... ça ne fontionne pas vraiment.
Première raison : le nombre 0 posséderait deux encodages possibles : 00 et 10.
Deuxième et vraie raison : l'addition ne fonctionne pas !
Nous savons tous que 2 + (-2) 10 donne 0 10.
Essayons :
Pour encoder les nombres (+5)10 ou (-5)10, on stocke 0101 ou 1101
| Nombre +510 | 0 | 1 | 0 | 1 | |
| Nombre -510 | 1 | 1 | 0 | 1 | |
| Retenue ? | +1 | +1 | +1 | ||
| Somme | 1 | 0 | 0 | 1 | 0 |
Si on considère que le bit de signe et toujours le bit le plus à droite, on obtient 10010, soit -2 10 !
2 - Complément à deux
Le complément à deux
La méthode du complément à deux permet d'encoder les entiers relatifs (qu'on nomme également entiers signés en informatique) de telle façon que la somme des bits d'un nombre et de son opposé donne bien un ensemble de bits à 0.
Bit de signe
On utilise le bit de poids fort pour stocker l'information signe
0, c'est positif (comme avant du coup)1, c'est négatif.
Cas des nombres positifs
Rien ne change par rapport au cas des nombres entiers naturels.
On a juste besoin d'un bit supplémentaire pour stocker l'information signe
Sur un octet, on ne dispose donc que de 7 bits pour encoder la valeur, le 8e bit sert à encoder le signe.
Sur un octet, la valeur positive maximale est donc encodée par ceci :
| Valeurs stockées | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Les bits codent | + | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
La valeur maximale positive est donc 64 + 32 + 16 + 8 + 4 + 2 + 1 10, soit 127 10.
Cas des nombres négatifs
Pour encoder un nombre négatif en utilisant le complément à deux, il faut
- Trouver l'encodage du nombre positif correspondant
- Inverser tous les bits (opération qu'on nomme complément à 1)
0devient11devient0- Rajouter 1 (sur le bit de poids faible donc) en ignorant le dépassement éventuel
Exemple avec -1
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| Inversion et +1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 +1 |
| Encodage de -1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
La représentation de -1 dans cet encodage est donc 1111 1111 .
Comme vous pouvez le voir, si on donne la valeur binaire contenu dans l'octet, on pouvait croire qu'on a voulu stocker 255 !
Il ne faut donc pas confondre
- la valeur de l'octet (ici on lit
25510 ou1111 11112) - la signification de cette valeur d'octet (ici on parvient à décoder qu'on a voulu stocker
-1).
Le contenu d'un octet n'a donc de sens que si on sait avec quel encodage il a été rempli.
Exemple avec -6
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| Inversion et +1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 +1 |
| Encodage de -6 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
Dans cette représentation, le nombre -6 est donc encodé par un octet valant 1111 1010 2 ou 250 10.
Cas du 0
| Code | Dépassement | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Inversion et +1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 +1 | |
| Encodage de -0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Comme on ne tient pas compte du dépassement, on obtient juste 0000 0000 2 ou 0 10
Le zéro n'a donc qu'une seule représentation avec la méthode du complément à deux.
01° Utiliser le complément à deux pour montrer que -210 s'encode ainsi sur 1 octet : 1111 1110 .
Quelle est la valeur de cet octet lu comme un entier naturel ?
Vérifier en tapant ceci dans une Console Python :
>>> int(0b11111110)
Attention : la fonction python int tente de convertir le contenu fourni en entier naturel. Ici, on utilise donc un encodage différent en lecture qu'en écriture. C'est pour cela qu'on ne retrouve pas le -2. C'est comme écrire un texte en anglais et tenter de le lire en chinois. Ca donne des résultats étranges.
...CORRECTION...
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| Inversion | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 +1 |
| Encodage de -2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
La représentation de -210 est donc 1111 1110 .
En décimal, cela représente le cas 254 .
02° Utiliser le complément à deux sur un octet pour montrer que -310 s'encode alors 1111 1101 . Quelle est la valeur de l'octet en décimal ?
...CORRECTION...
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| Inversion et +1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 +1 |
| Encodage de -3 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
La représentation de -310 est donc 1111 1101 .
03° Utiliser le complément à deux sur un octet pour montrer que -1310 s'encode alors 1111 0011 .
...CORRECTION...
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +13 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| Inversion et +1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 +1 |
| Encodage de -13 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
La représentation de -1310 est donc 1111 0011 .
04° Utiliser le complément à deux sur un octet pour montrer que -2610 s'encode alors 1110 0110 sur un octet.
Il faudra donc d'abord trouver comment encoder -2610.
...CORRECTION...
Commençons par trouver comment représenter +26 par une suite de puissance de 2.
La méthode intuitive ?
Trouver le plus grand bit à activer : 32 c'est trop.
Nous allons donc activer le bit codant 16. Il nous manque donc encore 26-16 = 10 à obtenir.
Nous allons donc activer le bit codant 8. Il nous manque donc encore 10-8 = 2 à obtenir.
Il reste donc à activer le bit codant 2 et c'est fini.
On obtient donc :
| Code | signe | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +26 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Inversion et +1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 +1 |
| Encodage de -26 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
On obtient donc l'encodage suivant : 1110 0110
En décimal, on a donc un octet valant 230 .
Sur deux octets, quatre octets ou huit octets, ça ne change rien : le bit de signe est toujours à gauche et le bit de poids faible est à droite.
Si on veut encoder -26 sur deux octets :
| Code | signe | 16384 | 8192 | 4096 | 2048 | 1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Encodage de +26 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Inversion et +1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 +1 |
| Encodage de -26 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
On obtient donc l'encodage suivant sur 16 bits : 1111 1111 1110 0110
Si on décompose les deux octets : 1111 1111 1110 0110
En utilisant deux octets, le nombre -26 est donc encodé par une suite de deux octets valant 255 230 .
3 - Décoder un integer signé
Vous savez maintenant comment utiliser le complément à deux pour encoder un entier relatif.
Voyons maintenant comment décoder le contenu d'un octet dont on pense qu'il encode un entier relatif.
Commençons par voir ce qu'on pourrait faire avec 4 bits (on nomme cela un quartet).
| Nombre décimal encodé | Contenu du quartet en binaire | Contenu du quartet si entier non signé (en décimal) |
| 0 | 0000 |
0 |
| 1 | 0001 |
1 |
| 2 | 0010 |
2 |
| 3 | 0011 |
3 |
| 4 | 0100 |
4 |
| 5 | 0101 |
5 |
| 6 | 0110 |
6 |
| 7 | 0111 |
7 |
| négatif mais combien ? | 1000 |
8 |
| négatif mais combien ? | 1001 |
9 |
| négatif mais combien ? | 1010 |
10 |
| négatif mais combien ? | 1011 |
11 |
| négatif mais combien ? | 1100 |
12 |
| négatif mais combien ? | 1101 |
13 |
| négatif mais combien ? | 1110 |
14 |
| négatif mais combien ? | 1111 |
15 |
Alors, comment parvenir à retrouver l'entier négatif que nous avons encodé ?
Avec le complément à deux, c'est facile : on utilise aussi le complément à deux pour décoder le contenu.
05° Utiliser le complément à deux (inversion et rajout de 1) sur le quartet pour retrouver l'entier négatif qu'on a voulu stocker dans les deux quartets suivant :
| Nombre décimal encodé | Contenu du quartet en binaire | Contenu du quartet en décimal |
| négatif mais combien ? | 1001 |
9 |
| négatif mais combien ? | 1010 |
10 |
...CORRECTION...
| Lecture des bits | 1 | 0 | 0 | 1 |
| Inversion | 0 | 1 | 1 | 0 |
| Rajout de 1 | 0 | 1 | 1 | 1 |
| Code | 4 | 2 | 1 |
Le quartet contenant 1001 peut donc être décodé par -710 si on considère que l'encodage utilisé est le complément à deux.
...CORRECTION...
| Lecture des bits | 1 | 0 | 1 | 0 |
| Inversion | 0 | 1 | 0 | 1 |
| Rajout de 1 | 0 | 1 | 1 | 0 |
| Code | 4 | 2 | 1 |
Le quartet contenant 1010 peut donc être décodé par -610 si on considère que l'encodage utilisé est le complément à deux.
Cas particulier du 1 suivi de 0
Il s'agit des contenus dont les bits forment une séquence de ce type :
10001000 00001000 0000 0000 0000- ...
| Lecture des bits | 1 | 0 | 0 | 0 |
| Inversion | 0 | 1 | 1 | 1 |
| Rajout de 1 | 1 | 0 | 0 | 0 |
| Code | 8 | 4 | 2 | 1 |
On revient à la même chose ! C'est un cas particulier, comme zéro.
A savoir : cas particulier, on l'utilise pour coder -8, la plus petit valeur possible ici.
Ce contenu du quartet va donc simplement nous permettre d'encoder -8.
Si on résume :
1000donne -23 soit -81000 0000donne -27 soit -1281000 0000 0000 0000donne -215 soit -32768- ...
Nous pouvons donc maintenant écrire notre table pour le quartet
| Nombre décimal encodé | Contenu du quartet en binaire | Contenu du quartet en décimal |
| 0 | 0000 |
0 |
| 1 | 0001 |
1 |
| 2 | 0010 |
2 |
| 3 | 0011 |
3 |
| 4 | 0100 |
4 |
| 5 | 0101 |
5 |
| 6 | 0110 |
6 |
| 7 | 0111 |
7 |
| -8 | 1000 |
8 |
| -7 | 1001 |
9 |
| -6 | 1010 |
10 |
| -5 | 1011 |
11 |
| -4 | 1100 |
12 |
| -3 | 1101 |
13 |
| -2 | 1110 |
14 |
| -1 | 1111 |
15 |
C'est peut-être bizarre pour un humain mais c'est pratique pour l'ordinateur. Au moins, la somme bits à bits de la représentation de +7 et -7 donne bien zéro.
4 - Valeurs extrêmes
Nous avons vu avec le quartet qu'il y a une dissymétrie entre la valeur maximale en positif et en négatif.
Pourquoi ?
Simplement car le bit de signe positif permet également d'encoder le nombre zéro.
Avec les 3 bits restants, on obtient donc bien 23 cas soit 8 cas : les valeurs comprises entre 0 et +7.
| Nombre décimal encodé | Contenu du quartet en binaire | Contenu du quartet en décimal |
| 0 | 0000 |
0 |
| 1 | 0001 |
1 |
| 2 | 0010 |
2 |
| 3 | 0011 |
3 |
| 4 | 0100 |
4 |
| 5 | 0101 |
5 |
| 6 | 0110 |
6 |
| 7 | 0111 |
7 |
C'est la même chose avec le bit de signe à -1 .
Avec les 3 bits restants, on obtient donc bien 23 cas soit 8 cas : les valeurs comprises entre -1 et -8.
| Nombre décimal encodé | Contenu du quartet en binaire | Contenu du quartet en décimal |
| -8 | 1000 |
8 |
| -7 | 1001 |
9 |
| -6 | 1010 |
10 |
| -5 | 1011 |
11 |
| -4 | 1100 |
12 |
| -3 | 1101 |
13 |
| -2 | 1110 |
14 |
| -1 | 1111 |
15 |
Il nous reste juste à généraliser.
Valeurs extrêmes d'un encodage d'entier relatif sur un octet
Pour connaitre les valeurs extrêmes, il suffit de compter le nombre de bits disponibles pour encoder les cas.
On retire un bit pour le bit de signe.
Avec un octet : -128 ≤ x ≤ +127
- 8 bits donc 7 bits pour encoder les différentes valeurs.
- Nombre de cas positifs : 27, soit 128.
- Première valeur : 0
- Valeur extrême : +127
- Nombre de cas négatifs : 27, soit 128.
- Première valeur : -1
- Valeur extrême : -128
On pourra également dire que x ∈ [-128 ; +127]
Ou encore x ∈ [-128 ; +128[
Valeurs extrêmes d'un encodage d'entier relatif sur deux octets
Avec deux octets : -32768 ≤ x ≤ +32767
- 16 bits donc 15 bits pour encoder les différentes valeurs.
- Nombre de cas positifs : 215, soit 32768.
- Première valeur : 0
- Valeur extrême : +32767
- Nombre de cas négatifs : 215, soit 32768.
- Première valeur : -1
- Valeur extrême : -32768
On pourra également dire que x ∈ [-32768 ; +32767]
Ou encore x ∈ [-32768 ; +32768[
Valeurs extrêmes d'un encodage d'entier relatif sur quatre octets
Souvent l'encodage de base sur les systèmes 32 bits.
Avec quatre octets : - 2 147 483 648 ≤ x ≤ + 2 147 483 647
- 32 bits donc 31 bits pour encoder les différentes valeurs.
- Nombre de cas positifs : 231, soit 2 147 483 648.
- Première valeur : 0
- Valeur extrême : +2 147 483 647
- Nombre de cas négatifs : 231, soit 2 147 483 648.
- Première valeur : -1
- Valeur extrême : -2 147 483 648
On pourra également dire que x ∈ [-2 147 483 648 ; +2 147 483 647]
Ou encore x ∈ [-2 147 483 648 ; +2 147 483 648[
06° Déterminer le nombre de bits disponibles dans un ensemble de 8 octets. En déduire l'encadrement des entiers relatifs encodables par un ensemble de 8 octets en utilisant la méthode proposée du complément à deux.
...CORRECTION...
Il y a 8 bits par octet.
Dans 8 octets, on trouve donc 8*8, soit 64 bits.
Pour encoder un entier signé, il y a 63 bits pour les valeurs.
On calcule 2**63, ce qui donne 9 223 372 036 854 775 808.
On pourra également dire que x ∈ [-9 223 372 036 854 775 808 ; +9 223 372 036 854 775 807]
Ou encore x ∈ [-9 223 372 036 854 775 808 ; +9 223 372 036 854 775 808[
07° Déterminer l'intervalle disponible lorsqu'on stocke sur 8 octets un entier non signé. Conclusion : pourquoi est-il parfois intéressant de signaler qu'on ne veut stocker qu'un entier naturel ?
...CORRECTION...
Il y a 8 bits par octet.
Dans 8 octets, on trouve donc 8*8, soit 64 bits.
Pour encoder un entier signé, il y a 64 bits pour les valeurs.
On calcule 2**64, ce qui donne 18 446 744 073 709 551 616.
La valeur maximale est donc deux fois plus grande qu'avec un entier signé !
On pourra également dire que x ∈ [0 ; +18 446 744 073 709 551 615]
Ou encore x ∈ [0 ; +18 446 744 073 709 551 616[
Généralisation
Entiers naturels
Valeurs maximales encodables dans un ensemble de X bits :
On pourra dire que x ∈ [ 0 ; 2X -1 ]
Ou encore x ∈ [ 0 ; 2X [
Entiers relatifs
Valeurs extrêmes encodables dans un ensemble de X bits :
L'un des bits est le bit de signe.
Il reste donc X-1 bits pour encoder les valeurs.
On pourra dire que x ∈ [ -2X-1 ; 2X-1 -1 ]
Ou encore x ∈ [ -2X-1 ; 2X [
5 - Formule du complément à deux
L'ordinateur fait ce qu'on a vu : inversion des bits et rajout de 1. Pour lui, les opérations sur les bits sont très rapide.
Mais pourquoi la technique se nomme complément à 2 ?
Bonne question.
En réalité, le nom entier est complément à 2X où X représente le nombre de bits disponibles.
Voici la formule reliant la valeur négative encodée et le contenu binaire des bits :
Formule du complément à deux
valeur négative = ( contenu binaire ) 10 - 2X
Exemple 1 :
- 8 Bits de contenu : X = 8
- contenu binaire =
1111 11112 = 255 10 si on le lit comme un entier non signé - valeur négative = 255 - 28 = 255 - 256 = -1
1111 1111encode donc -1 si on doit le décoder comme un entier signé.
Exemple 2 :
- 8 Bits de contenu : X = 8
- contenu binaire =
1000 00002 = 128 10 si on le lit comme un entier non signé - valeur négative = 128 - 28 = 256 = -128
1000 0000encode donc -128 si on doit le décoder comme un entier signé.
Exemple 3 :
- 16 Bits de contenu : X = 16
- contenu binaire =
1000 0000 1111 11112 = 33023 10 si on le lit comme un entier non signé - valeur négative = 33023 - 216 = 33023 - 65536 = -32513
1000 0000 1111 1111encode donc -32513 si on doit le décoder comme un entier signé.
Pour faire l'inverse, il suffit de passer le -2X dans le terme de gauche : il devient alors -2X.
Formule permettant de passer du contenu binaire à la valeur négative
valeur négative + 2X = ( contenu binaire ) 10
On peut écrire cette valeur en inversant les deux côtés. En maths, a = b peut s'écrire b = a aussi). Attention : pas en informatique où le = symbolise l'affectation.
( contenu binaire ) 10 = valeur négative + 2X
Remarque
Cette zone est en rouge car il s'agit de la même formule que celle de la zone verte : il suffit d'isoler le terme qui vous intéresse. Seule l'une d'entre elles est donc à apprendre, sinon c'est la confusion assurée.
Moralité : c'est plus rapidement pour un humain que la méthode vu dans le cours (1-inversion des bits, 2-rajout de 1), mais c'est juste un "truc". Preférez la méthode de l'inversion sur vos copies.
08° Quel est l'entier encodé par l'octet 1000 1111 en base 2 si on sait qu'il s'agit d'un entier signé ?
Utiliser d'abord la méthode rapide.
Vérifier en faisant la transformation (inversion + rajout de 1).
...CORRECTION...
1e méthode : on soustrait 28 (puisqu'on utilise un octet) à la valeur brute de l'octet lu comme un entier non signé
- Bits en mémoire :
1000 1111: 143 si on considère qu'il s'agit d'un entier non signé - 143 - 256 = -113
2e méthode : on se souvient comme ça fonctionne.
- Bits en mémoire :
1000 1111 - Etape 1 (inversion) :
0111 0000 - Etape 2 (rajout de 1) :
0111 0001 - Interprétation : on lit 64+32+16+1 = 113, le code initial encode donc le nombre -113.
09° Quel est l'entier encodé par l'octet 1111 0010 en base 2 si on sait qu'il s'agit d'un entier signé ?
Utiliser d'abord la méthode rapide.
Vérifier en faisant la transformation (inversion + rajout de 1).
...CORRECTION...
1e méthode : on soustrait 28 (puisqu'on utilise un octet) à la valeur brute de l'octet lu comme un entier non signé
- Bits en mémoire :
1111 0010: 242 si on considère qu'il s'agit d'un entier non signé - 242 - 256 = -14
2e méthode : on se souvient comme ça fonctionne.
- Bits en mémoire :
1111 0010 - Etape 1 (inversion) :
0000 1101 - Etape 2 (rajout de 1) :
0000 1110 - Interprétation : on lit 8+4+2 = 14, le code initial encode donc le nombre -14.
10° Quel est l'entier encodé par l'octet 1111 1110 en base 2 si on sait qu'il s'agit d'un entier signé ?
Utiliser d'abord la méthode rapide.
Vérifier en faisant la transformation (inversion + rajout de 1).
...CORRECTION...
1e méthode : on soustrait 28 (puisqu'on utilise un octet) à la valeur brute de l'octet lu comme un entier non signé
- Bits en mémoire :
1111 1110: 254 si on considère qu'il s'agit d'un entier non signé - 254 - 256 = -2
2e méthode : on se souvient comme ça fonctionne.
- Bits en mémoire :
1111 1110 - Etape 1 (inversion) :
0000 0001 - Etape 2 (rajout de 1) :
0000 0010 - Interprétation : on lit 2, le code initial encode donc le nombre -2.
Activité publiée le 06 10 2019
Dernière modification : 25 10 2019
Auteur : ows. h.