Exercices corrigés : systèmes de numération informatique (201-N11)

a) On écrit les poids au-dessus des bits : $128, 64, 32, 16, 8, 4, 2, 1$. Les bits à 1 sont ceux de poids $128$, $32$, $16$, $4$ et $2$. Somme : $128+32+16+4+2 = 182$. Contrôle rapide : le bit de poids fort vaut 1, donc le nombre est au moins 128 ; le bit de poids faible vaut 0, donc le nombre est pair. 182 satisfait les deux.

b) En base 8, les poids sont $64, 8, 1$. Donc $357_8 = 3(64) + 5(8) + 7(1) = 192 + 40 + 7 = 239$. Contrôle : le chiffre le plus grand utilisé est 7, ce qui est licite en base 8 ; un 8 ou un 9 dans une écriture octale serait une faute d'énoncé.

c) En base 16, les poids sont $256, 16, 1$, et $\text{F}$ vaut 15. Donc $2\text{F}5_{16} = 2(256) + 15(16) + 5(1) = 512 + 240 + 5 = 757$. Les lettres $\text{A}$ à $\text{F}$ valent 10 à 15 : c'est la seule chose à mémoriser en hexadécimal.

d) La partie entière $1101_2$ vaut $8+4+1 = 13$. Après la virgule, les poids deviennent des puissances négatives : $2^{-1} = 0{,}5$, puis $2^{-2} = 0{,}25$, puis $2^{-3} = 0{,}125$. Les bits sont $1, 0, 1$, donc la partie fractionnaire vaut $0{,}5 + 0{,}125 = 0{,}625$. Total : $13{,}625$. La règle est la même de part et d'autre de la virgule, seul l'exposant change de signe.

e) Sur $n$ bits il y a $2^{n}$ combinaisons, numérotées de 0 à $2^{n}-1$ : le plus grand entier non signé est donc $2^{n}-1$. Sur 8 bits, $255$ ; sur 16 bits, $65\,535$. Piège classique : répondre $2^{n}$ en oubliant que le zéro consomme une combinaison.

a) $156 = 2(78) + 0$ ; $78 = 2(39)+0$ ; $39 = 2(19)+1$ ; $19 = 2(9)+1$ ; $9 = 2(4)+1$ ; $4 = 2(2)+0$ ; $2 = 2(1)+0$ ; $1 = 2(0)+1$. Les restes lus de bas en haut donnent $10011100_2$. Vérification par les poids : $128 + 16 + 8 + 4 = 156$. Le contrôle par les poids est obligatoire, parce qu'il attrape l'erreur de sens de lecture, qui donnerait $00111001$.

b) Par divisions par 8 : $156 = 8(19)+4$ ; $19 = 8(2)+3$ ; $2 = 8(0)+2$, d'où $234_8$. Vérification : $2(64)+3(8)+4 = 128+24+4 = 156$. Par divisions par 16 : $156 = 16(9)+12$ ; $9 = 16(0)+9$, et $12 = \text{C}$, d'où $9\text{C}_{16}$. Vérification : $9(16)+12 = 156$. Raccourci : $10011100_2$ se découpe en $1001\ 1100 = 9\text{C}$, en paquets de 4 bits à partir de la droite.

c) $0{,}6875 \times 2 = 1{,}375$, on garde 1 ; $0{,}375 \times 2 = 0{,}75$, on garde 0 ; $0{,}75 \times 2 = 1{,}5$, on garde 1 ; $0{,}5 \times 2 = 1{,}0$, on garde 1, et il ne reste rien. Lecture de haut en bas : $0{,}1011_2$. Vérification : $0{,}5 + 0{,}125 + 0{,}0625 = 0{,}6875$. La conversion s'arrête ici parce que $0{,}6875 = \dfrac{11}{16}$ a un dénominateur qui est une puissance de 2.

d) $0{,}1 \times 2 = 0{,}2$ ; $0{,}2 \times 2 = 0{,}4$ ; $0{,}4 \times 2 = 0{,}8$ ; $0{,}8 \times 2 = 1{,}6$ ; $0{,}6 \times 2 = 1{,}2$ ; $0{,}2 \times 2 = 0{,}4$ et l'on retombe sur un état déjà vu. Le développement est périodique : $0{,}1 = 0{,}0\overline{0011}_2$, sans fin. La raison est arithmétique : $0{,}1 = \dfrac{1}{10}$ et 10 contient le facteur 5, qui n'est pas une puissance de 2. Un nombre décimal fini n'a d'écriture binaire finie que si son dénominateur réduit est une puissance de 2.

e) $1000 = 16(62)+8$ ; $62 = 16(3)+14$, et $14 = \text{E}$ ; $3 = 16(0)+3$. D'où $3\text{E}8_{16}$. Vérification : $3(256) + 14(16) + 8 = 768 + 224 + 8 = 1000$.

f) L'ordinateur ne stocke pas $0{,}1$ mais l'arrondi de son développement binaire infini sur le nombre de bits disponibles. Trois arrondis distincts se produisent, pour $0{,}1$, pour $0{,}2$ et pour $0{,}3$, et rien ne garantit que la somme des deux premiers tombe exactement sur le troisième : en pratique elle ne tombe pas. La conclusion tient en une règle : on ne compare jamais deux nombres à virgule flottante avec une égalité stricte, on teste $|x-y| < \varepsilon$. Pour de l'argent, on travaille en cents avec des entiers.

a) On aligne à droite : $10110$ vaut 22 et $1101$ vaut 13. Colonne par colonne depuis la droite : $0+1 = 1$ ; $1+0 = 1$ ; $1+1 = 10$, on pose 0 et on retient 1 ; $0+1+1 = 10$, on pose 0 et on retient 1 ; $1+0+1 = 10$, on pose 0 et on retient 1 ; il reste la retenue, on pose 1. Résultat : $100011_2$. Vérification : $32+2+1 = 35$ et $22+13 = 35$.

b) $110101$ vaut 53 et $10110$ vaut 22. On emprunte comme en décimal, un emprunt valant 2 dans la colonne de droite : $1-0 = 1$ ; $0-1$ impose un emprunt, $10-1 = 1$ ; $0-1$ après emprunt devient $1-1-1$, nouvel emprunt, $10-1-1 = 0$ ; et ainsi de suite. Résultat : $11111_2$. Vérification : $16+8+4+2+1 = 31$ et $53-22 = 31$. Un résultat en $11111$ n'est pas suspect : c'est $2^{5}-1$.

c) $1011$ vaut 11 et $101$ vaut 5. La multiplication binaire ne demande aucune table : chaque bit du multiplicateur donne soit une copie décalée du multiplicande, soit une ligne de zéros. Ici : $1011$ (bit de poids 1), $000000$ (bit de poids 2, nul), $101100$ (bit de poids 4, donc décalé de deux rangs). Somme : $1011 + 101100 = 110111_2$. Vérification : $32+16+4+2+1 = 55$ et $11 \times 5 = 55$.

d) $1101$ vaut 13 et $10$ vaut 2. Diviser par $10_2$, c'est décaler d'un rang vers la droite : le quotient est $110_2 = 6$ et le bit expulsé, ici 1, est le reste. Vérification : $2(6)+1 = 13$. Diviser par une puissance de 2 est un décalage, ce qui explique pourquoi les compilateurs remplacent $n/2$ par un décalage quand $n$ est un entier non signé.

e) Ajouter un 0 à droite décale tous les bits d'un rang vers la gauche : chaque bit voit son poids doubler, donc le nombre est multiplié par 2, et non par 10. Trois zéros multiplient par $2^{3} = 8$. C'est le même mécanisme qu'en décimal, où ajouter un zéro multiplie par 10, c'est-à-dire par la base. Retenir : le facteur est toujours la base, jamais dix.

a) Étape 1 : écrire $37$ sur 8 bits. $37 = 32+4+1$, donc $00100101$. Étape 2 : inverser tous les bits, ce qui donne $11011010$, puis ajouter 1 : $11011011$. Contrôle numérique : $11011011$ vaut $128+64+16+8+2+1 = 219$, et $219 = 256 - 37$, ce qui est exactement la définition. En hexadécimal, $\text{DB}$.

b) Le bit de poids fort vaut 1, donc le nombre est négatif. Deux méthodes. Méthode directe : lire le motif comme non signé, $10110100 = 128+32+16+4 = 180$, puis retrancher $256$ : $180 - 256 = -76$. Méthode par complément : inverser, $01001011$, ajouter 1, $01001100 = 64+8+4 = 76$, donc le motif valait $-76$. Les deux donnent le même résultat, et c'est le contrôle à faire.

c) De $-128$ à $+127$. Il y a $256$ motifs ; la moitié, ceux dont le bit de poids fort vaut 0, code $0$ à $127$ ; l'autre moitié code $-128$ à $-1$. L'asymétrie vient de ce que le zéro occupe une place du côté positif : il reste $127$ motifs pour les positifs et $128$ pour les négatifs. C'est précisément l'avantage du complément à deux sur les représentations avec bit de signe séparé, qui ont deux zéros et perdent un motif.

d) $45 = 00101101$. On lui ajoute la représentation de $-37$, soit $11011011$. L'addition binaire donne $1\,00001000$ sur neuf colonnes : la retenue sortante du rang 8 est simplement jetée, et il reste $00001000 = 8$. Vérification : $45-37 = 8$. C'est tout l'intérêt du complément à deux : le circuit d'addition sert aussi de circuit de soustraction, à un inverseur près.

e) Sur 4 bits, la plage est $-8$ à $+7$. L'opposé de $-8$ devrait être $+8$, qui n'existe pas dans la plage. En appliquant la recette : $-8$ s'écrit $1000$ ; on inverse, $0111$ ; on ajoute 1, $1000$ : on retombe sur $-8$. Le cas révèle que la négation en complément à deux n'est pas totale, et c'est un vrai piège de programmation, où $\lvert x \rvert$ peut renvoyer un nombre négatif pour la borne inférieure de la plage.

a) La virgule sépare les rangs positifs des rangs négatifs. À gauche, en partant de la virgule vers la gauche, les poids sont $8^{0}, 8^{1}, 8^{2}, 8^{3}$ ; à droite, $8^{-1}$ puis $8^{-2}$. D'où $2471{,}35_8 = 2 \cdot 8^{3} + 4 \cdot 8^{2} + 7 \cdot 8^{1} + 1 \cdot 8^{0} + 3 \cdot 8^{-1} + 5 \cdot 8^{-2}$. Valeur : $2(512) + 4(64) + 7(8) + 1 + \dfrac{3}{8} + \dfrac{5}{64} = 1024 + 256 + 56 + 1 + 0{,}375 + 0{,}078125 = 1337{,}453125$. La notation développée n'est pas un exercice de style : c'est la définition même de la base, et toute conversion vers le décimal n'est que ce calcul écrit plus vite.

b) $735_8 = 7(64) + 3(8) + 5 = 448 + 24 + 5 = 477$. $1204_8 = 1(512) + 2(64) + 0(8) + 4 = 512 + 128 + 4 = 644$ : le zéro se pèse aussi, il tient une position même s'il n'apporte rien. $61{,}4_8 = 6(8) + 1 + \dfrac{4}{8} = 49{,}5$. $0{,}52_8 = \dfrac{5}{8} + \dfrac{2}{64} = 0{,}625 + 0{,}03125 = 0{,}65625$. Piège classique : lire $0{,}52_8$ comme « cinquante-deux centièmes ». En base 8, le deuxième chiffre après la virgule pèse un soixante-quatrième, pas un centième.

c) Partie entière par divisions successives par 8, restes lus de bas en haut. $200 = 8(25) + 0$ ; $25 = 8(3) + 1$ ; $3 = 8(0) + 3$, d'où $200 = 310_8$ ; contrôle $3(64) + 1(8) = 200$. $1000 = 8(125) + 0$ ; $125 = 8(15) + 5$ ; $15 = 8(1) + 7$ ; $1 = 8(0) + 1$, d'où $1000 = 1750_8$ ; contrôle $512 + 7(64) + 5(8) = 512 + 448 + 40 = 1000$. Pour $93{,}75$, on sépare : $93 = 8(11) + 5$ ; $11 = 8(1) + 3$ ; $1 = 8(0) + 1$, donc $93 = 135_8$ ; puis $0{,}75 \times 8 = 6{,}0$, on garde 6 et il ne reste rien, donc $93{,}75 = 135{,}6_8$. Contrôle : $64 + 24 + 5 + 0{,}75 = 93{,}75$. Pour $0{,}1$ : $0{,}1 \times 8 = 0{,}8$, chiffre 0 ; $0{,}8 \times 8 = 6{,}4$, chiffre 6 ; $0{,}4 \times 8 = 3{,}2$, chiffre 3 ; $0{,}2 \times 8 = 1{,}6$, chiffre 1 ; $0{,}6 \times 8 = 4{,}8$, chiffre 4 ; $0{,}8 \times 8 = 6{,}4$ et l'on retombe sur un état déjà vu. Le développement est périodique : $0{,}1 = 0{,}0\overline{6314}_8$. Rien d'étonnant : $0{,}1 = \dfrac{1}{10}$ et 10 contient le facteur 5, qui ne divise aucune puissance de 8. Un décimal fini a une écriture finie en base 8 exactement quand son dénominateur réduit est une puissance de 2, la même condition qu'en binaire, parce que $8 = 2^{3}$.

d) On additionne colonne par colonne, et dès qu'une colonne atteint 8 on écrit le reste et on retient 1. Première addition : unités $7 + 6 = 13 = 8 + 5$, on pose 5 et on retient 1 ; huitaines $5 + 4 + 1 = 10 = 8 + 2$, on pose 2 et on retient 1 ; $3 + 2 + 1 = 6$. Résultat $625_8$. Contrôle décimal : $357_8 = 239$, $246_8 = 166$, somme 405, et $625_8 = 6(64) + 2(8) + 5 = 405$. Deuxième addition, à trois termes, alignés à droite : unités $5 + 3 + 7 = 15 = 8 + 7$, on pose 7 et on retient 1 ; $4 + 3 + 2 + 1 = 10$, on pose 2, retenue 1 ; $7 + 6 + 0 + 1 = 14$, on pose 6, retenue 1 ; $1 + 0 + 0 + 1 = 2$. Résultat $2627_8$. Contrôle : $997 + 411 + 23 = 1431$ et $2627_8 = 2(512) + 6(64) + 2(8) + 7 = 1431$. Troisième addition, à virgule, en alignant les virgules : $6 + 7 = 13$, on pose 5, retenue 1 ; $5 + 3 + 1 = 9$, on pose 1, retenue 1 ; $2 + 7 + 1 = 10$, on pose 2, retenue 1 ; $1 + 0 + 1 = 2$. Résultat $22{,}15_8$. Contrôle : $10{,}71875 + 7{,}484375 = 18{,}203125$ et $22{,}15_8 = 18 + \dfrac{1}{8} + \dfrac{5}{64} = 18{,}203125$. L'erreur la plus fréquente est de retenir à 10 par réflexe : $7 + 6$ donne alors « 13 » posé tel quel, et le résultat est faux de 8 sur cette colonne.

e) Le complément à 7 d'un nombre à 4 chiffres octaux s'obtient en remplaçant chaque chiffre $d$ par $7 - d$, sans aucune retenue ; c'est l'analogue de l'inversion des bits. Le complément à 8 est le complément à 7 plus 1, et il vaut $8^{4} - x = 4096 - x$ : c'est l'analogue du complément à deux. Pour $0325_8$ : complément à 7, chiffre par chiffre, $7-0, 7-3, 7-2, 7-5$, soit $7452_8$ ; plus 1, $7453_8$. Contrôle : $0325_8 = 3(64) + 2(8) + 5 = 213$, $4096 - 213 = 3883$, et $7453_8 = 7(512) + 4(64) + 5(8) + 3 = 3584 + 256 + 40 + 3 = 3883$. Soustraction par addition : $2461_8 + 7453_8$. Unités $1 + 3 = 4$ ; $6 + 5 = 11 = 8 + 3$, on pose 3, retenue 1 ; $4 + 4 + 1 = 9$, on pose 1, retenue 1 ; $2 + 7 + 1 = 10$, on pose 2, retenue 1. On obtient $12134_8$ sur cinq chiffres ; la retenue qui sort à gauche est jetée, puisque l'on travaille sur 4 chiffres, et il reste $2134_8$. Contrôle : $2461_8 = 1329$, $1329 - 213 = 1116$, et $2134_8 = 1024 + 64 + 24 + 4 = 1116$. Pourquoi ça marche : ajouter $4096 - x$ puis jeter $4096$ revient exactement à retrancher $x$. Plage signée sur 4 chiffres octaux, c'est-à-dire 12 bits : de $-2^{11} = -2048$ à $2^{11} - 1 = 2047$, soit de $4000_8$ (lu $-2048$) à $3777_8$. Un nombre est négatif quand son chiffre de tête vaut 4 ou plus : la moitié haute des motifs représente les négatifs, exactement comme le bit de poids fort en binaire, puisque le premier chiffre octal contient ce bit. Ainsi $7453_8$, lu comme un entier signé, vaut $3883 - 4096 = -213$.

f) Première soustraction, $7042_8 - 3567_8$. Unités : $2 < 7$, on emprunte une huitaine, $2 + 8 - 7 = 3$, et le chiffre des huitaines passe de 4 à 3. Huitaines : $3 < 6$, on emprunte, $3 + 8 - 6 = 5$, et le chiffre des 64 doit baisser de 1 ; il vaut 0, donc on emprunte d'abord aux 512, qui passent de 7 à 6, et les 64 valent $8 - 1 = 7$. Colonne des 64 : $7 - 5 = 2$. Colonne des 512 : $6 - 3 = 3$. Résultat $3253_8$. Contrôle : $7042_8 = 3618$, $3567_8 = 1911$, différence 1707, et $3253_8 = 3(512) + 2(64) + 5(8) + 3 = 1707$. Deuxième soustraction, $10{,}20_8 - 3{,}75_8$, en complétant $10{,}2$ par un zéro pour aligner : soixante-quatrièmes $0 < 5$, on emprunte, $0 + 8 - 5 = 3$, et les huitièmes passent de 2 à 1 ; huitièmes $1 < 7$, on emprunte, $1 + 8 - 7 = 2$, et les unités, qui valent 0, empruntent aux huitaines, $1 \to 0$, pour valoir $8 - 1 = 7$ ; unités $7 - 3 = 4$ ; huitaines $0 - 0 = 0$. Résultat $4{,}23_8$. Contrôle : $8{,}25 - 3{,}953125 = 4{,}296875$ et $4{,}23_8 = 4 + \dfrac{2}{8} + \dfrac{3}{64} = 4{,}296875$. Le piège de l'emprunt en cascade, à travers un zéro, est le même qu'en décimal ; la seule nouveauté est qu'un emprunt vaut 8.

g) Multiplication posée, avec la table de 8 en tête : chaque produit partiel se réduit modulo 8 et la retenue peut dépasser 1. $53_8 \times 7_8$ : $3 \times 7 = 21 = 2(8) + 5$, on pose 5 et on retient 2 ; $5 \times 7 + 2 = 37 = 4(8) + 5$, on pose 5 puis 4. Résultat $455_8$ ; contrôle $43 \times 7 = 301 = 4(64) + 5(8) + 5$. $124_8 \times 35_8$ : par 5, $4 \times 5 = 20 = 2(8) + 4$, on pose 4, retenue 2 ; $2 \times 5 + 2 = 12 = 8 + 4$, on pose 4, retenue 1 ; $1 \times 5 + 1 = 6$, ligne $644_8$. Par 3, décalée d'un rang : $4 \times 3 = 12$, on pose 4, retenue 1 ; $2 \times 3 + 1 = 7$ ; $1 \times 3 = 3$, ligne $3740_8$. Somme $644_8 + 3740_8$ : $4 + 0 = 4$ ; $4 + 4 = 8$, on pose 0, retenue 1 ; $6 + 7 + 1 = 14$, on pose 6, retenue 1 ; $3 + 1 = 4$. Résultat $4604_8$ ; contrôle $84 \times 29 = 2436 = 4(512) + 6(64) + 4$. $6{,}4_8 \times 2{,}2_8$ : on multiplie sans les virgules, $64_8 \times 22_8$, et l'on replace ensuite autant de chiffres après la virgule qu'il y en avait au total dans les facteurs, ici $1 + 1 = 2$. $64_8 \times 2 = 150_8$ (car $4 \times 2 = 8$, on pose 0, retenue 1 ; $6 \times 2 + 1 = 13$, on pose 5, retenue 1) ; la ligne par 2 décalée donne $1500_8$ ; somme $1650_8$ ; avec deux chiffres fractionnaires, $16{,}50_8 = 16{,}5_8$. Contrôle : $6{,}5 \times 2{,}25 = 14{,}625$ et $16{,}5_8 = 14 + \dfrac{5}{8} = 14{,}625$. La règle de placement de la virgule est la même qu'en décimal, parce qu'elle ne dépend que du nombre de rangs, pas de la base.

h) $345 = 8(43) + 1$, $43 = 8(5) + 3$, $5 = 8(0) + 5$, donc $345 = 531_8$ ; $219 = 8(27) + 3$, $27 = 8(3) + 3$, donc $219 = 333_8$. Addition : $1 + 3 = 4$ ; $3 + 3 = 6$ ; $5 + 3 = 8$, on pose 0, retenue 1, et l'on écrit 1 en tête. Résultat $1064_8$, et retour : $512 + 6(8) + 4 = 564 = 345 + 219$. Le contrôle ferme la boucle. Puis $6{,}5 = 6{,}4_8$ puisque $0{,}5 = \dfrac{4}{8}$, et $3{,}25 = 3{,}2_8$ puisque $0{,}25 = \dfrac{2}{8}$. On calcule $64_8 \times 32_8$ : par 2, $150_8$ ; par 3 décalée, $6 \times 3 = 18 = 2(8) + 2$ précédé de $4 \times 3 = 12 = 8 + 4$, ce qui donne $234_8$ puis $2340_8$ ; somme $150_8 + 2340_8 = 2510_8$ ; deux chiffres fractionnaires : $25{,}10_8 = 25{,}1_8$. Retour : $2(8) + 5 + \dfrac{1}{8} = 21{,}125$, et $6{,}5 \times 3{,}25 = 21{,}125$. Les deux nombres ont des écritures octales finies parce que leurs parties fractionnaires, $\dfrac{1}{2}$ et $\dfrac{1}{4}$, ont un dénominateur puissance de 2.

i) Chaque chiffre octal vaut exactement 3 bits : $7 = 111_2$, $5 = 101_2$, donc $755_8 = 111\ 101\ 101_2$. Les trois chiffres codent les droits de trois acteurs, le propriétaire, le groupe et les autres, et les trois bits de chaque chiffre sont, dans l'ordre, lecture, écriture, exécution. $7 = 111$ : le propriétaire peut tout ; $5 = 101$ : le groupe et les autres peuvent lire et exécuter, pas écrire. La base 8 est naturelle ici parce que les droits vont par paquets de 3 bits et qu'un chiffre octal est précisément un paquet de 3 bits : le découpage ne demande aucun calcul, il se lit. Un 644, pour comparaison, donne $110\ 100\ 100$ : le propriétaire lit et écrit, les autres lisent seulement. Voilà pourquoi la conversion binaire vers octal se fait en paquets de 3 et pourquoi l'octal survit là où l'on manipule des triplets de bits.