Dans l'architecture matéreille, les circuits de l'unité arithmétique et logique (ALU) réalisent toutes les opérations à l'aide de portes logiques fondamentales. Comprendre comment simuler l'addition, la soustraction, la multiplication et la division exclusivement avec des opérations bit à bit (AND, OR, XOR, NOT, décalages) permet de saisir les fondements du calcul binaire. Cette approche révèle également comment ces opérations sont optimisées au plus bas niveau.

1. Addition : XOR et gestion de la retenue

L'addition de deux entiers peut être décomposée en deux composantes parallèles : la somme partielle sans retenue et le masque de retenue.

L'opération XOR (^) fonctionne comme un additionneur sans retenue. Par exemple, 1 ^ 1 = 0 (le résultat unitaire est 0, mais une retenue est générée).

Les bits où les deux opérandes ont la valeur 1 produisent une retenue pour la position immédiatement supéreiure. La combinaison AND (&) avec un décalage à gauche de 1 (<< 1) identifie et déplace toutes ces retenues. La somme totale est la somme des retenues et de la somme partielle.

Simulation : calcul de 13 (1101) + 7 (0111)

• Étape 1 : somme partielle = 1101 ^ 0111 = 1010, retenue = (1101 & 0111) << 1 = 0101 << 1 = 1010.
• Étape 2 : somme partielle = 1010 ^ 1010 = 0000, retenue = (1010 & 1010) << 1 = 1010 << 1 = 10100.
• Étape 3 : somme partielle = 0000 ^ 10100 = 10100, retenue = (0000 & 10100) << 1 = 0. Terminé. Résultat : 20.

int additionner(int x, int y) {
    int somme = x;
    int retenue = y;
    while (retenue != 0) {
        int temp = somme;
        somme = somme ^ retenue;
        retenue = (temp & retenue) << 1;
    }
    return somme;
}

2. Soustraction : Utilisation du complément à deux

La soustraction a - b est mathématiquement équivalente à l'addition a + (-b). En informatique, les entiers négatifs sont représentés en complément à deux. Obtenir l'opposé d'un nombre n revient à inverser tous ses bits (complément à un, via ~n) puis à ajouter 1.

int opposer(int n) {
    return additionner(~n, 1);
}

int soustraire(int a, int b) {
    return additionner(a, opposer(b));
}

3. Multiplication : Simulation de la multiplication posée

La multiplication peut être réalisée en se basant sur le principe de la multilpication binaire posée. On parcourt les bits du multiplicateur b. Si le bit courant vaut 1, on ajoute le multiplicande a décalé à un accumulateur. À chaque itération, le multiplicande a est décalé d'un bit vers la gauche (son poids double), et le multiplicateur b est décalé d'un bit vers la droite.

Un pré-traitement est nécessaire pour gérer les signes : les opérandes sont converties en valeurs positives, et le signe du résultat final est déterminé par le XOR des signes initiaux.

int multiplier(int a, int b) {
    int signe = ((a < 0) ^ (b < 0)) ? -1 : 1;
    int positifA = (a < 0) ? opposer(a) : a;
    int positifB = (b < 0) ? opposer(b) : b;
    
    int resultat = 0;
    while (positifB != 0) {
        if (positifB & 1) {
            resultat = additionner(resultat, positifA);
        }
        positifA <<= 1;
        positifB >>= 1;
    }
    return (signe == -1) ? opposer(resultat) : resultat;
}

Attention : En C/C++, le décalage à droite d'un entier signé négatif est un comportement non défini. Il est donc crucial de travailler avec des valeurs positives comme dans l'implémentation ci-dessus, ou d'utiliser des types non signés pour les opérations de décalage intermédiaires.

4. Division : Recherche par dichotomie sur les poids fort

La division est l'opération la plus complexe. Une approche naïve par soustractions successives est inefficace. La méthode efficace imite une recherche binaire. Elle consiste à trouver, pour chaque bit du quotient (du plus significatif au moins significatif), si le diviseur décalé (b << i) peut être soustrait du dividende courant a.

Simulation : 15 (1111) ÷ 3 (0011)

• Test i=2 : 3 << 2 = 12 (1100). 15 ≥ 12 ? Oui. Bit de quotient à 1 (résultat = 100), nouveau dividende = 15 - 12 = 3.
• Test i=0 : 3 << 0 = 3 (0011). 3 ≥ 3 ? Oui. Bit de quotient à 1 (résultat = 101), nouveau dividende = 3 - 3 = 0.
• Résultat final : 101 binaire = 5.

La gestion des signes et des cas limites (comme la division par zéro ou INT_MIN / -1) est nécessaire pour une implémentation robuste. Le code ci-dessous illustre la logique centrale.

int diviser(int a, int b) {
    // Gestion du signe
    int signe = ((a < 0) ^ (b < 0)) ? -1 : 1;
    int dividendePositif = (a < 0) ? opposer(a) : a;
    int diviseurPositif = (b < 0) ? opposer(b) : b;
    
    int quotient = 0;
    // Parcours des bits du quotient potentiel (par exemple, pour 32 bits)
    for (int i = 31; i >= 0; i--) {
        // Vérifie si (diviseurPositif << i) peut être soustrait
        if ((dividendePositif >> i) >= diviseurPositif) {
            quotient = quotient | (1 << i);
            dividendePositif = soustraire(dividendePositif, diviseurPositif << i);
        }
    }
    return (signe == -1) ? opposer(quotient) : quotient;
}