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.
  • x ∈ [ 0 ; 255 ] ou
  • x ∈ [ 0 ; 28-1 ]

Nous avons vu qu'avec deux octets (16 bits) :

  • on obtient 216 (65536) valeurs différentes.
  • x ∈ [ 0 ; 65535 ] ou
  • x ∈ [ 0 ; 216-1 ]

...

Mais comment stocker un entier relatif, un entier pouvant être positif ou négatif ?

Documents de cours : open document ou pdf

1 - Combien de positifs ? Combien de négatifs ?

1.1 - 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é par + ou par -.

Les nombres entiers -5 ou +5 sont donc membres de ℤ.

1.2 - Nombre de valeurs encodées

On sépare les possibilités en deux :

  • Une moitié pour encoder les valeurs positives (dont le 0).
  • L'autre moitié pour encoder les valeurs négatives.

Ainsi :

  • Avec un octet
  • Avec deux octets

Avec les entiers naturels : les X bits servent à encoder la valeur

2X valeurs disponibles (dont le 0).

On obtient l'encadrement suivant :

x ∈ [ 0 ; 2X -1 ]

Avec les entiers relatifs : l'un des X bits est le bit de signe.

2X-1 valeurs disponibles pour chaque signe (le 0 étant dans les valeurs positives).

On obtient l'encadrement suivant :

x ∈ [ -2X-1 ; 2X-1 -1 ]

Exemple

Avec un octet (8 bits) :

x ∈ [ -27 ; 27 -1 ] soit

x ∈ [ -128 ; +127 ]

01° Déterminer l'encadrement des entiers relatifs encodables par un ensemble de 4 bits.

...CORRECTION...

Avec 4 bits, on a l'encadrement
x ∈ [ -23 ; 23 -1 ] soit
x ∈ [ -8 ; +7 ]

02° Déterminer l'encadrement des entiers relatifs encodables par un ensemble de 2 octets.

...CORRECTION...

2 octets forment 16 bits.

Avec 16 bits, on a l'encadrement
x ∈ [ -215 ; 215 -1 ] soit
x ∈ [ -32768 ; +32767 ]

03° Déterminer l'encadrement des entiers relatifs encodables par un ensemble de 4 octets.

...CORRECTION...

4 octets forment 32 bits.

Avec 32 bits, on a l'encadrement x ∈ [ -231 ; 231 -1 ] soit x ∈ [ -2147483648 ; +2147483647 ]

Comprennez bien que le décalage entre les deux extrême est dû au fait que 0 est un nombre positif.

La solution la plus "évidente" pour encoder des nombres positifs ou négatifs ?

Encodage simple mais non fonctionnel

On utilise le bit le plus à gauche pour encoder le signe du nombre :

  • Si le bit le plus à gauche est 0, c'est un nombre positif
  • Si le bit le plus à gauche est 1, c'est un nombre négatif

Les autres bits encodent directement la valeur absolue.

  • (+1) est encodé par  0000 0001 
  • (-1) est encodé par  1000 0001 
  • (+2) est encodé par  0000 0010 
  • (-2) est encodé par  1000 0010 
  • (+3) est encodé par  0000 0011 
  • (-3) est encodé par  1000 0011 

C'est simple mais ... ça ne fonctionne pas vraiment.

Premier problème : le nombre 0 posséderait deux encodages possibles :

 0000 0000  et  1000 0000 

Deuxième problème : l'addition ne fonctionnerait plus !

Nous savons que 3 + (-3) = 0

Essayons (sur 4 bits) avec +3 - 3, qui devrait donner 0...

Nombre +310 0011
Nombre -510  1011
Retenue ?  +1+1
Somme  1110

Pas de dépassement mais on obtient  1110 , soit -(4+2+0) = -6.

Pas 0...

Voyons comment faire pour obtenir 0.

2 - Complément à deux (version humain)

2.1 - Principe du complément à 2

Modulo

Nous allons utiliser le modulo.

Un angle possède 360 valeurs allant de 0 à 359°.

Après 359°, on atteint un angle de 360°, équivalent à un angle de 0°.

De la même façon 370° est équivalent à 10°.

En Python, on noterait

>>> 360 % 360 0 >>> 370 % 360 10

Même principe avec le dépassement sur un octet : nous avons 256 valeurs allant de 0 à 255.

Après la valeur 255, on atteint 256 donc on revient à 0 !

>>> 256 % 256 0 >>> 2**8 % 2**8 10

En Python, on notera

2.1 - 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 le plus à gauche pour stocker l'information signe 

  •  0 , c'est positif.
  •  1 , c'est négatif.

Cas des nombres positifs

Rien ne change par rapport au cas des nombres entiers naturels. On a juste un bit en moins pour stocker la valeur du nombre.

Sur un octet (8 bits), on a donc 1 bit de signe et 7 bits de valeur.

Sur un octet, la valeur positive maximale est donc encodée par 7 bits à 1, comme ceci :

Valeurs stockées01111111
Les bits codent +6432168421

La valeur maximale positive est donc 64 + 32 + 16 + 8 + 4 + 2 + 110, soit 12710.

Cas des nombres négatifs

Pour encoder un nombre négatif en utilisant le complément à deux, il faut suivre ces étapes 

  1. Trouver l'encodage du nombre positif correspondant (5 si on cherche -5)
  2. Inverser tous les bits (opération qu'on nomme complément à 1)
    •  0  devient  1 
    •  1  devient  0 
  3. Rajouter 1 (sur le bit de poids faible donc) en ignorant le dépassement éventuel
2.2 - Quelques exemples

Exemple avec -1

Code signe 64 32 16 8 4 2 1
A) Encodage de +1 0 0 0 0 0 0 0 1
B) Inversion 1 1 1 1 1 1 1 0
C) Rajout de 1 +1
Retenue ?
Résultat final : l'encodage de -1 1 1 1 1 1 1 1 1

La représentation du nombre signé -1 est donc  1111 1111 .

Si on décode ce contenu comme un entier non signé, on obtient 255 !

Exemple avec -6

Code signe 64 32 16 8 4 2 1
A) Encodage de +6 0 0 0 0 0 1 1 0
B) Inversion 1 1 1 1 1 0 0 1
C) Rajout de 1 +1
Retenue ? +1
Résultat final : l'encodage de -6 1 1 1 1 1 0 1 0

Dans cette représentation, le nombre -6 est encodé par un octet valant  1111 1010 2.

Si on décode ce contenu comme un entier non signé, on obtient 250.

Cas du 0

Code Dép. signe 64 32 16 8 4 2 1
A) Encodage de +0 0 0 0 0 0 0 0 0
B) Inversion 1 1 1 1 1 1 1 1
C) Rajout de 1 1
Retenue ? +1+1+1+1+1+1+1+1
Résultat final : encodage de -0 1 0 0 0 0 0 0 0 0

Comme on ne tient pas compte du dépassement, on obtient bien  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.

04° Utiliser le complément à deux pour montrer que -2 10 s'encode par  1111 1110  sur 1 octet.

Quelle est la valeur obtenue si on décode cet octet comme un entier naturel ?

Vérifier en tapant ceci dans une console Python :

>>> 0b11111110

Attention : La fonction native int() convertit toujours les contenus binaires fournis de cette façon en entier naturel.

...CORRECTION...

Code signe 64 32 16 8 4 2 1
A) Encodage de +2 0 0 0 0 0 0 1 0
B) Inversion 1 1 1 1 1 1 0 1
C) Rajout de 1 +1
Retenue ? +1
Résultat final : encodage de -2 1 1 1 1 1 1 1 0

La représentation de -2 10 est donc  1111 1110 .

En décodant comme un entier naturel, cela représenterait 254.

05° Utiliser le complément à deux sur un octet pour montrer que -3 10 s'encode  1111 1101 .

Quelle est la valeur de l'octet lu comme un entier naturel ?

...CORRECTION...

Code signe 64 32 16 8 4 2 1
A) Encodage de +3 0 0 0 0 0 0 1 1
B) Inversion 1 1 1 1 1 1 0 0
C) Rajout de 1 +1
Retenue ?
Résulat final : encodage de -3 1 1 1 1 1 1 0 1

La représentation de -310 est donc  1111 1101 .

En décodant comme un entier naturel, cela représenterait 253.

06° Utiliser le complément à deux sur un octet pour montrer que -13 10 s'encode  1111 0011 .

...CORRECTION...

Code signe 64 32 16 8 4 2 1
A) Encodage de +13 0 0 0 0 1 1 0 1
B) Inversion 1 1 1 1 0 0 1 0
C) Rajout de 1 +1
Retenue ?
Résultat final : encodage de -13 1 1 1 1 0 0 1 1

La représentation de -1310 est donc  1111 0011 .

En décodant comme un entier naturel, cela représenterait 252.

07° Utiliser le complément à deux sur un octet pour montrer que -26 10 s'encode  1110 0110  sur un octet.

Il faudra donc d'abord trouver comment encoder 26.

...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.

On active le 16. Il reste 26-16 = 10 à obtenir.

On active le 8. Il reste 10-8 = 2 à obtenir.

On active le 2. Il reste 2-2 = 0 à obtenir. C'est fini.

On obtient donc :

Code signe 64 32 16 8 4 2 1
A) Encodage de +26 0 0 0 1 1 0 1 0
B) Inversion 1 1 1 0 0 1 0 1
C) Rajout de 1 +1
Retenue ? +1
Encodage de -26 1 1 1 0 0 1 1 0

On obtient donc l'encodage suivant :  1110 0110 

En décodant comme un entier naturel, cela représenterait 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
A) Encodage de +26 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0
B) Inversion 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1
C) Rajout de 1 +1
Retenue ? +1
Résultat final : 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 16 bits en deux octets :  1111 1111   1110 0110 

En utilisant deux octets, le nombre -26 est donc encodé par 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 un contenu binaire dont on sait qu'il encode un entier signé.

Commençons par voir ce qu'on pourrait faire avec un quartet (4 bits).

Nombre décimal encodé Contenu du quartet en binaire Entier non signé correspondant
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 

Comment décoder ces octets s'ils encodent des entiers relatifs ?

Avec le complément à deux, on utilise simplement le complément à deux dans ce sens là également.

3.1 - Décoder un entier relatif

Si le bit de signe vaut 0 : on décode comme s'il s'agissait d'un entier naturel.

Si le bit de signe vaut 1 :

  • A) On écrit le contenu binaire encodant un entier négatif.
  • B) On réalise l'inversion
  • C) On rajoute 1.
  • D) On décode le contenu comme s'il s'agissant d'un entier naturel N
  • E) L'entier négatif encodé est alors simplement -N
3.2 - Exemple

Qu'encode 1110 0111 si on sait qu'il s'agit d'un entier relatif ?

A) on place notre contenu 1 1 1 0 0 1 1 1
B) Inversion 0 0 0 1 1 0 0 0
C) Rajout de 1 +1
Retenue ?
D) Décodage comme un entier naturel 0 0 0 1 1 0 0 1
Code 128 64 32 16 8 4 2 1

Le contenu  1110 0111  est donc décodé comme -25 car on lit 25 lors de l'étape D.

08° 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
négatif mais combien ?  1001 
négatif mais combien ?  1010 

...CORRECTION...

A) on place le contenu 1 0 0 1
B) Inversion 0 1 1 0
C) Rajout de 1 +1
Retenue ?
D) Décodage comme un entier naturel 0 1 1 1
Code 8 4 2 1

Le quartet contenant  1001  peut donc être décodé par -7 10 puisque le nombre lu à l'étape D est 7.

...CORRECTION...

A) placement des bits 1 0 1 0
B) Inversion 0 1 0 1
C) Rajout de 1 +1
Retenue ? +1
D) Décodage comme un entier naturel 0 1 1 0
Code 8 4 2 1

Le quartet contenant  1010  peut donc être décodé par -6 10 puisque le nombre lu à l'étape 4 est 6.

3.3 - Cas particulier d'un 1 pour le bit de signe suivi uniquement de 0

Il s'agit des contenus dont les bits forment une séquence de ce type :

  •  1000 
  •  1000 0000 
  •  1000 0000 0000 0000 
  • ...
A) placement des bits 1 0 0 0
B) Inversion 0 1 1 1
C) Rajout de 1 +1
Retenue ? +1+1+1
D) Décodage comme un entier naturel 1 0 0 0
Code 8 4 2 1

On revient à la même chose !

Ce contenu du quartet va donc simplement nous permettre d'encoder -8 puisqu'on lit 8 à l'étape D.

Si on décode un contenu de ce type en sachant qu'on a encodé un entier relatif :

  •  1000  encode -8
  •  1000 0000  donne -128
  •  1000 0000 0000 0000  donne -32768
  • ...

Nous pouvons donc maintenant écrire notre table pour le quartet 

Contenu binaire Décodé comme un entier relatif Décodé comme un entier naturel
 0000  0 0
 0001  1 1
 0010  2 2
 0011  3 3
 0100  4 4
 0101  5 5
 0110  6 6
 0111  7 7
 1000  -8 8
 1001  -7 9
 1010  -6 10
 1011  -5 11
 1100  -4 12
 1101  -3 13
 1110  -2 14
 1111  -1 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 - Pourquoi complément à deux ?

L'ordinateur utilise la méthode que nous avons vu : inversion des bits et rajout de 1. Pour lui, ces opérations sur les bits sont très rapide.

Mais pour un humain, c'est long. Voyons comment réaliser cela plus efficacement pour nous, les humains.

4.1 - Formule permettant de trouver le nombre relatif encodé

Pour décoder sous forme d'un entier relatif un contenu binaire de X bits dont le bit de signe est à 1, il suffit d'appliquer cette formule :

(bits décodés comme entier négatif) = (bits décodés comme entier naturel) - 2X

Exemple 1 :  1111 1111 

  • 8 bits : X = 8
  • (  1111 1111  décodés comme un entier naturel) = 255.
  • (  1111 1111  décodés comme un entier négatif) = 255 - 28 = 255 - 256 = -1

Exemple 2 :  1000 0000 

  • 8 Bits de contenu : X = 8
  • (  1000 0000  décodés comme un entier naturel) = 128
  • (  1000 0000  décodés comme un entier négatif) = 128 - 28 = 256 = -128

Exemple 3 :  1000 0000 1111 1111 

  • 16 Bits de contenu : X = 16
  • ( 1000 0000 1111 1111  décodés comme un entier naturel) = 33023
  • ( 1000 0000 1111 1111  décodés comme un entier négatif) = 33023 - 216 = 33023 - 65536 = -32513

09° 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 la formule.

...CORRECTION...

  • 8 bits : X = 8
  • (  1000 1111  décodés comme un entier naturel) = 143
  • (  1000 1111  décodés comme un entier négatif) = 143 - 28 = 143 - 256 = -113

10° 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...

  • 8 bits : X = 8
  • (  1111 0010  décodés comme un entier naturel) = 242
  • (  1111 0010  décodés comme un entier négatif) = 242 - 28 = 242 - 256 = -14

11° 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...

  • 8 bits : X = 8
  • (  1111 1110  décodés comme un entier naturel) = 254
  • (  1111 1110  décodés comme un entier négatif) = 254 - 28 = 254 - 256 = -2
4.2 - Trouver les bits d'encodage d'un nombre relatif

Il s'agit juste d'aller dans l'autre sens, et donc de transformer la formule pour placer ce qu'on cherche à gauche.

Retrouver la formule à partir de la précédente

On peut écrire cette valeur en inversant les deux côtés.

a = b - c

b - c = a

b = a + c

Appliqué à notre formule cela donne ceci :

(bits décodés comme entier négatif) = (bits décodés comme entier naturel) - 2X

(bits décodés comme entier naturel) - 2X = (bits décodés comme entier négatif)

(bits décodés comme entier naturel) = 2X + (bits décodés comme entier négatif)

Appliquer la formule

Imaginons qu'on veuille savoir comment encoder -239 sans passer par la méthode de l'inversion et du rajout de 1.

(bits décodés comme entier naturel) = 28 + (bits décodés comme entier négatif)

(bits décodés comme entier naturel) = 256 + (-239)

(bits décodés comme entier naturel) = 17

 0001 0001  = 17

On vient de montrer que  0001 0001  peut se décoder comme l'entier naturel 17 ou comme l'entier relatif -239.

4.3 - Pourquoi le nom "complément à deux" ?

En réalité, le nom devrait être "complément à 2x". Cela vient du fait que connaissant la relation entre l'encodage de la valeur positive x et l'encodage de la valeur négative -x est lié à 2x.

5 - FAQ

Rien pour l'instant

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.