• 15 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/10/2019

Codez en binaire les entiers naturels et relatifs

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Les entiers naturels

La représentation des nombres au sein d'un ordinateur repose sur le principe de l'électronique binaire : les composants électroniques exploitent et élaborent des tensions binaires. Une telle tension binaire ne peut prendre que deux valeurs clairement distinctes, historiquement, 0 V et 5 V.

Quoi qu'il en soit, on représente généralement la tension basse, souvent 0 V, par un « 0 » logique et la tension haute, par exemple, 1,8 V, par un « 1 » logique. Dans la suite, nous ne ferons référence qu'aux valeurs logiques des tensions, sans préciser les niveaux de tension en volts auxquels elles correspondent. Il s'agit donc d'un premier niveau d'abstraction, pour se dégager de la réalisation matérielle, qu'il importe de s'approprier.

Exemple de circuit à affichage numérique
Exemple de circuit à affichage numérique

La question qui se pose d'emblée : comment représenter un nombre quelconque avec uniquement deux niveaux logiques ?

La réponse réside dans la numération de base 2. Tout comme les nombres dans la vie courante sont représentés en base 10, l'ordinateur représente les nombres quelconques comme combinaisons des puissances de 2. Dans la vie courante, en base 10, les nombres sont représentés comme somme pondérée des puissances de 10. Les poids ou coefficients prennent 10 valeurs possibles, les chiffres arabes de 0 à 9. Ainsi, par exemple :

  $\(2018=2.10^3 + 0.10^2 +1.10^1 + 8.10^0\)$

En base 2, ce même nombre est représenté comme somme pondérée des puissances de 2, avec comme seuls poids possibles 0 et 1. Ainsi :

  $\(2018=1024+512+256+128+64+32+2\)$

Cette dernière valeur qui représente 2018 en base 2 est obtenue en représentant les poids (0 ou 1) des puissances de 2 selon le tableau qui suit :

1024

512

256

128

64

32

16

8

4

2

1

$\(2^{10}\)$

$\(2^9\)$

$\(2^8\)$

$\(2^7\)$

$\(2^6\)$

$\(2^5\)$

  $\(2^4\)$

$\(2^3\)$

$\(2^2\)$

$\(2^1\)$

$\(2^0\)$

1

1

1

1

1

1

0

0

0

1

0

 En l'occurrence, il faut 11 bits (binary units) pour représenter 2018. On vérifiera aisément que n bits permettent de représenter selon ce principe les entiers naturels compris entre 0 et $\(2^n -1\)$. Classiquement, les nombres codés en 8 bits permettent de représenter les entiers naturels entre 0 et 255. Sur 10 bits ( $\(2^{10}=1024\)$), on peut représenter les entiers naturels entre 0 et 1 023. Quand on pratique régulièrement le système binaire, on finit par retenir sans effort de mémoire, juste par assimilation, les puissances entières de 2, ou bien, on les recalcule rapidement selon la liste :

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1 024, 2 048, 4 096, 8 192, 16 384, etc.

Conversion binaire vers décimal et décimal vers binaire

Les microprocesseurs et microcontrôleurs actuels manipulent des groupes de bits appelés BUS, pour Binary Unit Systems, dont la taille va généralement de 8 bits (pour les microcontrôleurs peu puissants destinés à des applications simples souvent embarquées) à 32, voire 64 bits pour les microprocesseurs d’ordinateurs puissants.

Si on veut représenter l’état électrique des, par exemple, 16 bits de données, il est exclu de travailler en binaire parce qu’il faut écrire 16 digits à 0 ou 1, ce qui est laborieux, à plus forte raison avec 32 bits ou 64 bits. On pourrait penser à représenter ces nombres manipulés par les systèmes numériques en décimal, qui est notre système de représentation du quotidien.

Toutefois, on ne le fait pas car les conversions de binaire vers décimal et surtout de décimal vers binaire sont laborieuses, parce que 10 n’est pas une puissance entière de 2. Nous verrons un peu plus loin, dans le chapitre 3,  qu’on a tout intérêt à travailler avec un système de numération dont la base est une puissance entière de 2, par exemple 8, 16 ou 32. Historiquement, le système octal a existé (base 8), mais est aujourd’hui abandonné.

Revenons aux conversions de binaire vers décimal et de décimal vers binaire, même si ces conversions n’offrent pas beaucoup d’intérêt opérationnel.

Pour la conversion binaire vers décimal, elle est immédiate pour peu qu’on connaisse ou qu’on recalcule les puissances entières de 2. Ci-dessous, un exemple sur 10 bits.

512

256

128

64

32

16

8

4

2

1

1

0

0

1

1

0

0

0

1

1

On obtient immédiatement 512+64+32+2+1=611

Pour la conversion décimal vers binaire, on se contente d’en regarder le principe et un exemple pour des nombres qui restent relativement petits. La méthode consiste à identifier la puissance entière de 2 immédiatement inférieure au nombre à convertir, à placer un 1 dans la colonne correspondante et à retrancher cette puissance de 2 au nombre à convertir. On réapplique la même méthode sur le reste, jusqu’à arriver aux puissances  $\(2^1\)$ et $\(2^0\)$ . Concrètement, on n’a pas vraiment besoin de ce procédé dit par récurrence. Un exemple vaut mieux qu’un long discours.

Cherchons l’équivalent binaire de 1969 (on a marché sur la Lune, grâce aux ordinateurs, d’ailleurs !).

Il est clair qu'il faut incorporer 1 024 comme puissance entière de 2 la plus grande. Ensuite, on additionne les puissances entières de 2 suivantes et on calcule à chaque nouveau terme la somme partielle.

1024

512

256

128

64

32

16

8

4

2

1

1

1

1

1

0

1

1

0

0

0

1

On peut un peu détailler la procédure :

$\(1024 + 512 + 256 + 128\)$

Cette somme partielle atteint 1920, qui est bien inférieur à 1969. Si on ajoute 64 à cette somme partielle, on dépasse ; donc on met à 0 la colonne qui correspond à 64 et on essaie d’ajouter 32, soit 1952. On peut ajouter 16, ce qui porte la somme partielle à 1968. Il reste à ajouter 1 et on est arrivé à 1969.

Cette méthode est rapide. Elle possède la vertu de vous faire mémoriser les premières puissances de 2, mais elle est réservée à des nombres pas trop grands, sinon elle devient très fastidieuse.

Les entiers relatifs

La méthode précédente permet de coder l'ensemble des entiers naturels sans limitation, pour peu qu'on ajoute des bits. Il nous faut à présent une méthode pour coder les entiers relatifs, positifs et négatifs. Une première proposition serait la suivante :

Proposition naïve

L'idée immédiate mais naïve consiste à consacrer le bit d'extrême gauche comme bit de signe, 0 pour les nombres positifs et 1 pour les négatifs : avec 9 bits, par exemple, on représente les entiers compris entre -255 et +255. Mais le nombre 0 est représenté deux fois, 0 0000 0000 (+0) et 1 0000 0000 (-0) et surtout la somme de deux nombres opposés n'est pas nulle, ce qui est gênant. Ainsi, si on effectue 214 + (-214), on obtient :

 

 bit de report

bit de signe

128

64

32

16

8

4

2

1

214

 

0

1

1

0

1

0

1

1

0

-214

 

1

1

1

0

1

0

1

1

0

somme

1

1

1

0

1

0

1

1

0

0

Qui est visiblement non nul !

Pour effectuer cette somme, on procède colonne par colonne comme en base 10. Chaque colonne ou étage est susceptible de générer un report ou retenue pour l'étage suivant selon la règle simple suivante : 0+0=0 pas de report, 0+1=1+0=1 pas de report, 1+1=0 avec un report à 1 et enfin, 1+1+1=1 et un report (le dernier 1 de la somme provient du report de l'étage précédent).

Si on examine le résultat final, on constate qu’un dernier report a été propagé dans un 10e bit. Mais surtout, le résultat sur 9 bits est non nul, ce qui est inacceptable sur un plan mathématique.

Il faut donc trouver une autre méthode que cette idée naïve qui ne convient pas.

Complément à 2

Pour résoudre le problème, on définit le complément à 2 d'un entier positif qui représente son opposé, de manière à ce que la somme de deux entiers opposés soit bien égale à 0. Pour obtenir le complément à 2, il suffit de retenir la recette qui est très simple et qui se déroule en deux étapes vraiment élémentaires. La première étape consiste à complémenter chaque bit du nombre entier positif avec son bit de signe à 0,

 

bit de signe

128

64

32

16

8

4

2

1

+214

0

1

1

0

 1

0

1

1

0

complément à 1

1

0

0

1

 0

1

0

0

1

complément à 2, soit -214

1

0

0

1

 0

1

0

1

0

auquel on a ajouté le bit de signe à 0 comme dans la méthode naïve : cela signifie qu'un bit à 0 passe à 1 et un bit à 1 passe à 0. On obtient ainsi le complément à 1. Puis, la seconde étape consiste à ajouter le nombre 1 au complément à 1.

Si on somme à présent les deux entiers opposés, soit 214 + (-214), on obtient :

214

 

0

1

1

0

1

0

1

1

0

-214

 

1

0

0

1

0

1

0

1

0

somme

1

0

0

0

0

0

0

0

0

0

Certes, il y a un dernier report qui passe dans un dixième bit, mais sur 9 bits, la somme de deux entiers opposés est bel et bien nulle.

Selon vous (vous pouvez essayer sur l'exemple précédent), le complément à 2 d'un entier négatif représenté en complément à 2 redonne-t-il l'entier positif d'origine ?

Soustraction

Du point de vue de l’arithmétique, nous sommes maintenant en mesure d’effectuer des soustractions entre deux nombres codés en binaire. Il suffit de faire l’addition du premier opérande avec l’opposé du second opérande en complément à 2.

Nous traitons un exemple avec des nombres codés sur 10 bits, soit 9 bits pour la valeur absolue plus 1 bit de signe. Nous voulons effectuer 415 – 289.

Nous commençons par représenter +415, ce qui donne :

0

1

1

0

0

1

1

1

1

1

puis il faut représenter -289. Nous représentons d’abord +289, ce qui donne :

0

1

0

0

1

0

0

0

0

1

Il faut déterminer le complément à 2 de +289, ce qui donne :

1

0

1

1

0

1

1

1

1

1

Nous constatons que le bit de signe est à 1, ce qui traduit bien le fait que le nombre est négatif.

Il reste à additionner les deux nombres :

 

0

1

1

0

0

1

1

1

1

1

 

1

0

1

1

0

1

1

1

1

1

1

0

0

0

1

1

1

1

1

1

0

ce qui donne en base 10 : 64+32+16+8+4+2=126=415-289 !!

Là aussi, on constate qu’il y a un dernier report qui passe dans le 11e bit et qui sort de la plage de représentation sur 10 bits ; mais sur 10 bits, le résultat de la soustraction est correct.

En résumé

Nous savons à présent représenter les entiers naturels et relatifs comme sommes pondérées des puissances entières de 2, comme le fait tout système numérique. Il nous faut à présent une représentation plus commode pour représenter de façon équivalente, mais plus compacte, ces nombres binaires. Il s'agit du code hexadécimal.

Exemple de certificat de réussite
Exemple de certificat de réussite