Un détour nécessaire : le binaire

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 $10_8$, c’est-à-dire « 10 » en base 8. Et en binaire, c’est-à-dire en base 2, $2_{10}$ est représenté par $10_{2}$ (c’est-à-dire « 10 » en base 2).

Conversion en base 10

Instinctivement, on sait que si on a par exemple $1235_{10}$, c’est équivalent à $\{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 :

$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 $a$ composés de $n$ chiffres $a_i$ dans une base donnée peut donc s’écrire comme $a_{n-1}a_{n-2}\ldots a_0$. Un nombre $a_{\mathfrak{B}}$ dans une base $\mathfrak{B}$ correspond, en base 10, à :

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

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

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 $1085_9$, $11213_4$ et $1F75_{16}$ en base 10, sachant que pour la base 16 (hexadécimale), on considère que $10_{10} = A_{16}$, $11_{10} = B_{16}$, et ainsi de suite.

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.¹

Conversion d’une base 10 vers une base quelconque

Si on veut convertir un nombre donné en base 10 vers une base quelconque, disons $\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 $\mathfrak{B}$, puis à écrire le reste de cette division à côté, pour ensuite diviser le quotient par $\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.

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

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 $2^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 $724_{10}$ en binaire. La plus grande puissance de 2 inférieure à 724, c’est 512 ($2^9$). On a donc :

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).

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

ce qui signifie que $724_{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 $1_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 $N$ quelconque, il « suffit » de calculer $n=\lceil log_2 N\rceil$ ² pour savoir combien de bits sont nécessaires pour le représenter (au minimum). Dès lors, lorsqu’on représente un entier sur $n$ bits (autrement dit, à l’aide de $n$ bits), on peut représenter en pratique les entiers de $0$ à $2^{n}-1$. Ça signifie que $2^n$ ou $2^n+1$ ne possèdent pas de représentation si on utilise $n$ 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.

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 écrit¹. Par exemple, sur 5 bits, $\{11+13\}_{10}=\{01011+01101\}_2$ se calcule comme suit.

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

Nombres négatifs

On pourrait tout simplement écrire $-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 $a-b$ se calcule comme $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 $n-1$ bits de la valeur absolue du nombre.

Ainsi, $-7_{10}$ serait écrit, sur 5 bits (par exemple), $\underline 10111_2$, dont on saurait que le premier bit serait à $1$ s’il s’agit d’un nombre négatif, 0 pour un nombre positif². 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 $0$ possède alors deux représentations, qui, sur 5 bits, seraient donc $\underline 00000_2$ et $\underline 10000_2$ (qui correspond à $-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 $\{3-7\}_{10}$, qui dans cette représentation (sur 5 bits) s’écrit $\{\underline 00011+\underline 10111\}_2$ (on calcule en fait $\{3+(-7)\}_{10}$) :

Si on considère l’addition purement binaire, c’est correct (c’est comme si on calculait $\{3+23\}_{10}=26_{10}=11010_2$). Par contre, dans notre représentation, on a un nombre négatif (le premier bit est égal à $1_2$), mais on obtient $-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+\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 ($1\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 $1_2$, comme dans la technique du bit de signe.

Dès lors, si $7_{10}$ correspond à $\underline 00111_2$ sur 5 bits, alors $-7_{10}$ correspond, dans cette représentation, à $\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 $\{3-7\}_{10}$, on a donc cette fois $\{\underline 00011+\underline 11000\}_2$, ce qui donne

On obtient cette fois $\underline 11011_2$, ce qui équivaut bien à $-4_{10}$, puisque $\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, $0_{10}$ possède toujours deux représentations (sur 5 bits, $\underline 11111_2$ et $\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=\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, $0_{10}=\underline 00000_2$ et $-0_{10} = \{\overline{\underline 00000}+1\}_2=\{\underline 11111+1\}_2$, ce qui équivaut à…

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 $\underline 00000_2$, donc on a bien $0_{10}=-0_{10}$ dans le complément à 2. Pareil, ça fonctionne également dans le cas de $\{3-7\}_{10}$, sauf que cette fois-ci, $-7_{10}=\{\overline{\underline 00111}+1\}_2=\underline 11001_2$, et

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

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

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 $2^{n-1}-|a|$ et en représentant ce nombre dans les $n-1$ bits restants. Ainsi, pour représenter $-72_{10}$ en complément à deux, sur 8 bits, on calcule $\{2^7-72\}_{10}$, ce qui fait $56_{10}$, et on représente $56_{10}$ sur les 7 bits restants (par la technique de votre choix), donc $0111000_2$. $-72_{10}=\underline 10111000_2$ sur 8 bits en complément à 2.

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

« 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 $-0_{10}$ en complément à 2), on sorte de l’espace de représentation (qu’on ait un report sortant qui dépasse les $n$ 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).

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).

• Le premier et le deuxième cas (correspondant respectivement à $\{3+8\}_{10}$ et $\{-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 $11_{10}$ et $-11_{10}$ sont tous les deux représentables sur 5 bits, puisque compris dans l’intervalle $[-16_{10},15_{10}]$).
• Les deux cas suivants (correspondants respectivement à $\{11+12\}_{10}$ et $\{-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 $r_{s}$ le report généré par le bit de signe et $r_{e}$ le report entrant pour cette même addition de bits, alors,

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

La soustraction

On a donc vu que $a-b$ équivalait à $a+(-b)$ et qu’on pouvait représenter $-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$ en complément à deux, on calculait $\bar{b}+1$. Alors, pour que ça soit plus rapide, pourquoi ne pas calculer $a+\bar{b}$, en partant avec un report de $1_2$ sur l’addition du bit de poids le plus faible ?

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

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 $01001_2= 9_{10}$.

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, $7_{10}=\underline 000111_2$, et $-7_{10}=\underline 11001_2$. Eh bien sur 8 bits, ces mêmes nombres sont $\textcolor{blue}{\underline 000}00111_2$ et $\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, $-2^{n-1}$, est égal à son complément à 2 (de la même manière que le calcul de $-0_{10}$ génère $0_{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 C³, 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!

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\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 $\mathfrak{B}$), se cacule comme $b_0\times a + b_1\times a \times \mathfrak{B} + b_2\times a \times \mathfrak{B}^2+\ldots$, soit:

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

où $m$ et $n$ sont le nombre de chiffes dans $b$ et $a$, respectivement. Maintenant, cette écriture mathématique « cache » le fait que multiplier un nombre par $\mathfrak{B}^i$, ce n’est jamais que décaler le nombre de $i$ positions vers la gauche : $\{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 multiplicande¹, de plus en plus décalé vers la droite. L’avantage du binaire, c’est que si le bit correspondant dans le multiplicateur est $0_2$, pas besoin de réaliser l’addition.

où $a\ll i$ représente ici $a$ décalé de $i$ positions vers la gauche².

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

Le produit, $0001011011_2=91_{10}$ correspond bien au résultat de $\{7\times 13\}_{10}$. Par contre, on voit que la multiplication de deux nombres constitués de $n$ bits génère en fait un nombre composé de $2n$ 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 $n$ bits chacun³ (par contre, ce que le programme reçoit en retour est souvent la partie de $n$ 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\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) :

Et ça fonctionne (si on se limite aux 5 bits les plus à droite), puisque $\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 multiplicande⁴. Mathématiquement, ça se tient, puisque $a\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\times -3\}_{10}$ comme $\{-5\times 3\}_2=\{\underline 11011\times \underline 00011\}_2$ (la barre verticale indique encore et toujours la limite des 5 bits),

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

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 $2_{10}$ des très grands nombres).

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

$\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}$

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 $2n$ bits donne, tout au plus, un quotient de $n$ bits et un reste de $n$ 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.