Comment les portes additionnent des nombres

Une porte XOR et une porte AND suffisent pour additionner deux bits. Enchaîne quatre additionneurs complets et tu peux additionner deux nombres quelconques de 0 à 15.

Essaie avant de lire la suite. Additionne 0101 et 0011 sur papier, en binaire, comme tu additionnes en décimal, et écris chaque retenue au-dessus de la colonne suivante. Tu n'as besoin que de trois faits : 0 + 0 = 0, 0 + 1 = 1 et 1 + 1 = 10, ce qui veut dire qu'on écrit 0 et qu'on retient 1. Avec une retenue qui arrive, 1 + 1 + 1 = 11 : tu écris 1 et tu retiens 1. Le calcul se trouve dans le paragraphe suivant, alors cache-le d'abord.

Voici le calcul. Colonne de droite : 1 + 1 = 10, on écrit 0, on retient 1. Suivante : 0 + 1 plus la retenue donne encore 10, on écrit 0, on retient 1. Suivante : 1 + 0 plus la retenue, 10, on écrit 0, on retient 1. Colonne de gauche : 0 + 0 plus la retenue donne 1. Le résultat est 1000, c'est-à-dire 8, et 5 + 3 = 8. Trois des quatre colonnes ont produit une retenue. Une calculatrice, un jeu et un tableur finissent tous par faire exactement cela. Dans un processeur, chaque colonne est traitée par quelques portes, et la scène démarre sur la même somme. Essaie ensuite 9 + 8. Il faut un cinquième bit.

La colonne de droite n'a besoin que de deux portes

Regarde la colonne de droite toute seule. Le bit de résultat, la somme, vaut 1 quand exactement une entrée vaut 1. C'est la règle de XOR. La retenue vaut 1 seulement quand les deux entrées valent 1. C'est la règle de AND. Une porte XOR et une porte AND côte à côte, alimentées par les deux mêmes entrées, additionnent donc deux bits. Ce petit circuit est un demi-additionneur. Il n'est qu'un « demi » parce qu'il n'a aucun moyen de recevoir la retenue de la colonne à sa droite.

Les autres colonnes ont trois bits à additionner

Dans toutes les autres colonnes, trois bits se rencontrent : un de chaque nombre et la retenue venue de la droite. Un additionneur complet prend les trois. Sa somme vaut A XOR B XOR retenue entrante, soit 1 quand un nombre impair des trois vaut 1. Sa retenue sortante vaut 1 quand au moins deux d'entre eux valent 1. Deux demi-additionneurs et une porte OR forment un additionneur complet. Aligne quatre additionneurs complets, relie la retenue sortante de chacun à la retenue entrante de son voisin de gauche, et tu obtiens un additionneur 4 bits. Chaque retenue doit se propager de droite à gauche avant que la dernière colonne se stabilise : ce montage s'appelle un additionneur à propagation de retenue. Les vrais processeurs additionnent des nombres de 64 bits avec des circuits plus astucieux qui calculent les retenues à l'avance, mais la règle de chaque colonne reste la même.

Quand le résultat est trop grand

Quatre bits contiennent de 0 à 15. Additionne 9 et 8 : le vrai résultat, 17, s'écrit 10001 en binaire, soit cinq bits. Un registre qui ne garde que quatre bits stocke 0001, c'est-à-dire 1, et la retenue restée à gauche est le signal d'alerte. C'est un dépassement de capacité. 15 + 1 sur quatre bits laisse 0000. Les processeurs lèvent un indicateur quand cela arrive, pour que les programmes puissent s'en apercevoir. La soustraction réutilise le même additionneur. Pour calculer A − B, le processeur inverse tous les bits de B et ajoute 1, ce qui donne le complément à deux de B, puis l'additionne à A et abandonne la retenue en trop. Pour 5 − 3 sur quatre bits : 3 s'écrit 0011, inversé 1100, plus 1 donne 1101. Ensuite 0101 + 1101 = 10010, et en gardant quatre bits il reste 0010, c'est-à-dire 2.

Multiplier, c'est décaler et additionner

La multiplication utilise les mêmes pièces. En binaire, multiplier par 2 décale tous les bits d'un rang vers la gauche, comme multiplier par 10 ajoute un zéro en décimal : 0011 (3) devient 0110 (6). Pour 5 × 3, remarque que 3 = 2 + 1. Donc 5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111, soit 15. Un circuit multiplieur décale et additionne de cette façon, en prenant un par un les bits à 1 du second nombre.