Données Int

Identification

Infoforall

2 - Encodage des grands entiers naturels


Nous avons vu que l'ordinateur stocke les données sous forme d'octets.

Mais comment stocker un entier valant plus que 255 ?

Documents de cours : open document ou pdf

1 - Entiers naturels

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 : le premier bit encode 1, le suivant 2, le suivant 4 ...

Dans la plupart des langages, cet encodage est nommé unsigned. Cela veut dire que le nombre n'est pas signé. On ne peut donc représenter que des nombres sans signe.

Nous n'allons pas rentrer dans les détails : nous avons déjà vu dans l'activité précédente comment décoder l'entier naturel encodé par un ensemble de bits.

Pour rappel, voici des exemples sur un octet (8 bits) :

Votre nombre binaire M :

Nombre M =
Les bits codent 1286432168421
On obtient donc

D'ou la valeur de M en base 10 : M = = .

01° Utiliser le petit convertisseur ci-dessus pour trouver la valeur du plus grand entier naturel encodable avec 8 bits à 1 : 11111111. Quelle formule permet de connaitre la valeur maximale encodable par 8 bits ?

...CORRECTION...

On peut voir que (1111 1111)2 = (255)10

La formule permettant de retrouver cette valeur est 28 - 1.

Si on veut encoder des valeurs supérieures à 255, il suffit donc de rajouter des bits supplémentaires à gauche. Ils coderont donc 256, 512, 1024 ...

02° Quels nombres (entiers naturels) permettent d'encoder les deux ensembles de 9 bits suivants :

1 0000 0000

1 0000 0001

...CORRECTION...

Premier cas : seul le bit de poids fort est activé. Le nombre vaut donc 25610.

Nombre M =100000000
Les bits codent 2561286432168421
On obtient donc256

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 =100000000
Les bits codent 2561286432168421
On obtient donc2561

On encode donc le nombre 256 + 1, soit 25710.

Vérifions cela avec Python :

Fonction native bin

La fonction native bin permet d'obtenir un apercu de la codification binaire du nombre entier transmis entre parenthèses.

Elle fournit en sortie un string contenant la suite de bits permettant de représenter ce nombre en binaire.

>>> bin(255) '0b11111111'
>>> bin(255)[2:] '11111111'

03° Lancer un Shell Python (avec Python, IDLE ou Thonny par exemple) et lancer les instructions suivantes :

>>> bin(255) '0b11111111'
>>> bin(256) '0b100000000'
>>> bin(257) '0b100000001'

Qu'est-ce qui indique clairement que la réponse de la fonction native bin est de type string (str en python) ?

Dans cette réponse, qu'est-ce qui semble avoir été choisi pour indiquer qu'on est en train de voir un contenu binaire ?

...CORRECTION...

La présence de guillemets simples autour de la réponse permet de voir qu'il s'agit d'un string.

Ce string contient les valeurs des différents bits. On le différencie des autres strings par le fait qu'il commence par 0b.

Voici un truc permettant d'enlever le 0b. Nous l'expliquerons plus tard lorsque nous traiterons le cas des strings. Retenez pour l'instant qu'il permet visiblement de supprimer les deux premiers caractères.

>>> bin(255)[2:] '11111111'
>>> bin(256)[2:] '100000000'
>>> bin(257)[2:] '100000001'

Et si on veut un entier sur 8 bits ? 16 bits ?

Il faut encore rajouter un terme derrière notre string. Il s'agit de la méthode zfill qui permet de rajouter à gauche des caractères pour compléter les caractères. Par défaut, c'est un '0', ça tombe bien.

>>> bin(100)[2:].zfill(8) '01100100' >>> bin(100)[2:].zfill(16) '0000000001100100'

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

Et si on dispose d'un contenu binaire sous forme 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) 3
>>> int('0b11',2) 3
>>> int('11',2) 3

En réalité, on ne stocke jamais 9 bits ou 10 bits.

L'ordinateur travaille toujours avec un nombre entier d'octets :

  • 1 octet (soit 8 bits)
  • 2 octets (soit 16 bits)
  • 4 octets (soit 32 bits)
  • 8 octets (soit 64 bits)

2 - Plusieurs octets

Catégories d'entiers naturels (simple culture générale)

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 !

Alors, comment décoder une série d'octets caractérisant un nombre ?

Par exemple :

  •  1  10 soit  0000 0001  2
  •  2  10 soit  0000 0010  2
  •  3  10 soit  0000 0011  2
  •  4  10 soit  0000 0100  2

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 : les nombres sont  1  10,  2  10,  3  10 et  4  10. Facile.

Cas de l'encodage sur deux octets

Quel entier peuvent représenter une séquence de deux octets contenant Y =  0000 0111  et Z =  0111 0000  ?

Tentons de l'expliquer :

Nombre M = 0000 0111 0111 0000
Poids 327681638481924096 20481024512256 128643216 8421

On obtient donc N = 1024+512+256+64+32+16 = 1904.

C'est bien supérieur à 255, valeur maximale sur un octet.

C'est facile à comprendre, mais long à décoder. Voyons comment faire plus rapide avec les puissances de 2 :

Nombre M = 0000 0111 0111 0000
Poids 215214213212 2112102928 27262524 23222120

Et là, il suffit d'utiliser 2a+b = 2a * 2b.

Nombre M = 0000 0111 0111 0000
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 doncPremier octetDeuxième octet

Et donc, on voit bien qu'on peut simplifier la lecture des 16 bits en les séparant en deux lectures d'octets. Il suffit de multiplier le premier octet par 28 qui vaut 256.

Nombre M = 0000 0111 0111 0000
Poids 27262524 23222120 27262524 23222120
On obtient doncPremier octet Y valant 4 + 2 + 1 = 7Deuxième octet Z valant 64 + 32 + 16 = 112

Et voilà.

Nombre M = 0000 0111 0111 0000
Poids 128643216 8421 128643216 8421
On obtient donc256 * Y = 256 * 7 = 17921 * X = 1 * 112 = 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

Avec une séquence de 2 octets, on dispose de 16 bits.

On dispose donc de 216 valeurs, soit 65536.

On peut donc représenter des nombres variant de 0 à 65535.

Soit un nombre N encodé comme une séquence de deux octets  Y   Z .

L'octet le plus à gauche,  Y , est l'octet de poids fort. Son premier bit n'encode donc pas 20 (1) mais 28 (256).

En base 10, on trouve donc le nombre N encodé en calculant ceci :

N = Y * 256 + Z.

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 1 :  1   2  ou en version binaire  0000 0001   0000 0010 
  • Nombre 2 :  3   4  ou en version binaire  0000 0011   0000 0100 

...CORRECTION...

  • Nombre 1 = 1 * 256 + 2 = 258
  • Nombre 2 : 3 * 256 + 4 = 772

Cas de l'encodage sur quatre octets

Sur 4 octets, c'est donc le même principe :

Encodage d'un entier non signé sur 4 octets

Avec une séquence de 4 octets, on dispose de 32 bits.

On dispose donc de 232 valeurs, soit 4 294 967 296.

On peut donc représenter des nombres variant de 0 à 4 294 967 295. Un peu plus que 4 milliards.

Soit un nombre N encodé comme une séquence de quatre octets  W   X   Y   Z .

Le bit de poids faible de l'octet  Y  encode donc 28 (256).

Le bit de poids faible de l'octet  X  encode donc 216 (65536).

Le bit de poids faible de l'octet  W  encode donc 224 (16777216).

En base 10, on trouve donc le nombre N encodé en calculant ceci :

N = W*16777216 + X*65536 + Y*256 + Z.

07° En considérant un encodage sur 4 octets d'entiers naturels, déterminer la valeur encodée par la suite d'octets suivante :  1   2   3   4 

En version binaire, cela donne  0000 0001   0000 0010   0000 0011   0000 0100 

...CORRECTION...

Il suffit de réaliser le calcul suivant :

Nombre = 1*2**24 + 2*2**16 + 3*2**8 + 4

Nombre = 16 909 060.

Nous allons vérifier cela en utilisant Python :

08° Utiliser le code proposé pour voir comment vous pourriez un peu automatiser la recherche des octets :

Remarque : nous verrons dans l'activité sur les strings que [0:8] veut dire de prendre les caractères d'index 0 jusqu'à l'index 7, le 8e n'est pas pris. Attention donc à cette histoire de premier élément qui porte le numéro 0.

>>> bits = bin(16909060)[2:] >>> bits '1000000100000001100000100'

Visuellement, nous allons montrer ceci en groupant les octets par 8 :

'1 0000 0010 0000 0011 0000 0100'

Nous pouvons récupérer les bits des différents octets de la façon suivante :

  • L'octet w ne contient que le bit d'index 0 du string des bits (le premier) : 1.
  • L'octet x contient les bits d'index 1 à 8 : 0000 0010.
  • L'octet y contient les bits d'index 9 à 16 : 0000 0011
  • L'octet z contient les bits d'index 17 et plus : 0000 0100

Sans trop faire d'automatisation et rajouter de nouvelles connaissances, cela donne donc 

>>> w = bits[0] >>> w '1' >>> int(w, 2) 1
>>> x = bits[1:9] >>> x '00000010' >>> int(x, 2) 2
>>> y = bits[9:17] >>> y '00000011' >>> int(y, 2) 3
>>> z = bits[17:] >>> z '00000100' >>> int(z, 2) 4

Mais pourquoi multiplier X par 216 et W par 224 ?

Tout simplement car on décale de 8 bits à chaque fois.

Or 28 * 28 = 28+8 = 216

C'est la même chose pour W : on décale trois fois de 8 bits. D'où 28 * 28 * 28 = 28+8+8 = 224

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 peut y avoir un cas de figure particulier : on additionne deux entiers (sur 2 octets chacun) mais le résultat final ne tient pas sur deux octets : il en faudrait au moins un troisième.

Addition de nombre binaire

Nous avons vu l'addition de 1 dans l'activité précédente.

C'est pareil, si ce n'est qu'on travaille sur tous les bits à la fois. Attention à la retenue donc.

Pour rappel, en binaire, on obtient ceci

  •  0  +  0  =  0 
  •  0  +  1  =  1 
  •  1  +  1  =  10 
  •  1  +  1  +  1  =  11 
    • Exemple pas à pas

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ?
      N = A + B 1

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ?
      N = A + B 01

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 1 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 11 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1
      N = A + B 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 0 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 10 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 110 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 1110 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 1 1110 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1
      N = A + B 01 1110 0111 1001

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1 +1
      N = A + B 001 1110 0111 1001

      Au final

      Nombre A 0101 0101 0101 0101
      Nombre B 0100 1001 0010 0100
      Retenue ? +1 +1 +1
      N = A + B 1001 1110 0111 1001

09° Réaliser l'addition suivante sur votre copie . Le contenu du tableau est éditable pour éviter de recopier l'énoncé. Ne notez que le résultat.

Nombre A 0101 0101 0101 0111
Nombre B 0100 1001 0010 0110
Retenue ?
N = A + B

...CORRECTION...

Nombre A 0101 0101 0101 0111
Nombre B 0100 1001 0010 0110
Retenue ? +1





+1





+1
+1


N = A + B 1
0
0
1
1
1
1
0
0
1
1
1
1
1
0
1

10° Réaliser l'addition suivante sur votre copie . Le contenu du tableau est éditable pour éviter de recopier l'énoncé. Ne notez que le résultat.

Quel est le problème ?

Nombre A 1101 0101 0101 0111
Nombre B 0100 1001 0010 0110
Retenue ?
N = A + B

...CORRECTION...

Nombre A 1101 0101 0101 0111
Nombre B 0100 1001 0010 0110
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.

Voilà. C'est à cause de ce dépassement que le robot de l'activité 1 retournait à une vitesse de 0.

La vitesse maximale 1111 1111 devenait 10000 0000.

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.

4 - big endian et little endian

Un problème technique arrive lorsqu'on veut stocker puis relire les contenus en mémoire : il faut savoir dans quel ordre on les place !

Big endian ou gros boutisme

On place le contenu de façon à ce que l'octet de poids fort soit lu en premier.

Imaginons qu'on veuille stocker 25800 en mémoire.

N = 100*256 + 200 = 25800

En mémoire, le 100 devra apparaître en premier lors de la lecture.

On stocke donc 100 200.

Little endian ou petit boutisme

On place le contenu de façon à ce que l'octet de poids faible soit lu en premier.

Imaginons qu'on veuille stocker 25800 en mémoire.

N = 100*256 + 200 = 25800

En mémoire, le 200 devra apparaître en premier lors de la lecture.

On stocke donc 200 100.

Dans la prochaine activité, nous verrons comment coder les entiers négatifs, puis les flottants.

Activité publiée le 22 09 2019
Dernière modification : 29 09 2019
Auteur : ows. h.