Soustraction binaire
La soustraction binaire est l'opération arithmétique permettant de calculer la différence entre deux nombres représentés en base 2. À l'image de l'addition binaire, elle constitue l'une des opérations fondamentales réalisées par les processeurs modernes. Bien que son principe soit similaire à celui de la soustraction décimale enseignée à l'école, elle repose uniquement sur les chiffres 0 et 1, ce qui simplifie certaines règles tout en introduisant la notion d'emprunt (borrow) lorsqu'il devient impossible de soustraire directement deux bits.
Dans les ordinateurs modernes, la soustraction est rarement implémentée sous la forme d'un circuit spécialisé. La plupart des processeurs effectuent plutôt une addition du complément à deux du second opérande. Cette technique permet d'utiliser le même circuit électronique pour réaliser aussi bien les additions que les soustractions, réduisant ainsi la complexité du matériel. Toutefois, afin de bien comprendre le fonctionnement interne des calculs binaires, il est utile d'étudier la soustraction binaire dans sa forme traditionnelle avant d'aborder les compléments binaires.
Principe
La soustraction binaire s'effectue de droite à gauche, exactement comme une soustraction décimale. Chaque colonne est traitée indépendamment et, lorsqu'il n'est pas possible de soustraire le bit inférieur du bit supérieur, un emprunt est effectué sur la colonne immédiatement à gauche.
Les règles fondamentales de la soustraction binaire sont les suivantes :
|
0 - 0 → 0 1 - 0 → 1 1 - 1 → 0 0 - 1 → 1, emprunt 1 |
La dernière règle est la seule qui nécessite un emprunt. En effet, il est impossible de retirer 1 de 0. On emprunte donc un 1 à la colonne suivante. En base 2, cet emprunt correspond à ajouter 2 à la colonne courante :
| 102 - 12 = 12 |
Autrement dit :
| 0 + 2 - 1 = 1 |
Exemple simple
Calculons :
|
11012 -01012 |
En procédant colonne par colonne :
|
1101 - 0101 ------- 1000 |
Le résultat est :
| 10002 = 810 |
Puisque :
| 13 - 5 = 8 |
Exemple avec emprunt
Considérons maintenant :
|
10002 -00012 |
La première colonne nécessite un emprunt.
Le calcul devient :
|
1000 - 0001 ------- 0111 |
Le résultat est donc :
| 01112 = 710 |
Ce qui correspond bien à :
| 8 - 1 = 7 |
Algorithme
L'algorithme classique de soustraction binaire consiste à parcourir les bits de droite à gauche tout en tenant compte de l'emprunt éventuel.
Une représentation simplifiée est la suivante :
|
MODULE Soustraction(a,b) emprunt ← 0 POUR chaque bit de droite vers la gauche différence ← bitA - bitB - emprunt SI différence < 0 ALORS différence ← différence + 2 emprunt ← 1 SINON emprunt ← 0 FIN SI enregistrer différence FIN POUR RETOURNER résultat |
Cet algorithme reproduit exactement la méthode enseignée pour les soustractions décimales.
Soustraction par complément à deux
Les processeurs modernes utilisent rarement l'algorithme précédent.
Ils préfèrent convertir la soustraction :
| A - B |
en :
| A + (-B) |
Le nombre -B est obtenu grâce au complément à deux.
Par exemple :
| 12 - 5 |
devient :
| 12 + (-5) |
Cette technique permet d'utiliser exactement le même circuit électronique que celui servant à effectuer les additions.
Les avantages sont nombreux :
- réduction du nombre de circuits électroniques ;
- simplification de l'unité arithmétique (ALU) ;
- augmentation des performances ;
- simplification du jeu d'instructions du processeur.
- Utilisation des opérateurs binaires
Comme pour l'addition binaire, il est possible de construire une soustraction à partir d'opérations logiques.
Les circuits électroniques utilisent notamment :
- XOR pour calculer certaines différences de bits ;
- AND pour déterminer les emprunts ;
- NOT pour calculer les compléments ;
- des décalages de bits dans certaines implémentations spécialisées.
Ces opérations sont directement réalisées par les portes logiques présentes dans les processeurs.
Exemple en Java
L'exemple suivant utilise simplement l'opérateur de soustraction du langage Java :
Le résultat obtenu est :
12 - 5 = 720 - 7 = 13
15 - 15 = 0
8 - 1 = 7
Naturellement, le compilateur utilise les instructions de soustraction du processeur sans que le programmeur ait à gérer les emprunts.
Complexité
La soustraction binaire possède une complexité temporelle de :
| O(n) |
où n représente le nombre de bits des opérandes.
Chaque bit n'est traité qu'une seule fois, ce qui en fait une opération très efficace.
Avantages
La soustraction binaire présente plusieurs avantages :
- elle est simple à comprendre ;
- elle constitue la base des calculs arithmétiques binaires ;
- elle est facile à implémenter matériellement ;
- elle permet de manipuler des nombres de très grande taille ;
- elle est utilisée dans pratiquement tous les processeurs modernes.
Inconvénients
Quelques difficultés existent néanmoins :
- la gestion des emprunts complique légèrement l'algorithme ;
- les dépassements de capacité (overflow) doivent être détectés ;
- la manipulation des nombres négatifs nécessite généralement l'utilisation du complément à deux ;
- les calculs multiprécision demandent une propagation correcte des emprunts entre les différents mots mémoire.
Applications
La soustraction binaire est utilisée dans pratiquement tous les domaines de l'informatique :
- processeurs et microcontrôleurs ;
- unités arithmétiques et logiques (ALU) ;
- compilateurs ;
- systèmes d'exploitation ;
- bibliothèques multiprécision ;
- calcul scientifique ;
- cryptographie ;
- traitement d'images ;
- simulation numérique.
Elle intervient également dans de nombreux algorithmes plus complexes, notamment les divisions binaires, les comparaisons, les calculs matriciels et certaines méthodes de multiplication.
Remarque
En pratique, lorsqu'un programmeur écrit une instruction telle que :
| A - B |
il n'est pas nécessairement exécuté une véritable soustraction au niveau matériel. Sur la majorité des architectures modernes, le processeur transforme cette opération en une addition du complément à deux du second opérande. Cette optimisation permet de mutualiser les circuits électroniques et d'utiliser une seule unité arithmétique pour effectuer aussi bien les additions que les soustractions. C'est l'une des raisons pour lesquelles la compréhension du complément à deux est essentielle pour maîtriser l'arithmétique binaire et le fonctionnement interne des ordinateurs.