Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : les systèmes de numération informatique (201-N11)

La numération est le chapitre le plus mécanique du cours et pourtant celui où les copies perdent le plus de points : les algorithmes sont simples, mais chacun a un SENS de lecture, et l'inverser donne un résultat propre et faux.

Cette fiche rassemble ces sens de lecture et les cas limites : les restes de bas en haut, les paquets depuis la droite, l'ajout du $1$ après l'inversion, et le seul signe qui révèle un débordement.

Le fil du chapitre

Un motif de bits ne vaut rien tout seul : c'est l'INTERPRÉTATION choisie, non signée, complément à deux ou IEEE 754, qui décide de la valeur qu'il représente.

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

L'essentiel

Les poids positionnels, dans toutes les bases

• En base $b$ , le chiffre de rang $k$ pèse $b^{k}$ ; après la virgule, les poids sont $b^{-1}$ , $b^{-2}$ , et ainsi de suite.
• Un octet porte les poids $128$ , $64$ , $32$ , $16$ , $8$ , $4$ , $2$ , $1$ , du bit de poids fort à celui de poids faible.
• Un chiffre hexadécimal vaut exactement $4$ bits, un chiffre octal $3$ bits : le découpage en paquets se fait TOUJOURS à partir de la droite.
• Sur $n$ bits non signés : de $0$ à $2^{n}-1$ . En complément à deux : de $-2^{n-1}$ à $2^{n-1}-1$ .

Le motif

01100100

additionne les poids des rangs à

1

64+32+4=100

, et le rang le plus à gauche est celui qui pèse le plus.

Retenir les huit poids d'un octet dispense de tout calcul de conversion en dessous de $256$ : la lecture directe est plus rapide et plus sûre que les divisions successives.

Convertir, dans un sens et dans l'autre

• Décimal vers base $b$ , partie entière : divisions successives par $b$ , restes lus DE BAS EN HAUT.
• Partie fractionnaire : multiplications successives par $b$ , parties entières lues DE HAUT EN BAS.
• Base $b$ vers décimal : somme des chiffres multipliés par leurs poids, sans aucune division.
• Un décimal fini n'a d'écriture binaire finie que si son dénominateur réduit est une puissance de $2$ .

Les deux sens de lecture sont opposés, et c'est la seule chose à mémoriser : entiers de bas en haut, fractions de haut en bas.

Le complément à deux

• Complément à deux de $x$ : inverser tous les bits, PUIS ajouter $1$ . Le motif obtenu vaut $2^{n}-x$ .
• Le bit de poids fort joue le rôle de bit de signe : $1$ signifie négatif.
• L'intervalle n'est pas symétrique : sur $8$ bits, de $-128$ à $127$ , car le zéro occupe une place du côté positif.
• Débordement signé : les deux opérandes de MÊME signe et un résultat de signe opposé. Deux opérandes de signes contraires ne débordent jamais.

Le même motif de quatre bits se lit

12

en non signé et

-4

en complément à deux : c'est la convention choisie, non le motif, qui donne la valeur.

Le complément à deux existe pour qu'une seule addition serve aux positifs comme aux négatifs. C'est pour cela que la soustraction n'est qu'une addition du complément.

Opérations bit à bit, décalages et IEEE 754

• ET pour ÉTEINDRE des bits, OU pour les ALLUMER, OU EXCLUSIF pour les BASCULER.
• Décalage de $k$ rangs à gauche : multiplication par $2^{k}$ . À droite : division entière par $2^{k}$ .
• IEEE 754 simple précision : $1$ bit de signe, $8$ bits d'exposant biaisé de $127$ , $23$ bits de mantisse avec un $1$ implicite.
• Les entiers y sont exacts jusqu'à $2^{24}$ , soit $16\,777\,216$ ; au-delà, deux entiers voisins partagent la même représentation.

Les

32

bits d'un flottant simple précision : un pour le signe, huit pour l'exposant biaisé, vingt-trois pour la mantisse, dont le

1

de tête n'est pas stocké.

Un test d'égalité entre deux flottants est presque toujours une erreur de programmation : on compare $|a-b|$ à une tolérance, exactement comme dans les vérifications de cette fiche.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Lire les restes des divisions successives dans le mauvais sens

1,5 point, et le contrôle par les poids est immédiat

Ce qu'il ne faut pas écrire

« $13$ divisé par $2$ donne les restes $1$ , $0$ , $1$ , $1$ , donc $1011_{2}$ . »

Ce qu'il faut écrire

« Les restes se lisent DE BAS EN HAUT : $1101_{2}$ , ce qui vaut bien $8+4+1=13$ . »

Pourquoi : Le premier reste obtenu est celui du poids le plus FAIBLE, puisqu'on divise à partir des unités. Recomposer le nombre par ses poids attrape l'erreur en dix secondes.

2. Découper en paquets de quatre bits à partir de la gauche

2 points, et une valeur multipliée par une puissance de deux

Ce qu'il ne faut pas écrire

« $110101_{2}$ se découpe en $1101$ et $01$ , donc $\text{D}1_{16}$ . »

Ce qu'il faut écrire

« On découpe depuis la DROITE : $11$ et $0101$ , complété à gauche par des zéros, donc $0011\ 0101$ , soit $35_{16}$ . »

Pourquoi : Le regroupement suit les poids, qui se comptent depuis les unités. Compléter à gauche par des zéros ne change pas la valeur ; compléter à droite la multiplie.

3. Inverser les bits sans ajouter un

2 points, et toutes les additions qui suivent

Ce qu'il ne faut pas écrire

« $5$ vaut $0000\,0101$ , donc $-5$ vaut $1111\,1010$ . »

Ce qu'il faut écrire

« On inverse PUIS on ajoute $1$ : $1111\,1011$ . On vérifie que $5+251=256$ . »

Pourquoi : Le complément à un, sans le $+1$ , laisse deux représentations du zéro et casse l'addition. Le contrôle est arithmétique : le motif d'un négatif $-x$ vaut $2^{n}-x$ lu en non signé.

4. Diagnostiquer un débordement sur la retenue sortante

2 points, et la question de diagnostic vaut le double à l'examen

Ce qu'il ne faut pas écrire

« Il y a une retenue qui sort du bit de poids fort, donc il y a débordement. »

Ce qu'il faut écrire

« En complément à deux, le débordement se lit sur le SIGNE : deux opérandes positifs qui donnent un résultat négatif, ou l'inverse. »

Deux opérandes positifs,

100

50

, donnent un motif dont le bit de tête vaut

1

: le résultat se lit

-106

, et le débordement est là, sans aucune retenue sortante.

Pourquoi : La retenue sortante signale un débordement NON SIGNÉ. En complément à deux, elle est souvent parfaitement normale, par exemple quand on additionne deux nombres négatifs dont la somme tient encore.

5. Confondre les deux intervalles représentables

1 point, et une conclusion fausse sur un débordement

Ce qu'il ne faut pas écrire

« Sur $8$ bits on va de $-255$ à $255$ . »

Ce qu'il faut écrire

« Non signé : de $0$ à $255$ . Complément à deux : de $-128$ à $127$ , l'intervalle n'étant pas symétrique. »

Pourquoi : Huit bits ne codent que $256$ valeurs, quelle que soit la convention. Le zéro comptant du côté positif, il reste une valeur de plus du côté négatif.

6. Croire qu'un décimal simple s'écrit exactement en binaire

2 points sur la question d'analyse, et des bogues en programmation

Ce qu'il ne faut pas écrire

« $0{,}1+0{,}2=0{,}3$ , la machine le confirmera. »

Ce qu'il faut écrire

« $0{,}1$ n'a pas d'écriture binaire finie : la machine renvoie $0{,}30000000000000004$ , et on compare toujours à une tolérance. »

Pourquoi : Un décimal fini n'a d'écriture binaire finie que si son dénominateur réduit est une puissance de $2$ . Un dixième vaut $\dfrac{1}{10}$ , dont le dénominateur contient un $5$ .

7. Éteindre un bit avec un OU

1,5 point, et le programme fait le contraire de ce qu'il annonce

Ce qu'il ne faut pas écrire

« Pour mettre à zéro le bit $3$ , j'utilise un OU avec $0000\,1000$ . »

Ce qu'il faut écrire

« Le OU ALLUME. Pour éteindre, il faut un ET avec le masque INVERSÉ : $1111\,0111$ . »

Pourquoi : Chaque opérateur a un seul rôle : ET éteint, OU allume, OU EXCLUSIF bascule. Un OU avec un $1$ ne peut jamais produire un $0$ .

8. Confondre un chiffre hexadécimal et un octet

1 point, et un calcul de taille d'image divisé par deux

Ce qu'il ne faut pas écrire

« La couleur $\text{FF}$ tient sur un chiffre hexadécimal, donc sur $8$ bits chacun : trois chiffres pour une couleur RVB. »

Ce qu'il faut écrire

« Un chiffre hexadécimal vaut $4$ bits ; un octet en demande DEUX. Une couleur RVB s'écrit donc sur six chiffres hexadécimaux. »

Pourquoi : $16=2^{4}$ : chaque chiffre hexadécimal code exactement quatre bits. C'est toute la raison d'être de cette base, qui rend le binaire lisible sans le trahir.

9. Oublier le biais ou le 1 implicite en IEEE 754

2 points, et un ordre de grandeur absurde

Ce qu'il ne faut pas écrire

« L'exposant stocké vaut $10000011$ , soit $131$ , donc le nombre est de l'ordre de $2^{131}$ . »

Ce qu'il faut écrire

« L'exposant est BIAISÉ de $127$ : $131-127=4$ , donc le nombre est de l'ordre de $2^{4}=16$ . »

Pourquoi : Le biais permet de coder des exposants négatifs sans bit de signe supplémentaire. Et la mantisse s'écrit toujours avec un $1$ devant la virgule, qui n'est pas stocké puisqu'il est certain.

Quelle méthode choisir

Quelle opération bit à bit pour quel effet

On lit ce que le programme doit faire aux bits visés.

Si mettre certains bits à zéro sans toucher aux autres → ET avec un masque où les bits à éteindre valent $0$

Exemple : $x\ \text{ET}\ 1111\,0111$ éteint le bit $3$
Si mettre certains bits à un → OU avec un masque où les bits à allumer valent $1$

Exemple : $x\ \text{OU}\ 0000\,1000$ allume le bit $3$
Si inverser certains bits → OU EXCLUSIF avec un masque où les bits à basculer valent $1$

Exemple : appliqué deux fois, il redonne la valeur de départ
Si tester si un bit vaut $1$ → ET avec le masque, puis comparer le résultat à zéro

Exemple : $x\ \text{ET}\ 0000\,1000$ non nul signifie bit $3$ allumé
Si multiplier ou diviser par une puissance de deux → décalage à gauche ou à droite de $k$ rangs

Exemple : décaler de $3$ à gauche multiplie par $8$

à droite, c'est une division ENTIÈRE : les bits sortis sont perdus

Un masque s'écrit d'abord en binaire, puis se convertit en hexadécimal pour le code. L'écrire directement en hexadécimal est l'origine de la moitié des erreurs de masque.

Quelle interprétation donner à un motif de bits

On lit ce que l'énoncé dit du CONTEXTE, jamais le motif seul.

Si l'énoncé parle d'entier non signé, de taille ou de compteur → somme des poids, de $0$ à $2^{n}-1$

Exemple : $1001\,0110$ vaut $150$
Si l'énoncé parle d'entier signé ou de complément à deux → bit de tête à $1$ signifie négatif : la valeur est $\text{motif}-2^{n}$

Exemple : $1001\,0110$ vaut $-106$
Si l'énoncé parle de nombre à virgule flottante → découper $1+8+23$ , retirer le biais $127$ , restituer le $1$ implicite

Exemple : exposant stocké $131$ pour un exposant réel $4$
Si l'énoncé parle de texte, de caractère ou de touche → code ASCII, un octet par caractère pour les $128$ premiers

Exemple : $0100\,0001$ est la lettre A, soit $65$

Le même motif de $8$ bits peut valoir $150$ , $-106$ , un caractère ou une couleur. Nommer l'interprétation choisie avant de calculer vaut un point à chaque question de lecture.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Convertir par divisions successives

Quand l'utiliser : L'énoncé demande de passer du décimal à une autre base, avec ou sans partie fractionnaire.

1 Poser les divisions les unes sous les autres, en écrivant à chaque ligne le quotient et le reste.
2 S'arrêter quand le quotient vaut $0$ , jamais avant.
3 Lire les restes DE BAS EN HAUT pour la partie entière, et l'écrire avec l'indice de base.
4 Pour la partie fractionnaire, multiplier successivement et lire les parties entières DE HAUT EN BAS.
5 Vérifier en recomposant par les poids.

Phrase de conclusion

« $13=1101_{2}$ , car $8+4+1=13$ . »

Le piège : Arrêter les divisions quand le quotient vaut $1$ : le dernier reste, celui du poids fort, est alors perdu.

Barème : 1 point les divisions posées, 1 point le sens de lecture, 0,5 point la vérification par les poids.

Additionner en complément à deux et conclure sur le débordement

Quand l'utiliser : L'énoncé demande une addition sur $n$ bits signés, ou de dire si le résultat est correct.

1 Écrire les deux opérandes sur le MÊME nombre de bits, en complétant à gauche par le bit de signe.
2 Additionner bit à bit avec les retenues, et ignorer la retenue qui sort du rang le plus à gauche.
3 Lire le bit de signe du résultat et le comparer à ceux des opérandes.
4 Conclure : débordement seulement si les deux opérandes ont le même signe et le résultat le signe contraire.

Phrase de conclusion

« $100+50$ donne $1001\,0110$ , soit $-106$ : deux positifs donnant un négatif, il y a débordement, et le résultat est inutilisable. »

Le piège : Conclure au débordement parce qu'une retenue sort : c'est le critère du non signé, pas celui du complément à deux.

Barème : 1 point l'alignement, 1 point l'addition, 1 point le critère de signe, 1 point la conclusion.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Recomposer par les poids

Après toute conversion vers le binaire, additionner les poids des rangs à $1$ : on doit retrouver le nombre de départ.

$1101_{2}$ donne $8+4+1=13$ : la lecture des restes était dans le bon sens.
Le complément à deux se contrôle par une somme

Le motif de $-x$ sur $n$ bits, lu en NON signé, doit valoir exactement $2^{n}-x$ .

$-5$ sur $8$ bits donne $251$ , et $5+251=256$ .
Le nombre de chiffres attendu

Un octet fait deux chiffres hexadécimaux, un nombre inférieur à $256$ tient sur $8$ bits. Un résultat plus long trahit une erreur.

Une couleur RVB écrite sur trois chiffres hexadécimaux au lieu de six.
Le signe du résultat

Avant de conclure une addition signée, comparer le bit de tête du résultat à ceux des opérandes.

Deux positifs qui donnent un bit de tête à $1$ : le résultat est inutilisable, quel que soit son motif.

L'exercice type décortiqué

Une addition qui déborde, sur huit bits signés

Un capteur additionne deux mesures, $100$ et $50$ , dans une variable codée sur $8$ bits en complément à deux.

Écrire l'addition en binaire, donner la valeur lue par le programme, et dire s'il y a débordement.

Étape 1

$100=0110\,0100$ et $50=0011\,0010$ , tous deux sur $8$ bits.

Pourquoi

On écrit les deux opérandes sur le même nombre de bits avant toute chose : une addition sur des largeurs différentes n'a aucun sens et fait perdre le point d'alignement.

Étape 2

Somme bit à bit : $0110\,0100+0011\,0010=1001\,0110$ .

Pourquoi

L'addition binaire se pose exactement comme en décimal, avec des retenues. Ici aucune retenue ne sort du rang de tête, ce qui n'empêche rien.

Étape 3

Lecture non signée : $128+16+4+2=150$ , ce qui est la somme attendue.

Pourquoi

Le motif est juste : la machine n'a pas fait d'erreur de calcul. Le problème vient de l'interprétation, pas de l'addition.

Étape 4

Lecture signée : le bit de tête vaut $1$ , donc la valeur est $150-256=-106$ .

Pourquoi

En complément à deux, un motif de tête à $1$ se lit en retranchant $2^{8}$ . C'est la valeur que le programme utilisera réellement.

Étape 5

Critère : deux opérandes positifs, résultat négatif, donc DÉBORDEMENT.

Pourquoi

Le critère porte sur les signes, jamais sur la retenue sortante. Ici l'intervalle signé s'arrête à $127$ , et $150$ le dépasse.

Étape 6

Contrôle : $-106+256=150$ , et $150>127$ .

Pourquoi

Les deux relations confirment l'une le motif, l'autre le diagnostic. Sur $16$ bits, la même addition ne déborderait pas, puisque la limite serait $32\,767$ .

Conclusion rédigée

« Le motif obtenu est $1001\,0110$ ; lu en complément à deux sur $8$ bits, il vaut $-106$ . Deux opérandes positifs donnant un résultat négatif, il y a débordement : la variable doit être codée sur $16$ bits. »

L'erreur classique sur cet exercice : Répondre $150$ parce que le motif vaut bien $150$ : la question porte sur la valeur LUE par un programme qui interprète en complément à deux.

À savoir par cœur

• Divisions successives : restes DE BAS EN HAUT. Partie fractionnaire : parties entières DE HAUT EN BAS.
• Un chiffre hexadécimal vaut $4$ bits, un octal $3$ bits ; on découpe toujours depuis la DROITE.
• Complément à deux : inverser PUIS ajouter $1$ ; le motif de $-x$ vaut $2^{n}-x$ en non signé.
• Sur $n$ bits : non signé de $0$ à $2^{n}-1$ , signé de $-2^{n-1}$ à $2^{n-1}-1$ .
• Débordement signé : deux opérandes de MÊME signe et un résultat de signe contraire. La retenue sortante ne prouve rien.
• ET éteint, OU allume, OU EXCLUSIF bascule. Décalage à gauche multiplie, à droite divise en entier.
• IEEE 754 : $1+8+23$ bits, exposant biaisé de $127$ , $1$ implicite, entiers exacts jusqu'à $2^{24}$ .

Questions fréquentes

Dans quel sens lit-on les restes des divisions successives ?

De bas en haut, c'est-à-dire du dernier reste obtenu vers le premier. Le premier reste correspond au chiffre de poids le plus faible, puisque la première division porte sur les unités. On s'arrête seulement quand le quotient devient nul, sinon le chiffre de poids fort est perdu.

Comment écrire un nombre négatif en complément à deux ?

On écrit d'abord sa valeur absolue en binaire sur le nombre de bits voulu, puis on inverse tous les bits, et enfin on ajoute un. Le motif obtenu, lu comme un entier non signé, vaut deux puissance n moins le nombre de départ, ce qui donne une vérification immédiate.

Comment savoir s'il y a débordement ?

En comparant les signes. Il y a débordement signé lorsque les deux opérandes ont le même signe et que le résultat porte le signe contraire. Une retenue sortant du rang de tête ne prouve rien en complément à deux : elle signale un débordement seulement dans l'interprétation non signée.

Pourquoi 0,1 plus 0,2 ne fait pas exactement 0,3 en machine ?

Parce qu'un décimal n'a une écriture binaire finie que si son dénominateur réduit est une puissance de deux. Un dixième a un cinq au dénominateur, donc son écriture binaire est infinie et la machine l'arrondit. L'erreur d'arrondi survit à l'addition, d'où la règle de toujours comparer deux flottants à une tolérance près.

Combien de bits vaut un chiffre hexadécimal ?

Quatre exactement, puisque seize est deux puissance quatre. Un octet demande donc deux chiffres hexadécimaux, et une couleur en rouge vert bleu, qui occupe trois octets, s'écrit sur six chiffres. Le découpage en paquets de quatre bits se fait toujours à partir de la droite, en complétant à gauche par des zéros.

Passer à la pratique

Exercices corrigés : Systèmes de numération informatique

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

12 exercices corrigés
120 points
180 minutes

Faire les exercices

Fiche précédente Logique booléenne et mathématique Fiche suivante L'arithmétique modulaire

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

L'arithmétique modulaire

Voir aussi

Toutes les fiches Tous les exercices Tutorat au cégep Tuteur maths pour l'informatique (201-N11)Logique booléenne (201-N11)Graphes et matrices (201-N11)Cours de mathématiques

Vous suivez le cours 201-N11 en informatique au cégep ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maître en informatique appliquée de Concordia, je fais travailler la numération sur ce qui se casse en vrai : les débordements silencieux et les comparaisons de flottants.

Me contacter WhatsApp

Site par Studio Squalli