Section courante

A propos

Section administrative du site

Addition binaire

L'addition binaire repose exactement sur le même principe qu'une addition en base décimale. La seule différence réside dans le fait que le système binaire ne possède que deux chiffres, soit 0 et 1, alors que le système décimal en possède dix (0 à 9). Comme pour une addition traditionnelle, les calculs sont effectués colonne par colonne, en partant du bit de poids faible vers le bit de poids fort. Lorsqu'une colonne dépasse la valeur maximale pouvant être représentée sur un seul bit, une retenue est générée et est ajoutée à la colonne suivante. Ce mécanisme est identique à celui utilisé lorsque l'on additionne des nombres décimaux, mais la retenue apparaît beaucoup plus fréquemment puisque la valeur maximale d'un bit est seulement égale à 1.

À partir de ce principe, il est possible de définir les quatre règles fondamentales de l'addition binaire :

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, retenue 1 (depuis 1 + 1 = 2 = 0 + (1 x 21) )

La dernière règle mérite une attention particulière. En effet, 1 + 1 produit la valeur décimale 2, laquelle s'écrit 10 en binaire. Le chiffre 0 est conservé dans la colonne courante tandis que le 1 est reporté sous forme de retenue dans la colonne suivante. Cette situation est directement comparable à l'addition décimale 9 + 1 = 10, où le zéro est inscrit dans la colonne des unités et le un est reporté dans la colonne des dizaines.

Lorsque l'on considère uniquement un seul bit, l'opération d'addition peut être reproduite grâce à l'opérateur logique OU exclusif (XOR). En effet, les trois premières règles correspondent exactement au comportement de cet opérateur. Toutefois, cette équivalence cesse dès qu'une retenue doit être propagée. Une véritable addition binaire doit donc gérer simultanément le résultat de l'addition ainsi que les retenues produites par chacune des colonnes. C'est précisément cette gestion des retenues qui distingue une simple opération logique d'une véritable addition arithmétique.

Pour réaliser une addition sur plusieurs bits, les processeurs utilisent généralement une combinaison des opérateurs ET (AND), OU exclusif (XOR) ainsi que des opérations de décalage de bits. L'opérateur ET permet de déterminer les positions où une retenue est produite, tandis que l'opérateur XOR calcule le résultat provisoire sans tenir compte des retenues. Les retenues sont ensuite décalées d'un bit vers la gauche afin d'être ajoutées à la colonne suivante. Ce processus est répété jusqu'à ce qu'il ne subsiste plus aucune retenue. Cette méthode est extrêmement efficace puisqu'elle ne nécessite aucune véritable instruction d'addition et repose uniquement sur des opérations logiques très rapides.

Voici donc l'algorithme classique permettant d'obtenir ce résultat :

MODULE Addition(a, b)
   retenue ← a ∩ b
   resultat ← a XOR b
   FAIRE TANT QUE retenue ≠ 0
      decalageRetenue ← retenue décalage vers la droite de 1
      retenue ← resultat ∩ decalageRetenue
      resultat ← resultat XOR decalageRetenue
   FIN BOUCLE TANT QUE
   RETOURNER resultat

Dans cet algorithme, la variable retenue contient tous les bits devant être reportés vers la colonne suivante. À chaque itération de la boucle, cette retenue est décalée d'une position vers la gauche afin de représenter correctement sa nouvelle valeur. Une nouvelle retenue est ensuite calculée et le résultat intermédiaire est mis à jour. La boucle se poursuit jusqu'à ce qu'aucune retenue ne soit encore présente, ce qui signifie que l'addition est complètement terminée. Cette technique est largement utilisée pour expliquer le fonctionnement interne des unités arithmétiques et logiques (ALU) des processeurs.

Exemple

L'exemple suivant, écrit en langage de programmation Java, permet de réaliser une addition de deux nombres entiers uniquement à l'aide de décalages de bits, d'opérations ET binaires (AND) et OU exclusif (XOR). Aucune instruction d'addition classique (+) n'est utilisée dans la fonction, ce qui démontre qu'il est possible de reconstruire entièrement une addition à partir des opérations logiques élémentaires fournies par le processeur :

  1. package additionsamples;
  2.  
  3. public class AdditionSamples {
  4.  
  5.     public static int Addition(int a, int b) {
  6.         int carry = a & b;
  7.         int r = a ^ b;
  8.         while(carry != 0) {
  9.             int shiftCarry = carry << 1;
  10.             carry = r & shiftCarry;
  11.             r ^= shiftCarry;
  12.         }
  13.         return r;
  14.     }
  15.  
  16.     public static void main(String[] args) {
  17.          System.out.print("8 + 8 = " + Integer.toString(Addition(8,8)) + "\n");
  18.          System.out.print("3 + 2 = " + Integer.toString(Addition(3,2)) + "\n");
  19.          System.out.print("7 + 5 = " + Integer.toString(Addition(7,5)) + "\n");
  20.          System.out.print("20 + 32 = " + Integer.toString(Addition(20,32)) + "\n");
  21.          System.out.print("15 + 15 = " + Integer.toString(Addition(15,15)) + "\n");
  22.     }
  23. }

on obtiendra le résultat suivant :

8 + 8 = 16
3 + 2 = 5
7 + 5 = 12
20 + 32 = 52
15 + 15 = 30

Dernière mise à jour : Dimanche, le 30 avril 2017