Les calculs en binaire

Introduction du cours

Vous avez toujours rêvé d'additionner des nombres en binaire ? Alors ce tutoriel est fait pour vous ! ^^

En effet, vous allez apprendre ici à effectuer manuellement des opérations mathématiques avec des nombres binaires.

Avant de commencer il peut être utile (mais pas obligatoire) de savoir convertir un nombre décimal en binaire et inversement.
Pour cela, n'hésitez pas à vous reporter au tutoriel de Dentuk.

Ce cours n'est pas indispensable pour programmer avec un langage comme le C ou le Java mais si un jour vous comptez utiliser des micro-contrôleurs ou simplement réaliser une application en assembleur, ces connaissances pourront vous être utiles.

Attention, un QCM vous attend à la fin !

Écrire un nombre négatifPréparatifs

Avant de commencer, sachez que tous les exemples que je donnerai par la suite seront faits avec des char car je suis une feignasse et écrire un int en binaire est trop long. Cependant, ce que vous allez apprendre ici fonctionne avec tous les types de variables gérant des entiers (char, long, int) mais pas avec les variables acceptant aussi les nombres à virgule (float, double).
En effet, ces derniers ne sont pas codés de la même manière :

- Les variables pour les entiers sont codées en binaire en utilisant tous les bits pour donner la « valeur » du nombre.

Plan de Char

Ainsi un char qui est (en théorie) codé sur 8 bits pourra avoir 256 (28) valeurs différentes.

Ah ! Un détail (important) : si le char est employé en tant que « unsigned » (variable toujours positive), le bit 7 sert à donner la valeur du nombre mais si on l'utilise en tant que « signed », ce bit sert à donner le signe du nombre (0 signifie positif, 1 signifie négatif).
Ainsi 1000 1111 est égal à 143 si la variable est non-signée et à -113 dans le cas contraire (si vous lisez la fin de cette partie, vous comprendrez comment je fais pour « deviner » ça

:)

:)

).

- Par opposition, les variables gérant les nombres à virgule utilisent une partie des bits pour donner la « valeur » du nombre et le reste pour donner la position de la virgule.

Par exemple, pour un nombre codé sur 32 bits (float) :

Plan de nombre à virgule

Les bits 0 à 22 servent à coder le nombre sans tenir compte de la virgule (3616.999 s'écrit donc 3616999).
Les bits 23 à 30 servent à donner l'exposant (la position de la virgule, quoi

;)

;)

).
Le bit 31 sert à préciser le signe.

Si vous êtes curieux et que vous voulez en savoir plus : RTFM.

:p

:p

Enfin, il faut savoir que ce tutoriel utilise deux notations pour indiquer les bases et les opérations.

• La base d'un nombre est indiquée entre parenthèses et en indice, cela permet d'éviter toute confusion. Ainsi, 11(10) est le nombre 11 en décimal et 11(2) est le nombre 11 en binaire.

• Les signes opératoires sont les symboles que l'on trouve sur le pavé numérique du clavier. Ce sont le plus (+) pour l'addition, le moins (-) pour la soustraction, l'astérisque (*) pour la multiplication et la barre oblique (/) pour la division. Cependant, avec l'utilisation de la balise math, le signe multiplicatif est la croix traditionnelle.

  <math>3_{(10)} \times 6_{(10)} = 18_{(10)}</math>

Exemple : $2_{(10)} \times 3_{(10)} / 6_{(10)} = 1_{(10)}$

Écrire -1, c'est possible !

Bien... Et si nous commencions le cours ?

Si vous avez lu le tutoriel de Dentuk sur la conversion décimal/binaire, vous devez savoir que 1 s'écrit 0000 0001.

Mais savez-vous écrire -1 ?

Pour le savoir, on a deux méthodes : une simple que vous allez aimer et une plus compliquée que vous utiliserez.

Voici la méthode simple.
On sait que $0 - 1 = -1$ donc :

Soustraction de 1 par 0

Si ce n'est pas clair pour vous, vous pouvez imaginer que $0000 0000 = 1 0000 0000$ mais que le 1 « dépasse » de la variable donc qu'on ne l'écrit pas.
Parbleu ! Mais alors, -1 s?écrit de la même manière que 255 ?!
Eh oui, c'est pour cela qu'il faut bien comprendre la différence entre les nombres signés et les autres.

Ainsi :

Soustraction de 1 par -1

L'opération effectuée est : $-1 - 1 = -2$ d'où $-2_{(2)} = 254_{(2)}$

Si vous êtes perdu, passez à la partie suivante qui parle des additions et soustractions, cela sera peut-être plus clair après.

Ça va, vous suivez ?

J'espère que oui, car voici la méthode plus compliquée !

Attends ! Pourquoi utiliserait-on une technique plus dure si on connaît celle-ci ? On ne va pas se compliquer la vie pour rien !

Excellente question ! Eh bien tout simplement parce que la méthode plus compliquée permet de travailler aussi bien sur des petits nombres que sur des grands. Non pas que cette méthode ne puisse pas, mais essayez de trouver l'équivalent binaire de -19 de tête :

Soustraction impossible de 19 par 0

Personnellement, j'ai un peu de mal.

La méthode compliquée (aussi appelée complément à deux) :

1. Tout d'abord, vérifiez que le nombre à convertir en binaire est négatif. Si le nombre est positif, pas de souci, vous savez normalement le faire.

2. Si le nombre est négatif (par exemple -19) :

   • On convertit sa valeur absolue en binaire. Dans notre cas, on écrit donc 19 en binaire : $19_{(10)} = 0001 0011_{(2)}$.

   • On inverse tous les bits du nombre : les 0 deviennent des 1 et inversement. $0001 0011_{(2)}$ devient $1110 1100_{(2)}$.

   • On ajoute 1 au résultat précédent :

     Ajout de 1 à l'inversion des bits du nombre

   • $-19_{(10)} = 1110 1101_{(2)}$. Voilà ! C'était pas trop dur, avouez ! C'est juste un peu plus long.

Petit détail

Voici un tableau représentant l'équivalent décimal de la valeur des variables « signées » de type char.

Calcul 5

Comme les nombres négatifs ont toujours un 1 comme bit de poids fort, ils sont représentés au-dessus des nombres positifs dans ce tableau.

Vous constaterez ici que le 0 est considéré comme un nombre positif, donc que ces derniers ne vont que jusqu'à 127 tandis que les négatifs atteignent -128.

Une autre particularité due à cette façon de coder les nombres négatifs est que si une variable atteint le maximum 127 pour un char et qu'elle est incrémentée, elle passera directement à -128, alors que la même chose pour une variable « unsigned » la fait repartir à 0.

Essayez, vous verrez :

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { char k = 0; do { printf("%ld\n", k); k++; //J'incrémente ma variable. } while(k>=0); printf("%ld\n", k); //Tadam ! return 0; }

Bien entendu, ce problème peut aussi se retrouver dans les calculs si le résultat dépasse la valeur maximale permise par la variable, faites donc attention !

Addition et soustraction

Passons maintenant aux calculs !

Ne vous en faites pas, on ne va faire que des choses simples, déjà parce que je suis une bille en mathématiques et ensuite parce que les processeurs ne valent pas mieux. (C'est dit sans méchanceté, hein !) ;)
Ainsi, les seuls calculs que l'on va aborder seront l'addition, la soustraction, la multiplication et... la division !

Les additions

Commençons en douceur avec l'addition, que vous avez déjà employée si vous avez fait des essais dans la partie précédente.

Table de vérité

On va commencer par définir ce qui s'appelle une « table de vérité ».
Cette table de vérité est une liste des différents résultats qu'un calcul utilisant un certain opérateur peut donner :

Calcul décimal

Résultat décimal

Calcul binaire

Résultat binaire

$0 + 0$

$0$

$0000 + 0000$

$0000$

$0 + 1$

$1$

$0000 + 0001$

$0001$

$1 + 0$

$1$

$0001 + 0000$

$0001$

$1 + 1$

$2$

$0001 + 0001$

$0010$

Un petit rappel :

Lorsque vous faites ce calcul, vous savez que 9 plus 4 font 13. Vous mettez donc 3 en bas à droite et vous gardez quoi ? Eh oui, une retenue. ;) La retenue (ici, 1) s'ajoute au chiffre d'après.
En binaire, c'est la même chose :

Je vous rappelle qu'en binaire il n'y a que deux chiffres. La retenue arrive donc très souvent, il faut pouvoir s'en sortir avec.

Exemple

On va faire un exemple : $6 + 14 = 20$.

En binaire :

$6_{(10)} = 110_{(2)}$$14_{(10)} = 1110_{(2)}$

Bit n° 0 : $0 + 0 = 0$

On commence facile. ;)

Bit n° 1 : on tombe sur un cas de retenue. $1_{(2)} + 1_{(2)} = 10_{(2)}$ donc on met le $0$ dans le résultat et on garde le 1 en retenue. Ce qui donne donc :

Bit n° 2 : le calcul est $1_{(2)} + 1_{(2)}$ mais attention, il ne faut pas oublier la retenue du calcul précédent ! Le résultat donne en réalité $1_{(2)} + 1_{(2)} + 1_{(2)} = 11_{(2)} = 3_{(10)}$. On met donc $1$ dans le résultat et on garde une nouvelle retenue de 1.

Bit n° 3 : le calcul aurait dû être $0 + 1$ mais n'oubliez pas la retenue ! Eh oui ! Le calcul exact est donc $1_{(2)} + 1_{(2)} = 10_{(2)}$ ; on met donc 0 au résultat et 1 en retenue. Et comme il n'y a plus rien après, la retenue tombe toute seule au résultat. ;)

Eh voilà ! Vous pouvez vérifier que $20_{(10)} = 10100_{(2)}$.

Voilà, les additions sont finies. Ce n'était pas si dur, n'est-ce pas ? ;)

Les soustractionsTable de vérité

Voyons d'abord la table de vérité :

Calcul décimal

Résultat décimal

Calcul binaire

Résultat binaire

$0 - 0$

$0$

$0000 - 0000$

$0000$

$0 - 1$

$-1$

$0000 - 0001$

$1111$

$1 - 0$

$1$

$0001 - 0000$

$0001$

$1 - 1$

$0$

$0001 - 0001$

$0000$

La deuxième ligne est un peu particulière. Je l'explique : quand vous tombez sur un chiffre qui doit se faire soustraire par un plus grand que...