MaDIR Représentation des nombres

Section 3.1 Représentation des nombres

À l’école primaire, on apprend à interpréter un nombre comme \(1234\) en le décomposant selon ses unités, dizaines, centaines et milliers. En termes plus mathématiques, on peut écrire

\begin{equation*} 1234=1\times 1000+2\times 100+3\times 10+4\times 1\text{.} \end{equation*}

Pourquoi une telle décomposition? D’où vient le choix de \(1,10,100\) et \(1000\text{?}\) L’hypothèse la plus plausible est que les systèmes de numération qui se développèrent au fil du temps ont en quelque sorte convergé vers l’utilisation des chiffres \(0,1,2,\ldots,9\text{;}\) dix symboles, autant de doigts qu’un humain possède.

🔗

L’importance du nombre dix se fait d’autant plus remarquer quand on réécrit

\begin{equation} 1234=1\times 10^3+2\times 10^2+3\times 10^1+4\times 10^0\text{.}\tag{3.1.1} \end{equation}

Cela n’a toutefois pas toujours été ainsi. Différents système de représentation des nombres ont été élaborés dans l’histoire. Encore aujourd’hui, d’autres systèmes sont utilisés dans certains contextes. En informatique, la représentation binaire est prédominante.

🔗

Dans cette section, on rappelle la notion d’écriture en base dix, on définit la représentation en base deux (binaire) et seize (hexadécimale). On effectue aussi des opérations élémentaires sur les nombres écrits en base deux et on voit comment convertir un nombre d’une base à une autre.

🔗

Sous-section 3.1.1 Systèmes positionnels

La représentation d’un nombre peut se faire de plusieurs manières. Une manière brute et assez inefficace consiste par exemple à faire un trait pour chaque unité. Ce système devient vite encombrant et il est difficile de rapidement lire un nombre. D’autres systèmes un peu mieux ont été inventés par différentes civilisations au cours de l’histoire. Un système dans lequel un nombre peut s’écrire sous une forme ressemblant à l’équation (3.1.1) de l’introduction est appelé un système positionnel. Ces systèmes sont normalement construits selon une base entière \(b>1\text{,}\) dans le cas de l’introduction, c’est dix, et d’un ensemble de symboles en nombre égal à la base. On peut utiliser une base différente, par exemple quatre avec les symboles \(0,1,2,3\text{,}\) pour représenter n’importe quel nombre.

🔗

Chaque position correspond à une puissance de la base, puissance croissante lorsqu’on lit le nombre de droite à gauche. Ainsi le nombre à droite correspond aux unités, le deuxième nombre correspond à un multiple de \(b\text{,}\) le troisième au multiple de \(b^2\) et ainsi de suite. Afin de distinguer du cas usuel, lorsque la base sera différente de dix, on l’indiquera en indice. Cet indice sera toujours sous-entendu comme étant écrit en base dix.

🔗

Exemple 3.1.1. Des exemples en base quatre.

On considère les nombres suivants, écrits en base quatre:

\(123_4\text{;}\)
🔗

🔗
\(102030_4\text{;}\)
🔗

🔗
\(3223_4\text{.}\)
🔗

🔗

On cherche leur valeur en base dix.

🔗

Solution.

L’idée est de reprendre le principe de la décomposition sous une forme des puissances de \(4\text{.}\)

🔗

On a donc

\begin{equation*} 123_4=1\times 4^2+2\times 4^1 +3\times 4^0=16+8+3=27\text{.} \end{equation*}

🔗

🔗
De plus,

\begin{equation*} 102030_4=1\times 4^5 + 0\times 4^4 + 2\times 4^3 + 0\times 4^2 + 3\times 4^1 + 0\times 4^0=1164 \text{.} \end{equation*}

🔗

🔗
Finalement,

\begin{equation*} 3223_4=3\times4^3+2\times 4^2+2\times 4^1+3\times 4^0=235\text{.} \end{equation*}

🔗

🔗

🔗

La figure interactive 3.1.2 permet de visualiser les nombres de \(0\) à \(30\) dans chacune des bases deux,trois, quatre et cinq. Il est intéressant de voir comment la représentation d’un nombre évolue au fur et à mesure que celui-ci grandit.

🔗

Instructions.

Le curseur \(b\) représente la base utilisée et le curseur \(n\) représente le nombre en base dix. On peut choisir de voir comment un nombre change selon la base ou voir comment les nombres changent pour une base donnée.

🔗

Figure 3.1.2. Les nombres de \(0\) à \(30\) dans différentes bases

🔗

Sous-section 3.1.2 Représentation en base deux

Autre que la base dix, la base deux, ou représentation binaire est probablement la plus utilisée. Une des raisons est que les signaux envoyés par les pièces électroniques se trouvent en deux états, tel que mentionné dans la section 2.4. La représentation binaire utilise les puissances de deux et l’ensemble de chiffres \(\{0,1\}\) pour représenter les nombres. Tout nombre entier peut être représenté comme une somme de termes \(d\times 2^n\) où \(d\in \{0,1\}\) et \(n\in \N\text{.}\) Les nombres de \(0\) à \(30\) peuvent être visualisés dans la figure interactive 3.1.2 en mettant la valeur de \(b=2\text{.}\)

🔗

La conversion d’un nombre d’une base à l’autre dépend des bases utilisées. Lorsque la base dix est impliquée, le processus est plus naturel. On peut comparer la conversion à la traduction entre deux langues. Traduire un mot d’une langue proche de la sienne, mais inconnue, est souvent un peu plus simple que de prendre un mot de sa langue et le traduire dans la langue inconnue. C’est un peu le même principe pour la conversion entre une base \(b\) et la base dix. De la base \(b\) vers dix est un peu plus simple que de la base dix vers la base \(b\text{.}\) Pour le binaire, connaitre les premières puissances de deux peut-être pratique. Les \(13\) premières sont données dans la table 3.1.3.

🔗

Table 3.1.3. Les premières puissances de \(2\)

🔗

Puissance de \(2\)

\(2^{12}\)
\(2^{11}\)
\(2^{10}\)
\(2^{9}\)
\(2^8\)
\(2^7\)
\(2^6\)
\(2^5\)
\(2^4\)
\(2^3\)
\(2^2\)
\(2^1\)
\(2^0\)

Valeur en base dix
\(4096\)
\(2048\)
\(1024\)
\(512\)
\(256\)
\(128\)
\(64\)
\(32\)
\(16\)
\(8\)
\(4\)
\(2\)
\(1\)

Exemple 3.1.4. Du binaire vers la base dix.

On veut convertir les nombres suivants en base dix:

\(100110_2\text{;}\)
🔗

🔗
\(110111_2\text{;}\)
🔗

🔗
\(111111_2\text{;}\)
🔗

🔗
\(100100100_2\text{.}\)
🔗

🔗

🔗

Solution.

On réécrit avec les puissances de deux

\begin{equation*} 100110_2=1\times 32+0\times 16+0\times 8+1\times 4+1\times 2+0\times 1=38\text{.} \end{equation*}

🔗

🔗
On réécrit avec les puissances de deux

\begin{equation*} 110111_2=1\times 32+1\times 16+0\times 8+1\times 4+1\times 2+1\times 1=55\text{.} \end{equation*}

🔗

🔗
On réécrit avec les puissances de deux

\begin{equation*} 111111_2=1\times 32+1\times 16+1\times 8+1\times 4+1\times 2+1\times 1=63\text{.} \end{equation*}

🔗

🔗
On réécrit avec les puissances de deux

\begin{equation*} 100100100_2= 1\times 256+ 0\times 128+ 0\times 64+1\times 32+0\times 16+0\times 8+1\times 4+0\times 2+0\times 1=292\text{.} \end{equation*}

🔗

🔗

🔗

Une méthode pour convertir un nombre de la base décimale à une autre base est présentée ci-dessous. Une autre méthode sera présentée dans la section suivante.

🔗

Exemple 3.1.5. De la base dix vers le binaire.

On cherche à convertir les nombres suivants en binaire:

\(101\text{;}\)
🔗

🔗
\(187\text{.}\)
🔗

🔗

🔗

Solution 1.

On sait qu’un nombre en binaire va s’écrire sous la forme \(d_n2^n+d_{n-1}2^{n-1}+\cdots + d_12^1+d_02^0\) avec tous les \(d_k\in \{0,1\}\text{.}\) Pour trouver \(n\text{,}\) on cherche la plus grande puissance de la base qui est plus petite ou égale au nombre à convertir. Le nombre \(n\) sera la valeur de cette puissance. Ainsi pour \(101\text{,}\) la plus grande puissance qui est plus petite est \(2^6=64\text{.}\) On a donc

\begin{equation*} 101=d_62^6+d_{5}2^{5}+\cdots + d_12^1+d_02^0\text{.} \end{equation*}

🔗

Il faut ensuite choisir la plus grande valeur de \(d_n\) possible de sorte que \(d_n b^n\) soit inférieure au nombre \(n\text{.}\) Pour la base deux, le choix est simple et sera toujours \(1\text{.}\) Ainsi pour \(101\text{,}\) on a \(d_6=1\text{:}\)

\begin{equation*} 101=2^6+d_{5}2^{5}+\cdots + d_12^1+d_02^0\text{.} \end{equation*}

On envoie le terme trouvé du côté du nombre \(n\) en soustrayant et on répète ce processus jusqu’à ce que tous les \(d_k\) soient déterminés.

\begin{align*} 101-2^6&=d_{5}2^{5}+d_{4}2^{4}+d_{3}2^{3}+d_{2}2^{2} + d_12^1+d_02^0\\ 37&=d_{5}2^{5}+d_{4}2^{4}+d_{3}2^{3}+d_{2}2^{2} + d_12^1+d_02^0\\ \end{align*}

La plus grande puissance plus petite que le nombre à gauche est \(2^5\)

\begin{align*} 37&=2^5+d_{4}2^{4}+d_{3}2^{3}+d_{2}2^{2} + d_12^1+d_02^0\\ 37-2^5&=d_{4}2^{4}+d_{3}2^{3}+d_{2}2^{2} + d_12^1+d_02^0\\ 5&=d_{4}2^{4}+d_{3}2^{3}+d_{2}2^{2} + d_12^1+d_02^0\\ \end{align*}

La plus grande puissance qui est plus petite que 5 est 4. Les puissances précédentes qui ne sont pas utilisées sont multipliées par zéro.

\begin{align*} 5&=0\times 2^{4}+0\times 2^{3}+2^{2} + d_12^1+d_02^0\\ 5-2^2&=d_1 2^1+d_02^0\\ 1&=d_1 2^1+d_02^0\\ \end{align*}

La puissance 0 est égale à 1 et donc

\begin{align*} 1&=0\times 2^1+2^0\text{.} \end{align*}

En reprenant les valeurs de \(d_k\) non nulles, on a

\begin{equation*} 101=1100101_2\text{.} \end{equation*}

🔗

Solution 2.

On montre une manière plus concise d’écrire le raisonnement précédent. La plus grande puissance de \(2\) qui est inférieure ou égale à \(187\) est \(128\text{.}\) On a donc

\begin{align*} 187&=128+\text{quelque chose}\\ \end{align*}

Puisque 187-128=59 et que la plus grande puissance de 2 inférieure à 59 est 32, on a

\begin{align*} 187&=128+32+\text{autre chose}\\ \end{align*}

autre chose doit être égal à 27 lorsqu’on fait la soustraction. La plus grande puissance inférieure à cela est 16 et donc

\begin{align*} 187&=128+32+16+\text{quelque chose d'autre}\\ \end{align*}

on poursuit ainsi et on obtient finalement

\begin{align*} 187&=128+32+16+8+2+1\\ 187&=10111011_2 \end{align*}

🔗

En plus des nombres naturels, on peut aussi représenter les nombres négatifs ou même réels en d’autres bases. Pour un nombre négatif, on se contentera de convertir le nombre en valeur absolue en binaire et d’ajouter un signe \(-\) devant. Pour un ordinateur toutefois, la réalité est un peu plus complexe. Pour les nombres décimaux, on peut procéder d’une manière similaire à celles utilisées pour convertir d’une base à l’autre. Si on considère un nombre à virgule écrit en binaire (dont la partie entière sera \(0\text{,}\) pour simplifier), par exemple \(0.1011001_2\text{,}\) alors il suffit de poursuivre l’écriture en puissance avec des nombres négatifs:

\begin{equation*} 0\times 2^0+d_{-1}2^{-1}+d_{-2}2^{-2}+\cdots +d_{-m}2^{-m}\text{.} \end{equation*}

À noter toutefois que, comme dans le cas des nombres décimaux, il est possible que la partie fractionnaire soit infinie, périodique ou non. On se contentera de cas où la représentation sera finie.

🔗

Exemple 3.1.6. D’une représentation binaire fractionnaire à décimale.

On considère le nombre \(0.1011_2\) et on cherche sa conversion en base dix.

🔗

Solution.

On décompose le nombre selon les puissances négatives de \(2\) pour obtenir

\begin{equation*} 0.1011_2=1\times 2^{-1}+0\times 2^{-2}+1\times 2^{-3}+1\times 2^{-4}=0.5+0.125+0.0625=0.6875\text{.} \end{equation*}

🔗

Il est possible qu’un nombre ayant une représentation décimale finie possède une représentation binaire infinie, il faut donc bien choisir les exemples pour éviter que cela arrive. Dans la prochaine section, on verra comment convertir un nombre décimal qui devient à représentation infinie périodique. La table suivante pourra être utile.

🔗

Table 3.1.7.

🔗

Puissance de \(2\)	\(2^{-1}\)	\(2^{-2}\)	\(2^{-3}\)	\(2^{-4}\)	\(2^{-5}\)	\(2^{-6}\)	\(2^{-7}\)	\(2^{-8}\)
Valeurs décimales	\(0.5\)	\(0.25\)	\(0.125\)	\(0.0625\)	\(0.03125\)	\(0.015625\)	\(0.0078125\)	\(0.00390625\)

Exemple 3.1.8. D’une représentation décimale fractionnaire à binaire.

On veut convertir le nombre \(0.40625\) en binaire.

🔗

Solution.

L’idée est la même que celle utilisée à l’exemple 3.1.5. On cherche la plus grande puissance de \(2\) qui est plus petite ou égale à \(0.40625\text{.}\) Dans ce cas, c’est \(2^{-2}=0.25\text{.}\) On a donc

\begin{align*} 0.40625&=0\times 2^{-1}+1\times 2^{-2}+\text{autre chose}\\ \end{align*}

En soustrayant, il reste 0.15625, pour lequel 0.125 est la plus grande puissance inférieure ou égale à ce nombre. On a alors

\begin{align*} 0.40625&=0\times 2^{-1}+1\times 2^{-2}+1\times 2^{-3}+\text{quelque chose}\\ \end{align*}

On soustrait une autre fois et on obtient 0.03125, qui est une puissance exacte de 2. Alors

\begin{align*} 0.40625&=0\times 2^{-1}+ 2^{-2}+ 2^{-3}+2^{-5}\\ 0.40625&=0.01101_2\text{.} \end{align*}

🔗

Sous-section 3.1.3 Représentation en base hexadécimale

La représentation binaire d’un nombre prend beaucoup plus de place que la représentation décimale. C’est un désavantage avec lequel on est prêt à vivre en informatique étant donné la simplicité d’un système à deux possibilités (ouvert-fermé, haut-bas, vrai-faux, etc.). On a dit au tout début de la section que n’importe quel nombre \(b>1\text{.}\) Si \(b>10\) est un entier, quels symboles utilise-t-on pour représenter les nombres? L’un des systèmes les plus utilisés est le système hexadécimal. Celui-ci correspond à la base seize. Pour compléter l’ensemble des chiffres, on ajoute aux symboles les six premières lettres de l’alphabet, en majuscule. Ainsi, un nombre entier exprimé en hexadécimal sera de la forme

\begin{equation*} d_{n}\times 16^n + d_{n-1}\times 16^{n-1} +\cdots + d_{_1}\times 16^1 + d_{_0}\times 16^0 \end{equation*}

avec tous les \(d_k\in \{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\}\text{.}\) Dans les calculs, on se rappellera que \(A=10,B=11,C=12,D=13,E=14\) et \(F=15\text{.}\)

🔗

Les nombres naturels de \(0\) à \(3840\) sont transformés en base seize dans la figure interactive ci-dessous.

🔗

Instructions.

Le curseur \(n\) représente le nombre en base dix. On peut voir sa conversion en représentation hexadécimale.

🔗

Figure 3.1.9. Les nombres de \(0\) à \(3840\) en base seize

🔗

Les méthodes pour convertir entre la base dix et seize sont identiques à celles pour convertir entre base dix et deux. On donne deux exemples ci-dessous. La table des premières puissances de \(16\) est donné ici pour référence.

🔗

Table 3.1.10. Puissances de 16

🔗

Puissance de seize	\(16^8\)	\(16^{7}\)	\(16^{6}\)	\(16^{5}\)	\(16^{4}\)	\(16^{3}\)	\(16^{2}\)	\(16^{1}\)	\(16^{0}\)
Valeurs décimales	\(4294967296\)	\(268435456\)	\(16777216\)	\(1048576\)	\(65536\)	\(4096\)	\(256\)	\(16\)	\(1\)

Exemple 3.1.11. Conversion entre système décimal et système hexadécimal.

On veut convertir \(A0E2F3_{16}\) en décimal et \(987654321\) en hexadécimal.

🔗

Solution 1.

La conversion d’hexadécimal vers la base dix étant plus simple, on débute par celle-ci. On a

\begin{align*} A0E2F3_{16}&=A\times 16^5+0\times 16^4+E\times 16^3+2\times 16^2+F\times 16^1+3\times 16^0\\ &=10\times 16^5+14\times 16^3+2\times 16^2+15\times 16^1+3\times 16^0\\ \end{align*}

qui après addition de toutes ces puissances donne

\begin{align*} &=10543859\text{.} \end{align*}

🔗

Solution 2.

Pour la conversion de la base décimale vers la base seize, on regarde encore quelle est la plus grande puissance de seize qui est inférieure ou égale au nombre à convertir. Pour \(987654321\text{,}\) c’est \(16^7=268435456\) qui sera utilisé. Il y a toutefois une étape supplémentaire à considérer par rapport à la conversion au binaire. Combien de fois \(16^7\) rentre-t-il dans \(987654321\text{?}\) On utilise Sage pour faire ce calcul, en notant qu’à la section suivante on aura un opérateur spécial qui donnera directement la réponse, sans tenir compte de la partie fractionnaire.

🔗

Comme on obtient \(3.67929906026\text{,}\) on déduit qu’on peut mettre trois puissances de \(16^7\text{,}\) mais pas quatre. On a donc

\begin{equation*} 987654321=3\times 16^7+\text{quelque chose}\text{.} \end{equation*}

On poursuit les calculs avec Sage. Dans un premier temps, que reste-t-il si on soustrait \(3\times 16^7\) à \(987654321\text{?}\)

🔗

La plus grande puissance de \(16\) qui est plus petite que ce nombre est \(16^6\text{.}\) En répétant la méthode ci-dessus, on calcule combien de fois cette puissance rentre dans \(182347953\text{.}\)

🔗

La puissance peut rentrer \(10\) fois, ce qui veut dire que le symbole utilisé sera \(A\text{:}\)

\begin{equation*} 987654321=3\times 16^7+A\times 16^6+\text{quelque chose d'autre}\text{.} \end{equation*}

On soustrait \(10\times 16^6\) de \(182347953\) pour obtenir le reste.

🔗

On effectue une dernière étape complète avant de donner la réponse. Le reste pourra être complété en exercice. La cinquième puissance de \(16\) sera la prochaine à être utilisée.

🔗

On peut donc mettre \(13\) fois \(16^5\) dans \(14575793\text{,}\) ce qui signifie que le symbole utilisé sera \(D\text{.}\) On aura

\begin{equation*} 987654321=3\times 16^7+A\times 16^6+D\times 16^5+\text{autre chose}\text{.} \end{equation*}

Le reste sera égal à \(944305\) , comme le montre le calcul ci-dessous.

🔗

Au final, on peut montrer que

\begin{equation*} 987654321=3ADE68B1_{16}\text{.} \end{equation*}

L’exercice 3.1.7.6 demande le reste de la démarche.

🔗

La base hexadécimale est beaucoup utilisée en informatique, car on peut passer facilement de binaire à hexadécimale ou l’inverse sans passer par l’intermédiaire de la base dix. De plus, un nombre en base seize est moins long à écrire qu’un nombre en base deux (en termes de nombre de caractère à utiliser). Pour voir comment passer de la base deux vers la base hexadécimale, on considère l’exemple suivant. On veut convertir le nombre \(110110010110_{2}\) sous forme hexadécimale. Exprimé sous forme de puissances de deux, ce nombre est

\begin{equation*} 1\cdot 2^{11}+1\cdot 2^{10}+0\cdot 2^9+1\cdot 2^8+1\cdot 2^7+0\cdot 2^6+0\cdot 2^5+1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+0\cdot 2^0\text{.} \end{equation*}

On regroupe maintenant ces termes en paquets de quatre, en effectuant une mise en évidence de la plus grande puissance de deux possible. On obtient alors

\begin{gather*} (1\cdot 2^{11}+1\cdot 2^{10}+0\cdot 2^9+1\cdot 2^8)+(1\cdot 2^7+0\cdot 2^6+0\cdot 2^5+1\cdot 2^4)+(0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+0\cdot 2^0)\\ =(1\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^1+1\cdot 2^0)2^8+(1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0)2^4+(0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+0\cdot 2^0)2^0\text{.} \end{gather*}

On peut maintenant remarquer deux choses. Dans un premier temps, on a \(2^8=(2^4)^2=16^2, 2^4=16^1\) et \(2^0=16^0\text{.}\) En regroupant comme cela, on fait ressortir des puissances de 16, justement les puissances nécessaires pour écrire en base hexadécimale. Ensuite, dans les parenthèses, il ne reste que des puissances de deux entre \(0\) et \(3\text{.}\) Avec quatre chiffres binaires, on peut obtenir n’importe quel nombre entre \(0000_2=0\) et \(1111_2=15\text{,}\) exactement le nombre de caractères utilisés dans la base hexadécimale. Le nombre peut donc se réécrire comme suit:

\begin{align} (1\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^1+1\cdot 2^0)16^2+(1\cdot 2^3+0\cdot 2^2&+0\cdot 2^1+1\cdot 2^0)16^1+(0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+0\cdot 2^0)16^0 \tag{✶}\\ &=(1101_2)16^2+(1001_2)16^1+(0110_2)16^0\notag\\ &=D\cdot 16^2+9\cdot 16^1+6\cdot 16^0\notag\\ &=D96_{16}\text{.}\notag \end{align}

🔗

On remarque que les chiffres \(\{1,0\}\) dans les parenthèses de l’équation (✶) sont les mêmes chiffres que ceux de la représentation binaire, séparés en groupe de quatre. Pourquoi quatre? Parce que tel qu’observé, en effectuant une mise en évidence pour un groupe de quatre, on obtient des puissances de seize. L’algorithme suivant décrit la procédure pour convertir un nombre binaire en hexadécimal et hexadécimal en binaire

🔗

Algorithme 3.1.12. Conversion entre binaire et hexadécimale.

Pour convertir un nombre binaire en hexadécimale, on effectue les étapes suivantes.

De droite à gauche, sépare les chiffres en groupe de quatre. Si le groupe à gauche ne contient pas quatre chiffres, on comble avec des zéros à sa gauche.
🔗

🔗
On convertit chaque groupe de quatre en une valeur de \(0\) à \(15\text{,}\) en associant \(10=A,11=B,12=C,13=D,14=E\) et \(15=F\) si nécessaire.
🔗

🔗
En juxtaposant les chiffres obtenus, on obtient la représentation en hexadécimale.
🔗

🔗

🔗

En inversant ce processus on peut aussi convertir d’hexadécimal à binaire.

Convertir chaque caractère du nombre hexadécimal en binaire, en ajoutant des zéros à la gauche au besoin pour former des groupes de quatre chiffres.
🔗

🔗
Regrouper les groupes en un seul nombre.
🔗

🔗
Supprimer les zéros complètement à gauche si nécessaire.
🔗

🔗

🔗

On montre des exemples additionnels de cette procédure dans l’exemple suivant.

🔗

Exemple 3.1.13. Des conversions entre binaire et hexadécimal.

On veut convertir les nombres \(101110_2\) et \(1001001_2\) en hexadécimal et les nombres \(1234_{16}\) et \(BEBE2020_{16}\) en binaire.

🔗

Solution 1.

On commence par convertir les nombres binaires en base seize. Pour \(101110_2\text{,}\) on forme les groupes \(0010\,1110\text{,}\) ayant pris soin d’ajouter deux zéros à la gauche du premier bloc. Ces nombres correspondent respectivement à \(2\) et \(14=E\) en hexadécimal et donc, \(101110_2=2E_{16}\text{.}\) D’une manière similaire, \(1001001_2\) se regroupe comme \(0100\,1001\text{,}\) qui se convertissent comme \(4\) et \(9\text{,}\) pour donner \(1001001_2=49_{16}\text{.}\)

🔗

Solution 2.

Pour convertir les nombres hexadécimaux en binaire, on suit la procédure établie dans l’algorithme 3.1.12. Pour \(1234_{16}\text{,}\) on obtient \(0001\,0010\,0011\,0100\text{,}\) ce qui donne en regroupant et en éliminant les zéros de gauche \(1234_{16}=1001000110100_2\text{.}\) Ensuite pour \(BEBE2020_{16}\text{,}\) on a \(1011\,1110\,1011\,1110\,0010\,0000\,0010\,0000\text{,}\) ce qui donne \(BEBE2020_{16}=10111110101111100010000000100000_2\text{.}\) On voit bien ici l’avantage du système hexadécimal pour la longueur du nombre.

🔗

Sous-section 3.1.4 Opérations élémentaires en base deux

On s’intéresse maintenant à l’arithmétique dans les autres bases. Par simplicité, on n’utilise que le binaire, mais les opérations dans les autres bases se font essentiellement de la même manière.

🔗

Pour additionner deux nombres, on apprend assez tôt de faire l’addition position par position, en appliquant la retenue lorsque la somme des chiffres d’une même colonne dépasse dix. Le principe est le même en binaire, toutefois les retenues arrivent dès que la somme est supérieure ou égale à deux. En binaire, \(1_2+1_2=10_2\text{.}\) Voici un exemple d’addition de \(110101_2\) et \(101110_2\) en base deux.

\begin{alignat*}{6} & &&\small{1}&\small{1}&\small{1}&\small{1}&\small{1}&\small{1}&&\scriptsize{(\text{retenues})}&\\ & &&&1&1&0&1&0&1_2&&\\ &+&&&1&0&1&1&1&1_2&&\\ \hline&&&1&1&0&0&1&0&0_2&& \end{alignat*}

Dans la colonne à droite de cet exemple, on effectue \(1+1\) en binaire. Le résultat donne \(10_2\text{,}\) d’où le \(0\) dans la troisième ligne et le \(1\) dans la ligne des retenues. Ensuite, on additionne cette retenue avec le \(0\) et le \(1\) de cette colonne. Ceci donne encore une fois \(1+0+1=10_2\text{,}\) entrainant une autre retenue dans la colonne à gauche. Cette fois, pour la troisième colonne, il y a deux \(1\) à additionner en plus de la retenue. Cela donne \(1+1+1=11_2\text{,}\) expliquant pourquoi dans la réponse on obtient un \(1\) ainsi que dans la retenue. On poursuit ensuite de droite à gauche jusqu’à épuisement des nombres et des retenues.

🔗

Les soustractions fonctionnent aussi de manière similaire à l’arithmétique en base dix. Au lieu d’avoir des retenues, on fait des emprunts lorsqu’on doit soustraire \(1\) à \(0\text{.}\) Dans ce cas, la soustraction \(0_2-1_2\) devient \(10_2-1_2=1_2\) après emprunt, et l’emprunt se fait vers la gauche sur le prochain chiffre non nul (on ne peut emprunter à un \(0\)). Voici un exemple de la soustraction de \(1100101_2\) et \(1001010_2\text{.}\)

\begin{alignat*}{7} & & & & &\small{0}&\small{1}&\small{1}&\small{0}&\small{1}&&\scriptsize{(\text{emprunts})}&\\ & & & &1&\bcancel{1}&0&0&{\bcancel{1}}&0&1_2&&\\ &- & & &1&0&0&1&0&1&0_2&&\\ \hline& & & &0&0&1&1&0&1&1_2&& \end{alignat*}

🔗

Dans la deuxième colonne, il a été nécessaire de faire un emprunt. On a donc remplacé le \(0\) de la première colonne par \(10_2\) et en soustrayant le \(1\text{,}\) on obtient \(10_2-1_2=1_2\text{.}\) Il a aussi fallu emprunter dans la troisième colonne. Comme la quatrième est aussi nulle, on emprunte à la cinquième, ainsi \(100_2\) devient \(011_2\) avec le dernier \(1\) considéré comme \(10_2\text{.}\) La troisième colonne devient \(10_2-1_2=1_2\text{,}\) la quatrième \(1_2-0_2=1_2\) et la cinquième \(0_2-0_2=0_2\text{.}\) Finalement, la dernière colonne est \(1_2-1_2=0_2\text{.}\) Au final on a \(1100101_2-1001010_2=11011_2\text{.}\)

🔗

On veut maintenant effectuer une multiplication de deux nombres binaires. L’algorithme utilisé pour faire une multiplication en base dix peut être repris, mais on utilise une approche différente, similaire à la manière dont les ordinateurs font les calculs. Celle-ci exploite le fait que multiplié un nombre par une puissance de deux est équivalents à ajouter un certain nombre de zéros à la fin, comme multiplié par \(10,100,1000,\) etc. en base dix. Par exemple, pour faire \(1101_2\times 100_2\) on a

\begin{align*} 1101_2\times 100_2&=(2^3+2^2+2^0)\times 2^2\\ &=2^3\times 2^2+2^2\times 2^2+2^0\times 2^2\\ &=2^5+2^4+2^2\\ &=110100_2\text{.} \end{align*}

🔗

De manière plus générale, on ajoute autant de zéros qu’il y en a dans l’écriture de la puissance de deux.Pour un produit quelconque, on va décomposer l’un des facteurs selon ses puissances de deux, distribuer sur l’autre facteur et additionner les nombres obtenus.

🔗

Exemple 3.1.14. Une multiplication binaire.

On veut effectuer le produit de \(1001_2\) par \(1010_2\) en décomposant \(1010_2\) selon ses puissances.

🔗

Solution.

Puisque \(1010_2=1000_2+0010_2\text{,}\) on aura

\begin{equation*} 1001_2\times 1010_2=1001_2\times (1000_2+10_2)=1001_2\times 1000_2+1001_2\times 10_2\text{.} \end{equation*}

On ajoute à chaque terme le bon nombre de zéros et on obtient \(1001000_2+10010_2\text{.}\) Finalement, on additionne

\begin{align*} & & 10 01000_2&\\ &+&{}{}10010_2&\\ \hline& & 10 11010_2& \end{align*}

🔗

Si on veut multiplier des nombres réels avec un nombre fini de chiffres après le point, on procède comme suit. Une puissance négative de deux équivaut à déplacer le point vers la gauche, de un chiffre par valeur de \(n\) dans \(2^{-n}\text{.}\) Ainsi, \(1101.01_2\times 0.01_2=11.0101\text{,}\) puisque \(0.01_2=2^{-2}\text{.}\) On considère un exemple plus complexe.

🔗

Exemple 3.1.15. Multiplication binaire de nombres réels.

On veut effectuer \(10011.1011_2\times 101.101_2\text{.}\)

🔗

Solution.

En suivant la méthode pour les entiers, on décompose l’un des facteurs en une somme de puissances de deux. Ici, on choisit de décomposer le deuxième facteur, puisqu’il contient moins de chiffres. On a

\begin{equation*} 101.101_2=100_2+1_2+0.1_2+0.001_2\text{.} \end{equation*}

Le produit devient

\begin{align*} 10011.1011_2\times 101.101_2&=10011.1011_2\times (100_2+1_2+0.1_2+0.001_2)\\ &=10011.1011_2\times 100_2+10011.1011_2\times 1_2+10011.1011_2\times 0.1_2+10011.1011_2\times 0.001_2.\\ \end{align*}

En déplaçant le point, on trouve

\begin{align*} \phantom{10011.1011_2\times 101.101_2}&=1001110.11_2+10011.1011_2+1001.11011_2+10.0111011_2\\ \phantom{10011.1011_2\times 101.101_2}&=1101110.1011111 \end{align*}

🔗

Finalement, la division en binaire s’effectue aussi comme la division en base dix, en cherchant combien de fois on peut mettre ce par quoi on divise dans le nombre divisé. Une fois que suffisamment de chiffres du dividende (le nombre qui est divisé) ont été considérés pour que le diviseur puisse être soustrait au moins une fois, on utilise les autres chiffres du dividende de droite à gauche en abaissant un à un après la soustraction. Un exemple est illustré ci-dessous.

🔗

	\(7(\cancel{4}5)\)	\(3\)
\(-\)	\(6\)	\(2\)
	\(14 (\cancel{5})\)	\(\downarrow\)
\(-\)	\(12\)	\(24\)
	\(25\)	\(\downarrow\)
\(-\)	\(24\)	\(248\)
	\(1\)

Pour la division binaire, les chiffres du quotient (la réponse) ne peuvent être que \(1\) ou \(0\text{.}\) On revoit la même division que ci-dessous, mais en binaire, soit \(1011101001_2 \div 11_2\text{.}\)

	\(101(\cancel{1}101001)_2\)	\(11_2\)
\(-\)	\(\phantom{1}11_2\)	\(1_2\)
	\(101(\cancel{1}01001)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}11_2\)	\(11_2\)
	\(101(\cancel{0}1001)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}11_2\)	\(111_2\)
	\(100(\cancel{1}001)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}11_2\)	\(1111_2\)
	\(11(\cancel{0}01)_2\)	\(\downarrow\)
\(-\)	\(11_2\)	\(11111_2\)
	\(00(\cancel{0}1)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}0_2\)	\(111110_2\)
	\(00(\cancel{1})_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}0_2\)	\(1111100_2\)
	\(01_2\)	\(\downarrow\)
\(-\)	\(\phantom{0}0\)	\(11111000_2\)
reste	\(1_2\)

🔗

On pourra vérifier que \(11111000_2=248\) et bien sûr, \(1_2=1\text{.}\) On considère un autre exemple.

🔗

Exemple 3.1.16. Division en binaire.

On souhaite effectuer la division de \(218\) par \(22\) en binaire.

🔗

Solution.

On commence par convertir les nombres en binaire. Pour \(218\text{,}\) on obtient \(11011010_2=218\) et pour \(22\text{,}\) c’est \(10110_2=22\text{.}\) Le résultat de la division est donnée ci-dessous.

🔗

	\(11011(\cancel{0}10)_2\)	\(10110_2\)
\(-\)	\(10110_2\)	\(1_2\)
	\(001010(\cancel{1}0)_2\)	\(\downarrow\)
\(-\)	\(0_2\)	\(10_2\)
	\(10101(\cancel{0})_2\)	\(\downarrow\)
\(-\)	\(0_2\)	\(100_2\)
	\(101010_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}10110_2\)	\(1001_2\)
reste	\(10100_2\)

🔗

La division de réels est bien sûr possible, mais on se restreint à la division de nombres naturels.

🔗

Sous-section 3.1.5 (Section supplémentaire) Représentation en circuits d’opérations binaires

À l’exercice 2.4.3.5, on définit un circuit à deux entrées et deux sorties. Ce circuit est appelé un demi-additionneur. Étant donné deux entrées binaires, il retourne leur somme comme un nombre à deux chiffres, la puissance de \(2^0\) comme somme \(S\) et la puissance de \(2^1\) comme retenue \(R\text{.}\) Ainsi, \(0_2+1_2=1_2\) sera retournée comme \(S=1\) et \(R=0\text{,}\) alors que \(1_2+1_2=10_2\) sera retournée comme \(S=0\) et \(R=1\text{.}\)

🔗

On peut maintenant considérer l’addition binaire générale. Une addition se fait colonne par colonne. La somme d’une colonne est obtenue en faisant la somme des chiffres des nombres à additionner plus la retenue de la colonne précédente, le cas échéant. On va maintenant construire le circuit effectuant cette opération. Dans ce circuit, on note \(A\) le chiffre du premier terme de l’addition, \(B\) le second, \(P\) la retenue de la colonne précédente, \(S\) la somme de la colonne et \(R\) la nouvelle retenue. La figure 3.1.17 illustre l’additionneur.

🔗

Un circuit à trois entrées et deux sorties est illustré. Les entrées A et B se combinent dans une porte XOR et dans une porte ET. Le résultat de la porte XOR se combine dans une autre porte XOR avec l’entrée P pour donner la sortie S. Puis la première porte XOR se combine encore avec P, mais cette fois-ci dans une porte ET. Le résultat des deux portes ET se combinent dans une porte OU pour produire la sortie R. — Figure 3.1.17. Un circuit additionneur
🔗

On peut comprendre le circuit en considérant la table de vérité de l’opération \(A+B+P\) et en utilisant une forme normale. La table est donnée ci-dessous

🔗

Table 3.1.18. L’addition de deux chiffres et une retenue en binaire

🔗

\(A\)	\(B\)	\(P\)	\(S\)	\(R\)
\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(0\)	\(0\)	\(1\)	\(1\)	\(0\)
\(0\)	\(1\)	\(0\)	\(1\)	\(0\)
\(0\)	\(1\)	\(1\)	\(0\)	\(1\)
\(1\)	\(0\)	\(0\)	\(1\)	\(0\)
\(1\)	\(0\)	\(1\)	\(0\)	\(1\)
\(1\)	\(1\)	\(0\)	\(0\)	\(1\)
\(1\)	\(1\)	\(1\)	\(1\)	\(1\)

On regarde l’expression pour \(S\) à l’aide de la forme normale disjonctive. La sortie \(S\) sera égale à \(1\) si \((\neg A\wedge \neg B\wedge P)\vee (\neg A \wedge B \wedge\neg P)\vee (A\wedge\neg B\wedge \neg P)\vee (A\wedge B\wedge P)\text{.}\) On peut ensuite utiliser les règles de la logique pour simplifier un peu l’expression.

\begin{align*} S&\equiv(\neg A\wedge \neg B\wedge P)\vee (\neg A \wedge B \wedge\neg P)\vee (A\wedge\neg B\wedge \neg P)\vee (A\wedge B\wedge P)&&\\ &\equiv (\neg A \wedge B \wedge\neg P)\vee (A\wedge\neg B\wedge \neg P)\vee (A\wedge B\wedge P)\vee(\neg A\wedge \neg B\wedge P)&&\text{commutativité de la disjonction}\\ &\equiv((\neg A \wedge B \wedge\neg P)\vee (A\wedge\neg B\wedge \neg P))\vee ((A\wedge B\wedge P)\vee(\neg A\wedge \neg B\wedge P)&&\text{associativité de la disjonction}\\ &\equiv(((\neg A\wedge B)\vee(A\wedge \neg B))\wedge \neg P)\vee(((\neg A\wedge \neg B)\vee(A\wedge B))\wedge P)&&\text{distributivité de la conjonction sur la disjonction}\\ &\equiv((A\oplus B)\wedge \neg P)\vee ((\neg A\oplus B)\wedge P)&& \text{définition du ou exclusif}\\ &\equiv((A\oplus B)\wedge \neg P)\vee (\neg( A\oplus B)\wedge P)&&\text{voir l'exercice }\knowl{./knowl/xref/exo-negationxor.html}{\text{2.2.4.4}}\\ &\equiv(A\oplus B)\oplus P &&\text{définition du ou exclusif}\text{.} \end{align*}

L’exercice 3.1.7.13 permettra de montrer que \(R\equiv ((A\oplus B)\wedge P)\vee (A\wedge B)\text{.}\)

🔗

On observe dans le circuit de l’additionneur la présence de deux circuits demi-additionneurs, illustrés par les boites dans le circuit équivalent de la figure 3.1.19.

🔗

Un circuit à trois entrées et deux sorties est illustré. Les entrées A et B se combinent dans un circuit demi-additionneur. La sortie S de ce circuit se combine dans un autre circuit demi-additionneur avec l’entrée P. La sortie S de ce second demi-additionneur produit la sortie S globale du circuit. Puis, les sorties R des deux demi-additionneurs se combinent pour produire la sortie globale R du circuit. — Figure 3.1.19. Un circuit additionneur réduit grâce aux circuits demi-additonneurs
🔗

Maintenant, à partir de plusieurs combinaisons de circuits additionneurs, on peut illustrer comment faire l’addition de deux nombres binaires. La quantité de circuits additionneurs à utiliser dépend du nombre de chiffres utilisés pour représenter les nombres. Dans la figure 3.1.20, on illustre un circuit permettant de faire l’addition de nombres binaires écrits avec quatre chiffres. La sortie d’un tel système sera un nombre à cinq chiffres, avec potentiellement le premier de ces chiffres égal à zéro. Pour faire \(A+B=S\text{,}\) on suppose que \(A=(A_3A_2A_1A_0)_2\text{,}\) \(B=(B_3B_2B_1B_0)_2\) et \(S=(S_4S_3S_2S_1S_0)_2\text{.}\) Le circuit additionne, de haut en bas, les chiffres de droite à gauche de \(A\) et \(B\text{.}\)

🔗

Un circuit à huit entrées et cinq sorties est illustré. Les entrées A0 et B0 se combinent dans un circuit demi-additionneur. La sortie S de ce circuit produit la sortie S0 puis la sortie R se combine avec les entrées A1 et B1 dans un additionneur. La sortie S de cette additionneur produit S1 et la sortie R se combine avec A2 et B2 dans un autre additionneur. On continue ainsi de suite jusqu’au dernier additionneur, qui produit S3 par sa sortie S et S4 par sa sortie R. — Figure 3.1.20. Un circuit additionneur pour des nombres binaires à quatre chiffres
🔗

🔗

Les points importants de cette section sont:

Le principe d’un système positionnel, où chaque chiffre représente un multiple d’une puissance de la base.
🔗

🔗
La conversion d’un nombre en binaire en un nombre en base dix.
🔗

🔗
La conversion d’un nombre en base dix en un nombre en binaire.
🔗

🔗
La conversion d’un nombre en hexadécimal en un nombre en base dix.
🔗

🔗
La conversion d’un nombre en base dix en un nombre en hexadécimal.
🔗

🔗
La conversion directe entre binaire et hexadécimal.
🔗

🔗
Les opérations d’addition, soustraction, multiplication et division en base deux.
🔗

🔗

🔗

Exercices 3.1.7 Exercices

Réponse.

\(A_2\cap A_0 =\{5,7,13,15\}\)

🔗

Solution.

Par définition, on a que \(A_2=\{4,5,6,7,12,13,14,15\}\text{,}\) alors que \(A_0=\{1,3,5,7,8,9,11,13,15\}\text{.}\) Ainsi, \(A_2\cap A_0 =\{5,7,13,15\}\)

🔗

(e)

Énumérer les éléments dans \(A_3\cap A_1\text{.}\)

🔗

Réponse.

\(A_3\cap A_1 =\{10,11,14,15\}\)

🔗

Solution.

\(111_2\times 111_2\)

🔗

Réponse.

\(111_2\times 111_2=110001_2\)

🔗

Solution.

\begin{align*} 111_2\times 111_2&=(111)_2\times (100_2+10_2+1_2)\\ &=111_2\times 100_2+111_2\times 10_2+111_2\times 1_2\\ &=11100_2+1110_2+111_2 \end{align*}

🔗

On effectue alors l’addition

\(1101001_2\div 11_2 = 100011_2\)

🔗

Solution.

	\(\phantom{1}11(\cancel{0}1001)_2\)	\(\phantom{1}11_2\)
\(-\)	\(11_2\)	\(1_2\)
	\(0(\cancel{1}001)_2\)	\(\downarrow\)
\(-\)	\(0_2\)	\(10_2\)
	\(01(\cancel{0}01)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}0_2\)	\(100_2\)
	\(10(\cancel{0}1)_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}0_2\)	\(1000_2\)
	\(100(\cancel{1})_2\)	\(\downarrow\)
\(-\)	\(\phantom{1}11_2\)	\(10001_2\)
	\(11_2\)	\(\downarrow\)
\(-\)	\(11_2\)	\(100011_2\)
reste	\(0_2\)

🔗

(b)

\(1011101_2\div 110_2\)

🔗

Réponse.

\(1011101_2\div 110_2 = 1111_2\text{ avec reste de }11_2\)

🔗

(c)

\(110001_2\div 1111_2\)

🔗

Réponse.

\(110001_2\div 1111_2=11_2 \text{ avec reste de } 100_2\)

🔗

(d)

\(101110111_2\div 11011_2\)

🔗

Réponse.

Que peut-on dire du résultat de la soustraction d’un nombre à une puissance de deux supérieure?

🔗

Réponse.

Le résultat de la soustraction est obtenu de la manière suivante:

À partir de la droite, on garde les premiers zéros et le premier un.
🔗

🔗
Tous les autres chiffres sont inversés. Les zéros deviennent des uns et les uns deviennent des zéros.
🔗

🔗

🔗

Exercices supplémentaires

13.

Montrer en utilisant une table de vérité et la forme normale disjonctive que la retenue d’un additionneur s’écrit comme \(R\equiv ((A\oplus B)\wedge P)\vee (A\wedge B)\text{.}\)

🔗

Solution.

À l’aide de la table de vérité, on trouve la forme normale disjonctive de:

\begin{equation*} R\equiv (\neg A \wedge B\wedge P)\vee( A \wedge \neg B\wedge P)\vee(A \wedge B\wedge \neg P)\vee(A \wedge B\wedge P) \text{.} \end{equation*}

À l’aide des propriétés, on obtient

🔗

\begin{align*} R&\equiv (\neg A \wedge B\wedge P)\vee( A \wedge \neg B\wedge P)\vee(A \wedge B\wedge \neg P)\vee(A \wedge B\wedge P)&&\\ &\equiv (((\neg A \wedge B)\vee(A \wedge \neg B)) \wedge P )\vee(A \wedge B\wedge \neg P)\vee(A \wedge B\wedge P)&&\text{distributivité de la conjonction sur la disjonction}\\ &\equiv(((\neg A \wedge B)\vee(A \wedge \neg B)) \wedge P )\vee ((A\wedge B)\wedge(\neg P \vee P))&&\text{distributivité de la conjonction sur la disjonction}\\ &\equiv (((\neg A \wedge B)\vee(A \wedge \neg B)) \wedge P )\vee ((A\wedge B)\wedge(V))&&\text{propriété de la négation}\\ &\equiv (((\neg A \wedge B)\vee(A \wedge \neg B)) \wedge P )\vee (A\wedge B)&&\text{propriété d'identité}\\ &\equiv((A\oplus B)\wedge P)\vee (A\wedge B)&& \text{définition du ou exclusif} \end{align*}

🔗

14. La complémentation à \(2\).

On a vu dans le texte, faire une soustraction est une opération difficile comparativement à faire une addition. L’exercice 3.1.7.12 laisse entrevoir une manière différente de faire les soustractions. C’est d’ailleurs avec cette méthode (un peu modifiée) qu’un ordinateur effectue les soustractions. La méthode est basée sur l’observation suivante:

\begin{align*} A-B&=A-B+2^n-2^n\\ &=A+(2^n-B)-2^n\text{.} \end{align*}

🔗

Pour soustraire \(B\) à \(A\text{,}\) on lui additionne plutôt le complément à \(2\) de \(B\) selon la puissance \(n\text{.}\) On décortique la méthode ci-dessous.

🔗

(a)

Le complément à \(2\) selon la puissance \(n\) d’un nombre binaire \(B\) est le nombre obtenu en faisant la soustraction \(2^n_{10}-B_{10}\text{.}\) Grâce à l’exercice 3.1.7.12, on peut observer ceci. Le complément par rapport à une puissance \(n\) est obtenu en écrivant le nombre avec \(n\) chiffres, ajoutant au besoin des zéros à gauche. Par la suite:

À partir de la droite, on garde les premiers zéros et le premier un.
🔗

🔗
Tous les autres chiffres sont inversés. Les zéros deviennent des uns et les uns deviennent des zéros.
🔗

🔗

🔗

Par exemple, le complément de \(1010_2\) par rapport à la puissance \(n=4\) est

\begin{equation*} (1010_2)^{c}=(0110_2)\text{.} \end{equation*}

Calculer \(11001_2-10100_2\) en utilisant l’observation ci-dessus.

🔗

Solution.

\begin{equation*} 11001_2 + (10100_2)^c = 1 1001_2+0 1100_2= 10 0101_2\text{.} \end{equation*}

\(1\)

\begin{equation*} 11001_2-10100_2=00101_2 \end{equation*}

🔗

(iii)

Lorsque \(A<B\text{,}\) l’algorithme de soustraction ne fonctionne pas. On a alors deux options. La première consiste à faire \(B-A\) à la place et de mettre un signe négatif devant la réponse, puisque \(A-B=-(B-A)\text{.}\) L’autre option utilise un argument similaire pour montrer que

\begin{equation*} A-B=A+B^c-2^n=-(2^n-(A+B^c))\text{.} \end{equation*}

Le membre de droite de l’équation précédente n’est rien d’autre que le complément de \(A+B^c\text{.}\) On a donc

\begin{equation*} A-B=-(A+B^c)^c\text{.} \end{equation*}

🔗

(iv)

Utiliser la première méthode pour calculer \(1011_2-10101_2\text{.}\)

🔗

(v)

Utiliser la seconde méthode pour calculer \(111_2-10111_2\text{.}\)

🔗

15.

On désire construire un circuit qui va permettre de déterminer si deux nombres \(A,B\) écrits en binaire sont égaux. L’idée est de comparer chiffre par chiffre, l’égalité étant vérifiée si tous les chiffres à la même position sont égaux.

🔗

(a)

Quelle porte permet de vérifier si deux entrées ont la même valeur?

🔗

Indice.

🔗

(b)

Vérifier que le circuit correspond à l’expression \((A_1\wedge \neg B_1)\vee ((A_1=B_1)\wedge(A_0\wedge \neg B_0))\text{,}\) où l’expression \(A_1=B_1\) vaut \(1\) si les deux entrées ont la même valeur et \(0\) sinon.

🔗

(c)

En utilisant une boite générique pour illustrer le circuit d’égalité de l’exercice 3.1.7.15, illustrer un circuit permettant de généraliser celui de la figure 3.1.21 pour des nombres à \(\text{}\) chiffres.

🔗

Précédent Top Suivant