Arithmétique des entiers

Addition binaire

L’addition binaire est l’opération la plus simple à réaliser. Elle se réalise par calcul écrit de la même manière que dans le système décimal. Le report se fait uniquement dans le cas 1+1.


¹1
+
1

10

Exemple : 10011101 + 100110 :



¹¹¹¹



+10011101157_{10}

0010011038_{10}

11000011195_{10}

Dans un ordinateur, les additions se font via un additionneur (ou addeur). Les additionneurs sont des éléments essentiels de l’UAL (Unité Arithmétique et Logique).

Comme les reports sont pris en compte, il y a des risques de dépassement de valeurs. Par exemple, en travaillant sur un nibble

¹¹¹¹

+110113_{10}

00113_{10}

00000_{10}

Puisque nous sommes limités à 4 bits, le report excédentaire est abandonné. Il y a une erreur de dépassement de valeur.

Soustraction binaire

La soustraction est un peu plus complexe. Comment faire comprendre à l’ordinateur qu’on veut retirer un nombre d’un autre ? Son UAL ne comporte que des additionneurs…

Or, en arithmétique, nous savons que faire 7-3 revient à faire 7+ (-3). On additionne un nombre négatif. Il ne nous reste plus qu’à savoir comment écrire ces nombres négatifs.

Le complément à 1

Le complément à 1 va permettre d’ajouter un signe dans un nombre. En binaire, il n’y a pas de notion de signe, puisque toutes les opérations sont en réalité des dérivés de l’addition. Pour arriver à faire une soustraction en binaire, il va falloir utiliser une convention.

Le signe ‘-‘ sera indiqué par un 1 sur le bit de poids le plus fort (le plus à gauche). Le signe ‘+’ sera donc logiquement indiqué par un 0. Attention, si par convention nous attribuons au MSB le signe, ce bit n’est plus utilisé pour signifier la valeur du nombre!

Une des solutions pour obtenir un nombre négatif, c’est d’utiliser le complément à 1.

Le complément à 1 s’obtient en inversant bit à bit les chiffres. Tous les 1 deviennent des 0 et inversement.

Prenons un octet (8 bits). Si le nombre est positif, le MSB (bit de poids fort) sera à 0. +23 sera codé 0001 0111. -23 sera codé en inversant bit à bit : 1110 1000.

Dans la même optique, le complément à 1 du nombre 0000 000 sera : 1111 1111. Vérifions : si on additionne un chiffre avec son complément à 1, nous devrions obtenir +0 (0000 0000) ou -0 (1111 1111).


0001011123_{10}
+11101000-23_{10} ?

111111110_{10}

Dans le cas d’une addition avec reports, le dernier report (à gauche) sera perdu. Prenons l’exemple suivant :

¹¹¹¹






0001101026_{10}
+11101101-18_{10} ?

000001117_{10}

Le report est perdu. Remarquez que le complément à 1 n’est pas une méthode fiable ! En effet, la somme d’un nombre avec un nombre complémenté à 1 peut parfois générer une erreur. Ici, 26-18 doit donner 8, alors que la soustraction binaire donne 7 !

Le complément à 1 n’est fiable que si le résultat est une valeur négative. Si le résultat est positif, il convient d’ajouter 1 au résultat.

Cette méthode possède avantage et inconvénient. L’avantage, c’est d’avoir des nombres signés. Les inconvénients, on restreint la plage de nombres, on possède le +0 et le -0 et il faut parfois ajouter 1 pour obtenir le résultat réel.

Sur un octet non signé, la valeur maximale est de 28 = valeurs différentes. Sur un octet signé, la plage maximale va de -127 à + 127, avec le +0 et le -0.

Pour éviter ces inconvénients, la méthode du complément à 2 a été développée.

Par convention, on notera  \overline{N} le complément d’un nombre N.

Le complément à 2

Le complément à 2 est la seule méthode correcte mathématiquement. Elle consiste à prendre le complément à 1 d’un nombre, et de l’incrémenter de 1. . Comme pour le complément à 1, la notation du signe se fait sur des longueurs données. On perd donc le MSB, mais on ne possède plus la double valeur 0. Par exemple, sur un octet, la plage va de -128 à +127.

Le complément à 2 s’obtient en deux étapes :

  • On prend le complément à 1 d’un nombre : 0000 1100 (+12) devient 1111 0011 ;
  • On ajoute 1 au complément à 1 : 1111 0100 (-12).
Pour noter un nombre en complément à 2 directement, retenez ce truc : repérez le premier bit à 1 le plus à droite possible. Les bits à sa gauche seront inversés, les bits restants sont inchangés. Par exemple : 0001 1010 → 1110 0110.

Exemple :


0001001018_{10}







¹



11101101-18_{10}cà1
+000000011_{10}

11101110-18_{10}cà2

Soustraction binaire

Revenons à la soustraction. La soustraction binaire se fait en additionnant un nombre avec un nombre complémenté à 2. Les éventuels reports seront abandonnés.

Exemple :

¹¹¹¹¹¹¹



0001101026_{10}
+11101000-18_{10}

000010008_{10}

Exemple :





¹¹¹



10101110-82_{10}
+0100101175_{10}

11111001-7_{10}

Dans cet exemple, le nombre 1111 1001 (-7) est bien le complément à 2 de 0000 0111 (+7).

Multiplication binaire

Souvenez-vous de la multiplication écrite en décimale. Par exemple, 39*47 :



39
×
47

273
156
1833

La multiplication se divise en une somme de résultats partiels. Les addeurs de l’UAL peuvent donc faire des multiplications ! En binaire, les principes arithmétiques de la multiplication restent d’application : le 0 est absorbant et le 1 est neutre.

Multiplier en binaire revient à faire une série d’additions du multiplicande (le premier facteur) par rapport à chaque bit du multiplicateur.

Exemple :







0010011139_{10}
×




0010111147_{10}




¹¹¹¹¹¹¹¹¹¹¹¹¹¹








00100111





00100111





00100111





00100111





00100111





00100111






00111001010011833_{10}

La procédure est simple : comme pour la multiplication décimale, on commence de la droite. Si le dernier bit du multiplicateur est 1, alors on recopie le multiplicande. Sinon, on ne met rien. Ensuite, on se décale d’un bit vers la gauche et on recommence.

Une fois tous les bits traités, on additionne le tout. Les retenues sont prises en compte.

Attention ! Comme pour l’addition, il y a des risques de dépassement de valeurs !

Exemple (valeurs signées)







0010011139_{10}
×




0010111147_{10}




¹¹¹¹¹¹¹¹¹¹¹¹¹¹








00100111





00100111





00100111





00100111





00100111





00100111






001110010100141_{10} !!

Division binaire

Dernière étape : la division. Pour le moment, concentrons-nous sur les divisions euclidiennes (quotient + reste).

La division booléenne est la plus grande consommatrice de ressources. En effet, la division consiste à compter le nombre de fois où on va soustraire le diviseur du dividende.

Exemple : 119 ÷19

Le mode opératoire est le suivant :

  1. Conversion en binaire du diviseur et du dividende.
  2. Calculer le Cà2 du diviseur.
  3. Poser le quotient à 0.
  4. Soustraire le diviseur du dividende.
  5. Ajouter un tour au quotient final.
  6. Répéter les deux dernières opérations jusqu’à ce que le dividende soit inférieur au diviseur.

119: 01110111

19 : 00010011

-19 : 11101101


01110111000100110
+11101101







1

01100100








+11101101







10

01010001








+11101101







11

00111110








+11101101







100

00101011








+11101101







101

00011000








+11101101







110

00000101







110

119÷19=6 reste 5

Vous aurez remarqué que les quatre opérations mathématiques de base se réduisent en binaire à une simple addition. La construction de l’UAL en est aussi simplifiée. Un additionneur suffit, ainsi qu’un mécanisme calculant le Cà2.
Print Friendly, PDF & Email