Données Entiers relatifs

Identification

Infoforall

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 encoderr les nombres (+5)10 ou (-5)10, on stocke 0101 ou 1101

Nombre +510 0101
Nombre -510 1101
Retenue ? +1+1+1
Somme 10010

Si on considère que le bit de signe et toujours le bit le plus à droite, on obtient 10010, soit  -2 10 !

Bref, ce serait simple mais ça ne fonctionnerait pas. On ne fait donc pas comme cela pour le stockage des entiers relatifs en mémoire.

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ées01111111
Les bits codent +6432168421

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)
    •  0  devient  1 
    •  1  devient  0 
  • 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 1 1 1 1 1 1 1 0
Rajout 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  255 10 ou  1111 1111 2)
  • 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 1 1 1 1 1 0 0 1
Rajout de 1 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 1 1 1 1 1 1 1 1
Rajout de 1 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 un Shell 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
Rajout de 1 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 1 1 1 1 1 1 0 0
Rajout de 1 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 1 1 1 1 0 0 1 0
Rajout de 1 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
Octet de +26 0 0 0 1 1 0 1 0
Inversion 1 1 1 0 0 1 0 1
Rajout de 1 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
Octet de +26 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0
Inversion 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1
Rajout de 1 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 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 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 :

  •  1000 
  •  1000 0000 
  •  1000 0000 0000 0000 
  • ...
Lecture des bits 1 0 0 0
Inversion 0 1 1 1
Rajout de 1 1 0 0 0
Code Signe ? 4 2 1

On revient à la même chose ! Comme avec le zéro.

Souvenez-vous : on suppose qu'on décode un contenu négatif puisque le bit de signe est initialement à 1.

Ce contenu du quartet va donc simplement nous permettre d'encoder -8.

Si on résume :

  •  1000  donne -23 soit -8
  •  1000 0000  donne -27 soit -128
  •  1000 0000 0000 0000  donne -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 - Méthode calculatoire rapide

Pourquoi la technique se nomme complément à 2 ?

Bonne question.

En réalité, le nom entier est complément à 2N ou 2X, où N ou X représente le nombre de bits disponibles.

Voici le truc pour trouver rapidement ce que représente un entier signé commençant par 1.

  1. On interprète ces bits comme un entier non signé
  2. On retranche 2X où X est le nombre de bits utilisés en mémoire.

Exemple 1 :

  • 8 Bits en mémoire : 1111 1111 : 255 si on considère qu'il s'agit d'un entier non signé
  • 255 - 256 = -1
  • 1111 1111 encode donc -1.

Exemple 2 :

  • 8 Bits en mémoire : 1000 0000 : 128 si on considère qu'il s'agit d'un entier non signé
  • 128 - 256 = -128
  • 1000 0000 encode donc -1.

Exemple 3 :

  • 16 Bits en mémoire : 1000 0000 1111 1111 : 33023 si on considère qu'il s'agit d'un entier non signé
  • 33023 - 216 = 33023 - 65536 = -32513
  • 1000 0000 1111 1111 encode donc -32513.

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.

Dans une prochaine activité, nous verrons avec plus de précision les dépassements de capacité et le nombre de bits nécessaires aux opérations d'addition et de multiplication.

Activité publiée le 06 10 2019
Dernière modification : 25 10 2019
Auteur : ows. h.