Licence CC BY-NC

Un détour nécessaire : le binaire

Publié :

Un ordinateur, vous commencez à le sentir, c’est entre autre un très long et très complexe circuit logique (voir même plusieurs). Néanmoins, le but de ce circuit est de réaliser des opérations et entre autre des opérations mathématiques « classiques » sur des nombres quelconques. La question qu’on va se poser ici, c’est comment on peut représenter ces nombres au niveau de la machine ?

C'est la base !

Sans refaire tout un cours de numération, nous travaillons, dans la vie de tout les jours, avec la base 10. Ça signifie que « 10 » est le premier nombre (c’est-à-dire une suite de chiffre) qui nécessite deux chiffres pour être représenté. Par exemple, si on travaillait en base 8, ça signifie que pour représenter 8, il faudrait écrire… « 10 ». Pour ne pas confondre, on va plutôt écrire 10810_8, c’est-à-dire « 10 » en base 8. Et en binaire, c’est-à-dire en base 2, 2102_{10} est représenté par 10210_{2} (c’est-à-dire « 10 » en base 2).

Conversion en base 10

Instinctivement, on sait que si on a par exemple 1235101235_{10}, c’est équivalent à {1×1000+2×100+3×10+5}10\{1\times 1000+2\times 100+3\times 10 + 5\}_{10} (j’utilise ici les accolades pour indiquer que tous les nombres sont en base 10). Mais s’il me prend l’envie de le réécrire d’une manière légèrement différente, on se rend compte de l’usage de la base :

123510={1×103+2×102+3×101+4×100}10,1235_{10} = \{1\times 10^3 + 2\times 10^2 + 3\times 10^1 + 4\times 10^0\}_{10},

ce qui signifie qu’à chaque fois, le chiffre est multiplié par la base exposant la position dans le nombre, lu de droite à gauche (et en commençant à 0). Un nombre aa composés de nn chiffres aia_i dans une base donnée peut donc s’écrire comme an1an2a0a_{n-1}a_{n-2}\ldots a_0. Un nombre aBa_{\mathfrak{B}} dans une base B\mathfrak{B} correspond, en base 10, à :

a10={i=0n1aiBi}10a_{10}=\left\{\sum_{i=0}^{n-1} a_i\,\mathfrak{B}^i\right\}_{10}

aia_i représente le chiffre à la position ii. Cette formule est en fait très pratique pour passer d’une base B\mathfrak{B} à la base 10. Ainsi,

1257={1×72+2×71+5×70}10=6810,1001012={1×25+0×24+0×23+1×22+0×21+1×20}10={25+22+20}10=3710.\begin{aligned} &125_7 = \{1\times 7^2+2\times 7^1+5\times 7^0\}_{10} = 68_{10},\\ &100101_2 = \{1\times 2^5+0\times 2^4+0\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0\}_{10} = \{2^5+2^2+2^0\}_{10} = 37_{10}. \end{aligned}

Comme on le voit, c’est assez systématique et à condition de jongler avec les puissances, c’est assez rapide à mettre en place.

Pour vous entraîner, convertissez 108591085_9, 11213411213_4 et 1F75161F75_{16} en base 10, sachant que pour la base 16 (hexadécimale), on considère que 1010=A1610_{10} = A_{16}, 1110=B1611_{10} = B_{16}, et ainsi de suite.

10859={1×93+8×9+5}10=80610112134={1×44+1×43+2×42+1×4+3}10=359101F7516={1×163+15×162+7×16+5}=805310\begin{aligned} &1085_9 = \{1\times 9^3+8\times 9+5\}_{10} = 806_{10} \\ &11213_4 = \{1\times 4^4+1\times 4^3+2\times 4^2+1\times 4 + 3\}_{10} = 359_{10}\\ &1F75_{16} = \{1\times 16^3+15\times 16^2+7\times16+5\} = 8053_{10} \end{aligned}

Dans le cas du binaire, on a une suite de bits, valant 0 ou 1. Le bit le plus à droit est nommé bit de poids faible tandis que celui le plus à gauche est nommé bit de poids fort.1

Conversion d’une base 10 vers une base quelconque

Si on veut convertir un nombre donné en base 10 vers une base quelconque, disons B\mathfrak{B}, il existe une méthode (puis une seconde dans le cas du binaire, même si elle repose sur la même astuce).

Méthode générale

La méthode consiste à diviser (par division euclidienne, donc entière) le nombre en question par B\mathfrak{B}, puis à écrire le reste de cette division à côté, pour ensuite diviser le quotient par B\mathfrak{B} et ainsi de suite jusqu’à ce que le quotient obtenu soit égal à 0.

Par exemple, si on veut convertir 137 en base 5, on divise 137 par 5. On obtient 27, avec 2 comme reste. On divise 27 par 5, on obtient 5, avec 2 pour reste et ainsi de suite.

Quotient Reste
137 2
27 2
5 0
1 1
0

Le nombre converti s’obtient en lisant ensuite la colonne des restes à l’envers. On a donc 102251022_5, et vous pouvez vérifier, c’est correct. Vous pouvez donc vous entrainer à convertir 1256101256_{10} en base 7, puis 64510645_{10} en base 2 (en binaire, quoi).

Quotient Reste
1256 3
179 4
25 4
3 3
0

Donc 125610=344371256_{10} = 3443_7

Quotient Reste
645 1
322 0
161 1
80 0
40 0
20 0
10 0
5 1
2 0
1 1
0

Donc, 64510=10100001012645_{10}=1010000101_2

Encore une fois, c’est assez systématique. Par contre, c’est relativement long, surtout pour les petites bases.

Le cas particulier du binaire

La seconde méthode consiste à écrire toutes les puissances de 2 dans un tableau de droite à gauche, tant que 2x2^x est plus petit que le nombre que vous devez convertir. Ensuite, on soustrait la plus grande puissance écrite au résultat, et on écrit 1 en dessous de cette puissance. On sélectionne alors la plus grande puissance inférieure à ce résultat, qu’on soustrait, en indiquant 1 en dessous de la puissance. Et ainsi de suite, jusqu’à ce qu’on obtienne 0. Les puissances qui ne sont pas utilisées sont marqués à 0 et le nombre en binaire est ainsi obtenu.

Par exemple, convertissons 72410724_{10} en binaire. La plus grande puissance de 2 inférieure à 724, c’est 512 (292^9). On a donc :

512 256 128 64 32 16 8 4 2 1
1 . . . . . . . . .

si on soustrait 512 à 724, on obtient 212. On voit que la plus grande puissance de 2 inférieure à 212, c’est 128. On marque 1 dans la colonne 128 (et zéro dans la colonne 256), et on soustrait 128 à 212 (on obtient 84).

512 256 128 64 32 16 8 4 2 1
1 0 1 . . . . . . .

Et ainsi de suite. Finalement, on obtient le tableau suivant :

512 256 128 64 32 16 8 4 2 1
1 0 1 1 0 1 0 1 0 0

ce qui signifie que 72410=10110101002724_{10}=1011010100_2, ce qui est la bonne réponse. C’est un peu plus rapide à faire, selon moi, surtout si le nombre une fois converti en binaire ne contient pas que des 121_2 (auquel cas c’est juste aussi long que la méthode ci-dessus). Néanmoins, les deux méthodes donnent le même résultat, donc c’est comme vous souhaitez.

Binaire et représentation des nombres

En mathématiques, on ne s’inquiète pas trop de la place que prend un nombre. On sait à peu près qu’il en existe une infinité et qu’on obtient toujours le suivant en faisant « +1 » et le précédent en faisant « -1 ». Bon, parfois, il faut écrire très petit sur sa feuille, parfois il faut utiliser de moyens alternatifs (comme la notation scientifique, qu’on retrouve aussi pour représenter les nombres à virgule en binaire), mais dans l’idée c’est ça.

Néanmoins, un ordinateur fonctionne (généralement) en représentant les nombres en utilisant un nombre de bits constant. En effet, c’est plus simple de ne pas avoir à se demander combien de bit fait le nombre avant de travailler avec et beaucoup plus efficace d’effectuer une opération sur deux nombres si on sait quelle taille ils font.

En fonction du processeur dont est fait votre ordinateur, la taille (le nombre de bits) allouée à la représentation des nombres entiers varie, mais est généralement de 64 bits (ou 32 bits pour certains processeurs plus vieux) et les circuits sont construits de manière à refléter cette taille, pour une raison assez pratique : ces nombres entiers servent également à représenter des adresses mémoires au niveau du processeur et une bonne partie d’un programme informatique revient à manipuler des adresses mémoires.

Lorsqu’on a un nombre NN quelconque, il « suffit » de calculer n=log2Nn=\lceil log_2 N\rceil 2 pour savoir combien de bits sont nécessaires pour le représenter (au minimum). Dès lors, lorsqu’on représente un entier sur nn bits (autrement dit, à l’aide de nn bits), on peut représenter en pratique les entiers de 00 à 2n12^{n}-1. Ça signifie que 2n2^n ou 2n+12^n+1 ne possèdent pas de représentation si on utilise nn bits (ce serait équivalent à l’infini), on sort de l’espace de représentation. Et on va voir juste en dessous qu’on peut exploiter ce phénomène une fois qu’on en est conscient. :)


  1. Dans un scénario de type big-endian. Ce qui est la méthode naturelle pour écrire les nombres (chiffre de poids le plus fort à gauche), mais n’est pas la méthode employée sur un certain nombre d’architectures modernes, qui sont little-endian. Ici, on va travailler en big-endian et ne pas s’en soucier pour ne pas complexifier les explications (on garde donc l’ordre usuel).

  2. Les parenthèses \lceil \rceil signifient qu’il faut arrondir à l’entier supérieur, c’est l’équivalent de la fonction ceil() d’un grand nombre de langages de programmation.

Addition, soustraction et nombres négatifs en binaire

Comme on va le voir par la suite, les opérations avec le binaire sont en fait équivalentes à ce que vous avez fait en primaire, mais dans une base différente.

L’addition

Ainsi, l’addition de deux nombres peut s’effectuer comme un calcul écrit1. Par exemple, sur 5 bits, {11+13}10={01011+01101}2\{11+13\}_{10}=\{01011+01101\}_2 se calcule comme suit.

111101011+0110111000\begin{array}{cccccc} &\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}& \textcolor{blue}{1}\\ &0&1&0&1&1 \\ +&0&1&1&0&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &1&1&0&0&0 \end{array}

En effet, lorsqu’on a {1+1}2\{1+1\}_2, on dépasse la base, donc on écrit 020_2 et on reporte 121_2 (les reports sont indiqués en bleu). Et ainsi de suite. Lorsqu’on se retrouve avec {1+1+1}2\{1+1+1\}_2, on écrit et reporte 121_2, tout simplement. On obtient au final 11000211000_2, ce qui correspond bien à 241024_{10}.

Nombres négatifs

On pourrait tout simplement écrire 10112-1011_2, comme on le fait classiquement, mais on souhaite une représentation qu’on puisse facilement exploiter. En particulier, on veut que l’addition de nombres dans cette représentation soit aussi simple que l’addition en binaire qu’on a vu plus haut (et qu’on ait donc pas à s’inquiéter du signe). Ce qui permettrait, si c’est le cas, de ne pas avoir à s’inquiéter d’écrire un circuit pour la soustraction, puisque aba-b se calcule comme a+(b)a+(-b).

Première solution : le bit de signe

Une solution, pourrait être d’utiliser un bit de signe, disons le premier (celui de poids fort), et le reste des bits seraient la représentation sur n1n-1 bits de la valeur absolue du nombre.

Ainsi, 710-7_{10} serait écrit, sur 5 bits (par exemple), 101112\underline 10111_2, dont on saurait que le premier bit serait à 11 s’il s’agit d’un nombre négatif, 0 pour un nombre positif2. Notez que par facilité, je vais souligner le premier bit quand on sera dans une suite de bits représentant un nombre négatif, afin de les différentier d’une représentation non signée.

Le problème de cette représentation, c’est que 00 possède alors deux représentations, qui, sur 5 bits, seraient donc 000002\underline 00000_2 et 100002\underline 10000_2 (qui correspond à 0-0). Ce n’est pas quelque chose qui est forcément souhaitable (même si on pourrait s’en sortir). Par contre, cette représentation rend l’addition (ou la soustraction) de nombres signés relativement complexe à écrire, car l’addition de deux nombres signés de cette manière ne correspond pas à leur addition purement binaire.

Par exemple, soit le calcul {37}10\{3-7\}_{10}, qui dans cette représentation (sur 5 bits) s’écrit {00011+10111}2\{\underline 00011+\underline 10111\}_2 (on calcule en fait {3+(7)}10\{3+(-7)\}_{10}) :

11100011+1011111010\begin{array}{cccccc} &&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}\\ &0&0&0&1&1\\ +&1&0&1&1&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &1&1&0&1&0 \end{array}

Si on considère l’addition purement binaire, c’est correct (c’est comme si on calculait {3+23}10=2610=110102\{3+23\}_{10}=26_{10}=11010_2). Par contre, dans notre représentation, on a un nombre négatif (le premier bit est égal à 121_2), mais on obtient 1010-10_{10}, ce qui n’est pas la bonne réponse. Utiliser un bit de signe n’est donc pas une bonne idée dans ce cas ci.

Le complément à 1

Qu’à cela ne tienne, on a en fait déjà vu la solution : a+aˉ=0a+\bar a=0, ce qui est bien la propriété que doit respecter un nombre et son opposé négatif. Cette méthode s’appelle le complément à 1 et consiste à représenter le nombre négatif correspondant en inversant tous les bits (101\leftrightarrow 0). On constate que dans la pratique, les nombres négatifs ont alors leur bit de poids fort (le bit le plus à gauche) qui vaut 121_2, comme dans la technique du bit de signe.

Dès lors, si 7107_{10} correspond à 001112\underline 00111_2 sur 5 bits, alors 710-7_{10} correspond, dans cette représentation, à 001112=110002\overline{\underline 00111}_2 = \underline 11000_2 (tous les bits sont inversés et on voit que le bit de poids fort est égal à 1, comme avec le bit de signe, raison pour laquelle je vais continuer à le souligner). Et cette fois-ci, pour l’addition, ça fonctionne ! Si on reprend {37}10\{3-7\}_{10}, on a donc cette fois {00011+11000}2\{\underline 00011+\underline 11000\}_2, ce qui donne

00011+1100011011\begin{array}{cccccc} % &&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}\\ &0&0&0&1&1\\ +&1&1&0&0&0\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &1&1&0&1&1 \end{array}

On obtient cette fois 110112\underline 11011_2, ce qui équivaut bien à 410-4_{10}, puisque 410=0001002=110112\overline{4}_{10}=\overline{\underline 000100}_2=\underline 11011_2. On a donc une méthode qui permet de réaliser l’addition (et la soustraction) sans avoir à se soucier du signe (et, encore mieux, sans avoir à se soucier de savoir si les nombres qu’on manipule sont signés ou pas). Par contre, 0100_{10} possède toujours deux représentations (sur 5 bits, 111112\underline 11111_2 et 000002\underline 00000_2), ce qui n’a l’air de rien, mais demande en fait de tester deux valeurs pour savoir si un résultat est nul ou pas.

La solution finale : le complément à 2

On utilise donc la technique du complément à 2 : a=aˉ+1-a=\bar a +1. Tous les avantages du complément à 1 sont conservés, mais en plus, pour zéro, ça fonctionne, parce que, toujours sur 5 bits, 010=0000020_{10}=\underline 00000_2 et 010={00000+1}2={11111+1}2-0_{10} = \{\overline{\underline 00000}+1\}_2=\{\underline 11111+1\}_2, ce qui équivaut à…

1111111111+1100000\begin{array}{c|ccccc} \textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}\\ &1&1&1&1&1\\ +&&&&&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ 1&0&0&0&0&0 \end{array}

ce qui fonctionne, par ce qu’on travaille sur 5 bits (représenté par la barre verticale dans le calcul ci-dessus), on oublie donc le report sortant (report induit par l’addition des bits de poids fort, et qui « sort » des 5 bits), et on obtient 000002\underline 00000_2, donc on a bien 010=0100_{10}=-0_{10} dans le complément à 2. Pareil, ça fonctionne également dans le cas de {37}10\{3-7\}_{10}, sauf que cette fois-ci, 710={00111+1}2=110012-7_{10}=\{\overline{\underline 00111}+1\}_2=\underline 11001_2, et

1100011+1100111100\begin{array}{cccccc} &&&\textcolor{blue}{1}&\textcolor{blue}{1}\\ &0&0&0&1&1\\ +&1&1&0&0&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &1&1&1&0&0 \end{array}

Ce qui est bien la représentation de 410-4_{10} en complément à 2, puisque {000100+1}2=111002\{\overline{\underline 000100}+1\}_2=\underline 11100_2.

En fait, calculer la représentation de a-a comme le complément à deux de aa revient à calculer 2n1a2^{n-1}-|a|, où nn est le nombre de bits qu’on se donne pour représenter les nombres et a|a| la valeur absolue de aa. Autrement dit, si un nombre est écrit en complément à deux, alors le bit de poids fort correspond à 2n1-2^{n-1}, puis les autres puissances de 2 s’additionnent, comme vu précédemment. De ce fait, cette représentation permet de stocker des nombres allant de 2n1-2^{n-1} à 2n112^{n-1}-1.

Ainsi, si on reprend 410-4_{10} en complément à 2, c’est-à-dire 111002\underline 11100_2, cela correspond en base 10 à

111002={1×24+1×23+1×22+0×21+0×20}10={16+8+4}10=410.\begin{aligned} \underline 11100_2 &= \{-1\times 2^4+1\times2^3+1\times 2^2+0\times 2^1+0\times 2^0\}_{10} \\ &= \{-16+8+4\}_{10} \\ &= -4_{10}. \end{aligned}

Et on voit bien que les deux correspondent. On peut donc rapidement convertir un nombre négatif en base 10 selon la technique vue plus haut, en calculant 2n1a2^{n-1}-|a| et en représentant ce nombre dans les n1n-1 bits restants. Ainsi, pour représenter 7210-72_{10} en complément à deux, sur 8 bits, on calcule {2772}10\{2^7-72\}_{10}, ce qui fait 561056_{10}, et on représente 561056_{10} sur les 7 bits restants (par la technique de votre choix), donc 011100020111000_2. 7210=101110002-72_{10}=\underline 10111000_2 sur 8 bits en complément à 2.

Pour vous entraîner, vous pouvez convertir 3310-33_{10}, 12410-124_{10} et 110-1_{10} en complément à 2 sur 8 bits.

  • {2733}10=9510\{2^7-33\}_{10}= 95_{10}, or 9510=1011111295_{10}=1011111_2 (sur 7 bits), donc 3310=110111112-33_{10}=\underline 11011111_2 ;
  • {27124}10=410\{2^7-124\}_{10}= 4_{10}, or 410=000010024_{10}=0000100_2 (sur 7 bits), donc 12410=100001002-124_{10}=\underline 10000100_2 ;
  • {271}10=12710\{2^7-1\}_{10}= 127_{10}, or 12710=11111112127_{10}=1111111_2 (sur 7 bits), donc 110=111111112-1_{10}=\underline 11111111_2.

« Il y en a un peu plus, je vous le mets ? » (l’overflow)

On est passé très vite (exprès) sur le fait que dans certain calculs (entre autre le résultat de 010-0_{10} en complément à 2), on sorte de l’espace de représentation (qu’on ait un report sortant qui dépasse les nn bits qu’on s’est donné pour représenter notre nombre) n’était pas un problème. Sauf que des fois, c’est bien entendu quelque chose qu’on ne souhaite pas, et ce problème arrive quand le résultat du calcul n’est pas représentable avec l’espace de représentation qu’ont s’est fixé, c’est ce qu’on appelle l'overflow.

Évidement, ça ne peut jamais arriver lorsque on additionne des nombres de signes différents, ou qu’on soustrait des nombres de même signe, puisque dans ces cas, le résultat est forcément représentable si les opérandes le sont. Il reste donc à s’intéresser aux autres cas possibles (opérandes de même signe pour l’addition, de signes opposés pour la soustraction).

aa bb overflow sur a+ba+b ? overflow sur aba-b ?
>0 >0 peut être NON
>0 <0 NON peut être
<0 >0 NON peut être
<0 <0 peut-être NON

Voyons un peu quand ces cas aboutissent à un overflow : restons sur 5 bits et comparons les différents calculs suivants (la barre indique la limite des 5 bits).

00011+01000010111111101+11000110101101011+01100101111110101+10100101001\begin{array}{c|ccccc} %&&&\textcolor{blue}{1}&\textcolor{blue}{1}\\ \\ &0&0&0&1&1\\ +&0&1&0&0&0\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &0&1&0&1&1 \end{array} % \hspace{1cm} \begin{array}{c|ccccc} \textcolor{blue}{1}&\textcolor{blue}{1} \\ &1&1&1&0&1\\ +&1&1&0&0&0\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ 1&1&0&1&0&1 \end{array} %- \hspace{1cm} \begin{array}{c|ccccc} &\textcolor{blue}{1}\\ &0&1&0&1&1\\ +&0&1&1&0&0\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ &1&0&1&1&1 \end{array} %- \hspace{1cm} \begin{array}{c|ccccc} \textcolor{blue}{1}&&\textcolor{blue}{1} \\ &1&0&1&0&1\\ +&1&0&1&0&0\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ 1&0&1&0&0&1 \end{array}
  • Le premier et le deuxième cas (correspondant respectivement à {3+8}10\{3+8\}_{10} et {38}10\{-3-8\}_{10}) ne posent pas de problème : bien que l’on a un report sortant, les résultats sont corrects si on se limite aux 5 bits de notre représentation (ce qui est logique, puisque 111011_{10} et 1110-11_{10} sont tous les deux représentables sur 5 bits, puisque compris dans l’intervalle [1610,1510][-16_{10},15_{10}]).
  • Les deux cas suivants (correspondants respectivement à {11+12}10\{11+12\}_{10} et {1112}10\{-11-12\}_{10}) sont eux problématiques (ce qui, encore une fois, est logique).

La clé, c’est de regarder s’il y a un report entrant généré par l’addition impliquant le bit de poids fort (le bit de signe) : si on a un report entrant et sortant ou pas de report du tout, il n’y a pas de problème et il suffit de lire les bits sans s’inquiéter. S’il y a seulement un des deux reports qui est présent, alors on est dans un cas d'overflow.

Ainsi, dans le cas de la deuxième addition, il n’y a pas de problèmes car il y a report entrant et sortant pour le bit de signe, ce qui n’est pas le cas pour la troisième (report entrant, mais pas de report sortant) ou la quatrième (uniquement un report sortant). Si on note rsr_{s} le report généré par le bit de signe et rer_{e} le report entrant pour cette même addition de bits, alors,

rer_{e} rsr_{s} overflow
0 0 0
1 0 1
0 1 1
1 0 0

Ce qui correspond à la fonction logique rers+rersr_{e}\cdot\overline{r_{s}}+\overline{r_{e}}\cdot r_{s}, c’est à dire à un XOR (rersr_{e}\oplus r_{s}).

Il y a donc une différence à ce niveau-là entre les opérations sur entiers signés et non signés. En effet, dans le cas d’une opération sur nombres non-signés, l’absence de report entrant n’est pas un problème, seul la présence de report sortant l’est (puisque ça signifie qu’on sort de l’espace de représentation des entiers non-signés). Comme le processeur n’a pas moyen de savoir a priori s’il manipule des entiers signés ou pas (et que tout le but, c’est justement de ne pas trop à avoir à s’en inquiéter), les instructions processeurs correspondantes sont différentes pour les entiers signés ou pas.

La soustraction

On a donc vu que aba-b équivalait à a+(b)a+(-b) et qu’on pouvait représenter b-b en utilisant le complément à deux, ce qui, moyennant qu’il n’y ait pas d'overflow, fonctionne. On a vu que pour obtenir la représentation de b-b en complément à deux, on calculait bˉ+1\bar{b}+1. Alors, pour que ça soit plus rapide, pourquoi ne pas calculer a+bˉa+\bar{b}, en partant avec un report de 121_2 sur l’addition du bit de poids le plus faible ?

Prenons, par exemple, le calcul {156}10\{15-6\}_{10} (pas de problème d'overflow à l’horizon). Pour rappel 6ˉ10=001102=110012\bar 6_{10}=\overline{\underline 00110}_2=\underline 11001_2, et donc

11111101111+11001101001\begin{array}{c|ccccc} \textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{blue}{1}&\textcolor{red}{1}\\ &0&1&1&1&1\\ +&1&1&0&0&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}\\ 1&0&1&0&0&1 \end{array}

Le report entrant a été indiqué en rouge. On voit que

  1. On a effectivement pas de problème d'overflow, comme promis, puisque report généré par les deux dernières additions ;
  2. Que dès lors, si on se limite à 5 bits, on a bien la bonne réponse puisque 010012=91001001_2= 9_{10}.

Ce qui semble tenir de l’astuce ici est en fait beaucoup plus intelligent que ça : en remarquant ça, on se rend compte que pour calculer a±ba\pm b, on a en fait besoin que d’un seul circuit logique réalisant l’addition, et qui prendrait en entrée bb ou bˉ\bar b et un report entrant ou pas pour avoir un circuit qui réalise l’addition et la soustraction sans trop avoir à se fatiguer (puisque sinon, il faudrait d’abord calculer bˉ+1\bar b +1 avant de l’additionner à aa). D’ailleurs, c’est ce qu’on va exploiter au prochain chapitre.

Bonus : ce qu’implique le complément à 2

Voici quelques effets, parfois surprenants, de l’utilisation de la représentation en complément à 2 pour les nombres négatifs :

  1. Il est facile d’étendre un nombre dans une représentation donnée à une autre représentation : il suffit de recopier le bit de signe (celui que je souligne) autant de fois que nécessaire (c’est ce qu’on appelle l’extension de signe). Ainsi, sur 5 bits, 710=00011127_{10}=\underline 000111_2, et 710=110012-7_{10}=\underline 11001_2. Eh bien sur 8 bits, ces mêmes nombres sont 000001112\textcolor{blue}{\underline 000}00111_2 et 111110012\textcolor{blue}{\underline 111}11001_2, respectivement (l’extension de signe est indiquée en bleu).

  2. La comparaison d’entier non-signés et d’entier signés n’est plus là même, puisque une comparaison lexicographique classerait alors les nombres négatifs avant les positifs. Néanmoins, en pratique, la comparaison d’entiers se fait en effectuant une soustraction : si le résultat est différent de 0 (ou qu’il y a eu overflow), alors les deux nombres ne sont pas les mêmes (le signe du résultat et la présence d’un overflow indique même si les deux nombres comparés sont plus grands ou plus petits l’un par rapport à l’autre). Et cette approche fonctionne que l’entier soit signé ou non.

  3. Le nombre le plus négatif, 2n1-2^{n-1}, est égal à son complément à 2 (de la même manière que le calcul de 010-0_{10} génère 0100_{10}). Du coup, dans certains langages de programmation, la fonction abs() (ou équivalent), qui calcule la valeur absolue d’un nombre entier, peut avoir un comportement inattendu lorsqu’on calcule la valeur absolue de ce nombre en question.

    Le dernier point est par exemple vrai en C3, où on utilise INT_MIN pour représenter le nombre le plus négatif représentable dans le type int (entiers), et où INT_MIN == -INT_MIN. Dès lors, on peut avoir ce genre de comportement.

    // petit code à compiler par exemple avec "gcc -o test main.c"
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h> 
    
    int main() {
        printf("abs(%d) = %d\n", -16, abs(-16)); 
        // donne "abs(-16) = 16"
        
        printf("abs(%d) = %d\n", 8, abs(8)); 
        // donne "abs(8) = 8"
        
        printf("abs(%d) = %d\n", INT_MIN, abs(INT_MIN));
        // donne, chez moi, "abs(-2147483648) = -2147483648", 
        // mais ça dépendra de la valeur de INT_MIN chez vous.
    }
    

    Ce « bug » provient de l’implémentation de abs() en C, qui pourrait ressembler à ceci.

    /* Ceci est une implémentation naïve et très peu efficace. */
    int abs(int n) {
      if (n >= 0)
        return n;
      else
        return -n; // ici, -a != |a| si a = INT_MIN 
    }
    

    Comme ça, vous savez! :pirate:


  1. Et d’ailleurs, ça fonctionne pour n’importe quelle base.

  2. C’est une convention, qui en vaut une autre. D’ailleurs peu importe.

  3. Mais aussi au moins en C++ et en Java. J’ai pas testé pour les autres, et c’est pas réellement grave.

Multiplication et divison binaire

Au détail du complément à deux, on a vu que les vieilles recettes de primaire fonctionnaient bien ici. Eh bien la bonne nouvelle, c’est que c’est toujours le cas pour les deux dernières opérations mathématiques !

La multiplication (shift, add, shift, add, …)

Pour rappel, la multiplication de deux nombres, {a×b}B={an1an2a0×bm1bm2b0}B\{a\times b\}_{\mathfrak{B}} = \{a_{n-1}a_{n-2}\ldots a_0\times b_{m-1}b_{m-2}\ldots b_0\}_\mathfrak{B}, quelles que soient leurs bases (disons donc B\mathfrak{B}), se cacule comme b0×a+b1×a×B+b2×a×B2+b_0\times a + b_1\times a \times \mathfrak{B} + b_2\times a \times \mathfrak{B}^2+\ldots, soit:

a×b=i=0m1bi×a×Bia\times b = \sum_{i=0}^{m-1} b_i\times a\times \mathfrak{B}^i

mm et nn sont le nombre de chiffes dans bb et aa, respectivement. Maintenant, cette écriture mathématique « cache » le fait que multiplier un nombre par Bi\mathfrak{B}^i, ce n’est jamais que décaler le nombre de ii positions vers la gauche : {32×103}10=3200010\{32\times 10^3\}_{10}=32\textcolor{blue}{000}_{10}, je ne vous apprends normalement rien. Et ce qui est vrai dans n’importe quelle base est vrai en binaire, dans lequel décaler les bits vers la droite multiplie le nombre par 2 (pour ce qui est des entiers non signés, en tout cas). Dès lors, la multiplication de nombres entiers non-signés revient à une série d’addition du multiplicande1, de plus en plus décalé vers la droite. L’avantage du binaire, c’est que si le bit correspondant dans le multiplicateur est 020_2, pas besoin de réaliser l’addition.

a×b=i=0m1{0si bi=0,aisi bi=1.a\times b = \sum_{i=0}^{m-1} \begin{cases} 0&\text{si }b_i=0, \\ a \ll i&\text{si }b_i=1. \end{cases}

aia\ll i représente ici aa décalé de ii positions vers la gauche2.

Ainsi, {7×13}10={00111×01101}2\{7\times 13\}_{10}=\{00111\times 01101\}_2 (sur 5 bits, et en non-signé) équivaut à :

00111×011010011100111+001110001011011\begin{array}{ccccccccccc} &&&&&&0&0&1&1&1\\ &&&&&\times&0&1&1&0&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &&&&&&0&0&1&1&1\\ &&&&0&0&1&1&1&&\\ +&&&0&0&1&1&1&&&\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &0&0&0&1&0&1&1&0&1&1 \end{array}

Le produit, 00010110112=91100001011011_2=91_{10} correspond bien au résultat de {7×13}10\{7\times 13\}_{10}. Par contre, on voit que la multiplication de deux nombres constitués de nn bits génère en fait un nombre composé de 2n2n bits, ce qui est relativement logique, et d’ailleurs les multiplications ne génèrent pas d’erreur d'overflow au niveau du processeur, dès lors stocké dans deux nombres de nn bits chacun3 (par contre, ce que le programme reçoit en retour est souvent la partie de nn bits la plus à droite, mais ça dépend du langage de programmation).

Pour ce qui est de la multiplication d’entiers signés, le seul cas problématique (au delà de l'overflow) est le cas où le multiplicateur est négatif. En effet, si c’est le multiplicande qui est négatif, cela fonctionne quand même (pour peu qu’on ne sorte pas de la représentation). Pour preuve, {3×3}10={11101×00011}2\{-3\times 3\}_{10}=\{\underline 11101\times \underline 00011\}_2 (sur 5 bits, pour pas changer) vaut (la barre verticale indique la limite de 5 bits) :

11101×0001111101+111010000110111\begin{array}{cccccc|ccccc} &&&&&&1&1&1&0&1\\ &&&&&\times&0&0&0&1&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &&&&&&1&1&1&0&1\\ +&&&&&1&1&1&0&1&\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &0&0&0&0&1&1&0&1&1&1\\ \end{array}

Et ça fonctionne (si on se limite aux 5 bits les plus à droite), puisque 101112=910\underline 10111_2=-9_{10}.

Dès lors, une solution lorsqu’on a un multiplicateur négatif, ben … C’est de prendre le négatif du multiplicateur et du multiplicande4. Mathématiquement, ça se tient, puisque a×b=(1)×a×b=a×ba\times-b=(-1)\times a\times b = -a\times b, mais on voit que le multiplicateur est alors positif. Et ça, on vient de voir que ça fonctionnait.

On peut donc calculer sans problème {5×3}10\{5\times -3\}_{10} comme {5×3}2={11011×00011}2\{-5\times 3\}_2=\{\underline 11011\times \underline 00011\}_2 (la barre verticale indique encore et toujours la limite des 5 bits),

11011×0001111011+110110000110001\begin{array}{cccccc|ccccc} &&&&&&1&1&0&1&1\\ &&&&&\times&0&0&0&1&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &&&&&&1&1&0&1&1\\ +&&&&&1&1&0&1&1&\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em} &\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &0&0&0&0&1&1&0&0&0&1\\ \end{array}

Bien entendu, 100012=1510\underline 10001_2=-15_{10}.

Pendant très longtemps, les processeurs ne possédaient pas de circuits logiques spécifiques5 pour la multiplication. Quand on y réfléchit, on se rend compte que la manière vue ci-dessus est quand même très lente, puisque faire une multiplication de deux nombres de nn bits requiert au final 2n2n additions (et, si on y réfléchit pas, un additionneur qui travaille avec 2n2n bits, mais il y a moyen de s’en passer). Heureusement, il existe des algorithmes beaucoup plus efficaces, réduisant le nombre d’addition à effectuer (la page Wikipédia de la multiplication donne quelques pistes à ce sujet). Néanmoins, le message reste vrai : une multiplication, c’est une série de décalages et d’additions.

La division entière (shift, sub, shift, sub …) et le modulo

Pour commencer, rappelons que la division revient à une série de soustraction du dividende par le diviseur (autant de fois qu’il faut pour obtenir un reste qui soit plus petit que le diviseur). Bien entendu, ça, c’est la manière la plus inefficace de faire (imaginez le temps que ça prendrait de diviser par 2102_{10} des très grands nombres).

Ici, le calcul écrit nous permet d’aller plus vite que ça. Si on calcule par exemple {23÷4}10\{23\div 4\}_{10} en non-signé, {10111÷(00)100}2\{10111\div (00)100\}_2, on a

1011110010010111110011\begin{array}{cccccc|ccc} &1&0&1&1&1&1&0&0\\ &&&&&\rule{1em}{1pt}\hspace{-2.3em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ -&1&0&0&&&1&0&1\\ \rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}\\ &&&1&1&1\\ &&-&1&0&0\\ &&\rule{2em}{1pt}\hspace{-2em}&\rule{2em}{1pt}\hspace{-2em}&\rule{2.5em}{1pt}\hspace{-2em}\\ &&&&1&1 \end{array}
Division écrite en binaire. On obtient 001012=51000101_2=5_{10} et 112=31011_2=3_{10} pour reste, ce qui est juste. :)

Néanmoins, quand on écrit ça, même si c’est correct, on fait plein de simplifications dans notre tête. Ainsi, on décale le diviseur vers la droite petit à petit. Mais surtout, on ne fait pas la soustraction lorsque on voit bien que le reste issu de la soustraction précédente est plus petit que le diviseur, et on continue alors de décaler le diviseur vers la droite, tout en considérant le bit suivant du dividende. Une implémentation basique de la division consiste à effectuer cette différence, mais à ne pas conserver le reste si celui-ci est inférieur à 0. Les bits du quotient sont alors mis en fonction de si le reste est supérieur ou strictement inférieur à 0.

On constate que la division de deux nombres de 2n2n bits donne, tout au plus, un quotient de nn bits et un reste de nn bits. Le quotient est le résultat de la division entière tandis que le reste est le résultat du modulo du dividende et du quotient, ce qu’on écrit très souvent en programmation reste = a % b.

Une fois encore, ce n’est pas la manière la plus efficace de faire, et des algorithmes plus efficaces existent (voir à ce sujet la page Wikipédia sur les algorithmes de division (en)).


  1. Oui, moi aussi je l’ai découvert en écrivant ce tuto, si a×ba\times b, aa est le multiplicande (et oui, c’est un nom masculin) et bb le multiplicateur.

  2. Notation empruntée à différents langages de programmation, car il n’existe pas de symboles mathématiques pour ça, ou en tout cas pas que je connaisse. :)

  3. Deux registres de nn bits, quoi. Bien entendu, si on écrit un peu de code assembleur, il y a moyen de récupérer le second registre.

  4. Une autre solution ça serait de faire une extension de signe des nombres de nn bits sur 2n2n bits, mais déjà que ce qu’on voit là n’est pas hyper efficace, ça le serait encore moins.

  5. Et pas d’instruction assembleur correspondante non plus.


Les nombres flottants ont été écartés de ce tutoriel afin de ne pas complexifier les choses. En effet, la représentation de ces nombres en utilisant la virgule flottante est très intéressante, mais dépasse de très loin ce dont on a besoin ici. Si ça vous intéresse, je vois renvois à la page Wikipédia correspondante, mais aussi à ce tutoriel qui présente une représentation alternative.

Au-delà de la représentation binaire des nombres entiers (positifs et négatifs), on a vu qu’il suffisait d’un circuit réalisant l’addition (et la soustraction, mais l’utilisation du complément à deux rend ça compatible avec un circuit réalisant l’addition) pour réaliser les 4 (+1, le modulo) opérations mathématiques de bases. En combinant ce circuit avec l’une ou l’autre fonctionnalités supplémentaires (quelques opérations logiques), on peut réaliser ce qu’on appelle une ALU, ou arithmetic-logic unit. Et comme on a vu tous les outils pour en réaliser une version simple, c’est ce que je me propose de vous montrer dans le prochain et dernier chapitre.

On s’y voit de suite. :)

Et si vous souhaitez voir comment on peut exploiter le binaire de façon plus complète dans vos codes, vous pouvez également lire ce tutoriel de Lucas-84.