Représentation des Entiers Relatifs en Informatique : Théorie, Démonstrations et Implémentations

Contenu de l'article

1. Introduction et Contexte Historique
2. Comparaison des Méthodes de Représentation
3. Représentation en Signe-Magnitude
4. Représentation en Complément à Un
5. Représentation en Complément à Deux
6. Démonstrations Mathématiques Complètes
7. Implémentations en C, Python et Assemblage
8. Applications en Architecture et Cryptographie
9. Exercices Corrigés et Problèmes Avancés
10. Annexes : Preuves Supplémentaires et Codes Sources
11. Références Académiques et Bibliographie
12. Glossaire des Termes Techniques

Introduction et Contexte Historique

La représentation des nombres relatifs est un pilier fondamental de l’arithmétique informatique, car elle détermine la manière dont les entiers signés sont stockés, manipulés et calculés dans les systèmes numériques. Trois méthodes principales coexistent : la représentation en signe-magnitude, le complément à un, et le complément à deux. Chacune de ces méthodes influence directement la complexité des circuits logiques, la performance des calculs, et la fiabilité des systèmes embarqués ou des architectures processeurs modernes.

Historiquement, la représentation en signe-magnitude a été la première utilisée, en raison de sa simplicité conceptuelle. Cependant, elle a rapidement montré ses limites, notamment en raison de la double représentation du zéro et de la complexité des opérations arithmétiques. Le complément à un a ensuite été introduit pour simplifier certaines opérations, mais il souffrait toujours de la double représentation du zéro et d’une complexité accrue pour l’addition. C’est finalement le complément à deux qui s’est imposé dans les années 1960, notamment avec des machines pionnières comme le CDC 6600. Cette méthode a révolutionné l’arithmétique binaire en permettant une simplification radicale des circuits logiques et en éliminant la double représentation du zéro. Aujourd’hui, elle est adoptée par la quasi-totalité des architectures modernes, telles que x86, ARM et RISC-V, en raison de son efficacité et de sa simplicité.

Cet article explore ces trois méthodes sous plusieurs angles :

1. Leurs fondements mathématiques, incluant les plages de représentation, les propriétés algébriques et les limites théoriques.
2. Leurs implémentations matérielles et logicielles, avec des exemples concrets en C, Python et Assemblage.
3. Leurs applications pratiques, notamment dans les processeurs, la cryptographie et les systèmes embarqués.
4. Leurs limites et optimisations, comme la gestion des débordements, les algorithmes de multiplication rapide et les techniques de détection d’erreurs.

Nous aborderons également des démonstrations mathématiques complètes, des exercices corrigés et des problèmes avancés pour illustrer les concepts théoriques et pratiques.

Comparaison des Méthodes de Représentation

Le tableau ci-dessous résume les principales caractéristiques des trois méthodes de représentation des nombres relatifs. Ces critères sont essentiels pour comprendre pourquoi le complément à deux domine aujourd’hui l’arithmétique informatique.

Critère	Signe-Magnitude	Complément à Un	Complément à Deux
Plage de représentation (\(n\) bits)	\(-[2^{n-1}-1, 2^{n-1}-1]\)	\(-[2^{n-1}-1, 2^{n-1}-1]\)	\([-2^{n-1}, 2^{n-1}-1]\)
Nombre de représentations du zéro	2 (\(+0\), \(-0\))	2	1
Complexité de l'addition	Élevée (circuits distincts pour les signes)	Moyenne (nécessite un end-around carry)	Faible (circuit unique pour addition et soustraction)
Complexité de la soustraction	Élevée (nécessite une logique de comparaison)	Moyenne (similaire à l’addition mais avec gestion du report)	Identique à l'addition
Utilisation actuelle	Rare (systèmes hérités ou applications spécifiques)	Théorique ou historique	Standard (x86, ARM, RISC-V, etc.)
Exemple pour \(n=8\), \(x=-5\)	10000101	11111010	11111011
Avantages principaux	Représentation intuitive, compatible avec les nombres non signés	Simplicité de l’inversion des bits pour obtenir le négatif	Unicité du zéro, simplicité des circuits, fermeture sous l’addition
Inconvénients principaux	Double zéro, addition complexe	Double zéro, gestion du report de sortie	Aucun (mis à part la plage asymétrique)

Représentation en Signe-Magnitude

Définition Formelle

Dans la représentation en signe-magnitude, un entier relatif \(x\) est encodé à l’aide d’un bit de signe \(s\) (où \(s = 0\) pour les nombres positifs et \(s = 1\) pour les nombres négatifs) et de \(n-1\) bits pour la magnitude \(M\). La valeur de \(x\) est donnée par :

\[ x = (-1)^s \times M, \quad \text{où } M = \sum_{i=0}^{n-2} b_i \cdot 2^i. \]

Cette méthode est intuitive car elle sépare clairement le signe de la valeur absolue du nombre. Cependant, elle présente des limites majeures, notamment la double représentation du zéro et la complexité des opérations arithmétiques.

Propriétés et Limites

• Avantages :
  • Représentation directe et intuitive, compatible avec les nombres non signés.
  • Facilité de conversion entre nombres signés et non signés.
• Inconvénients :
  • Double représentation du zéro : \(0\) peut être représenté par \(000\dots0\) (\(+0\)) ou \(100\dots0\) (\(-0\)), ce qui complique les tests d’égalité et les comparaisons.
  • Complexité des opérations arithmétiques : L’addition et la soustraction nécessitent des circuits distincts pour gérer les signes, ce qui augmente la complexité matérielle.

Exemple Détaillé

Prenons un exemple avec \(n=8\) bits :

• Le nombre \(5\) est représenté par \(00000101\).
• Le nombre \(-5\) est représenté par \(10000101\).
• Pour effectuer l’addition \(5 + (-3)\) :
  1. Les signes sont différents, donc on effectue une soustraction des magnitudes : \(5 - 3 = 2\).
  2. Le résultat est \(00000010\), avec le signe déterminé par le nombre ayant la plus grande magnitude (ici, \(5 > 3\), donc le résultat est positif).

Démonstration de la Double Représentation du Zéro

Par définition, le zéro positif est représenté par \(000\dots0\), tandis que le zéro négatif est représenté par \(100\dots0\). Ces deux codes sont distincts, ce qui implique que les tests d’égalité à zéro doivent vérifier à la fois la magnitude et le bit de signe. Cela ajoute une complexité inutile aux circuits logiques.

Représentation en Complément à Un

Définition Formelle

Dans la représentation en complément à un, un nombre négatif \(-x\) est obtenu en inversant tous les bits de la représentation binaire de \(x\). Formellement, pour un nombre \(x\) sur \(n\) bits :

\[ \phi_{\text{complement a un}}(x) = \begin{cases} \phi_{\text{nat}}(x) & \text{si } x \geq 0, \\ \overline{\phi_{\text{nat}}(x)} & \text{si } x < 0. \end{cases} \]

où \(\overline{\phi_{\text{nat}}(x)}\) désigne l’inversion de tous les bits de la représentation naturelle de \(x\).

Addition et End-Around Carry

L’addition de deux nombres \(a\) et \(b\) en complément à un suit les étapes suivantes :

1. Effectuer l’addition binaire classique des deux nombres.
2. Si un report de sortie (ou carry out) est généré, il est réinjecté dans le bit de poids faible (technique dite de l’end-around carry).

Exemple : Calculons \(7 + (-7)\) sur 8 bits :

• \(7\) est représenté par \(00000111\).
• \(-7\) est représenté par \(11111000\) (inversion des bits de \(7\)).
• L’addition donne : \(00000111 + 11111000 = 11111111\).
• Un report de sortie est généré, donc on l’ajoute au résultat : \(11111111 + 1 = 00000000\).

Limites

• Double représentation du zéro : \(000\dots0\) et \(111\dots1\) représentent tous deux le zéro, ce qui complique les tests d’égalité.
• Complexité matérielle : La gestion du report de sortie nécessite des circuits supplémentaires, ce qui rend cette méthode moins efficace que le complément à deux.

Représentation en Complément à Deux

Définition Formelle

Dans la représentation en complément à deux, un nombre négatif \(-x\) est représenté par \(2^n - x\). La formule générale est :

\[ \phi_{\text{complement a deux}}(x) = \begin{cases} x & \text{si } x \geq 0, \\ 2^n + x & \text{si } x < 0. \end{cases} \]

Cette méthode élimine la double représentation du zéro et simplifie les opérations arithmétiques, ce qui explique son adoption universelle dans les architectures modernes.

Propriétés Algébriques

• Unicité du zéro : Seule la représentation \(000\dots0\) est valide pour le zéro.
• Fermeture sous l'addition : Pour tout \(a, b\) dans la plage \([-2^{n-1}, 2^{n-1}-1]\), la somme \(a + b \mod 2^n\) reste dans cette plage.
• Soustraction = Addition du complément : La soustraction \(a - b\) est équivalente à l’addition \(a + \phi(-b)\).

Exemples et Débordements

Prenons \(n=8\) bits :

• Le nombre \(5\) est représenté par \(00000101\).
• Le nombre \(-5\) est représenté par \(11111011\) (car \(2^8 - 5 = 251\), soit \(11111011\) en binaire).
• Un exemple de débordement : \(127 + 1 = -128\). En effet, \(127\) est représenté par \(01111111\), et \(1\) par \(00000001\). Leur somme est \(10000000\), qui représente \(-128\) en complément à deux.

Preuve de l'Unicité du Zéro

Supposons qu’il existe une autre représentation du zéro, notée \(\phi(z)\). Alors, \(z = 2^n\), ce qui est impossible sur \(n\) bits. Par conséquent, le zéro est unique dans cette représentation.

Détection des Débordements

Un débordement (overflow) se produit si et seulement si :

\[ (a > 0 \land b > 0 \land a + b < 0) \lor (a < 0 \land b < 0 \land a + b \geq 0). \]

Démonstrations Mathématiques Complètes

1. Fermeture sous l'Addition en Complément à Deux

Soient \(a, b \in [-2^{n-1}, 2^{n-1}-1]\). Leur somme \(a + b\) est calculée modulo \(2^n\). Si \(a + b \geq 2^{n-1}\) ou \(a + b < -2^{n-1}\), un débordement se produit. Sinon, le résultat est exact et reste dans la plage de représentation.

2. Algorithme de Booth pour la Multiplication

L’algorithme de Booth est une méthode optimisée pour la multiplication binaire, qui réduit le nombre d’additions en exploitant les séquences de 1 dans la représentation binaire. Par exemple, pour calculer \(-7 \times 5\) sur 8 bits :

1. \(-7\) est représenté par \(11111001\).
2. \(5\) est représenté par \(00000101\).
3. L’algorithme de Booth produit le résultat \(11011101\), qui correspond à \(-35\) en complément à deux.

L’algorithme examine les paires de bits adjacents du multiplicateur \(Y\) en complément à deux, y compris un bit implicite \(y_{-1} = 0\). Pour chaque bit \(y_i\), les bits \(y_i\) et \(y_{i-1}\) sont considérés. Si \(y_i = y_{i-1}\), on décale simplement. Si \(y_i = 1\) et \(y_{i-1} = 0\), on soustrait le multiplicande. Si \(y_i = 0\) et \(y_{i-1} = 1\), on ajoute le multiplicande. Cela permet de réduire le nombre d’opérations arithmétiques, surtout pour les séquences de 1 consécutifs.

3. Division par Newton-Raphson

Pour calculer \(\frac{a}{b}\), on utilise une itération de Newton-Raphson pour approximer l’inverse de \(b\) :

\[ x_{k+1} = x_k (2 - b x_k) \quad \text{avec } x_0 = \text{approximation initiale de } 1/b. \]

Implémentations en C, Python et Assemblage

C : Addition avec Détection de Débordement

Voici un exemple de code en C qui détecte les débordements lors de l’addition de deux entiers :

#include <stdio.h>
#include <limits.h>

int main() {
    int a = 120, b = 80;
    int sum = a + b;
    if ((a > 0 && b > 0 && sum < 0) || (a < 0 && b < 0 && sum > 0))
        printf("Débordement détecté !\n");
    else
        printf("Somme : %d\n", sum);
    return 0;
}

Python : Conversion et Vérification

Le code Python suivant illustre la conversion en complément à deux et la détection de débordement :

def to_twos_complement(n, bits):
    if n >= 0:
        return bin(n)[2:].zfill(bits)
    else:
        return bin((1 << bits) + n)[2:]

def detect_overflow(a, b, result, bits):
    max_val = (1 << (bits-1)) - 1
    min_val = -(1 << (bits-1))
    return (a > 0 and b > 0 and result < min_val) or (a < 0 and b < 0 and result > max_val)

a, b = 120, 80
bits = 8
sum_val = (int(to_twos_complement(a, bits), 2) + int(to_twos_complement(b, bits), 2)) & 0xFF
sum_val = sum_val if sum_val < 128 else sum_val - 256
if detect_overflow(a, b, sum_val, bits):
    print("Débordement !")
else:
    print(f"Somme : {sum_val}")

Assemblage x86 : Utilisation du Flag OF

En Assemblage x86, le flag OF (Overflow Flag) est utilisé pour détecter les débordements :

section .text
global _start

_start:
    mov al, 120
    add al, 80
    jo overflow   ; Saut si débordement (OF=1)
    jmp end

overflow:
    ; Gestion du débordement
    mov eax, 4
    mov ebx, 1
    mov ecx, msg
    mov edx, len
    int 0x80

end:
    mov eax, 1
    int 0x80

section .data
msg db "Débordement détecté !", 0xA
len equ $ - msg

Applications en Architecture et Cryptographie

Architecture des Processeurs

Le complément à deux est omniprésent dans les unités arithmétiques et logiques (ALU) des processeurs modernes. Ses avantages incluent :

• La simplification des circuits, car un seul additionneur suffit pour l’addition et la soustraction.
• La génération de flags de débordement pour les instructions conditionnelles, comme JO en x86.

Les processeurs modernes (x86, ARM, RISC-V) utilisent le complément à deux pour toutes les opérations arithmétiques, car il permet une implémentation matérielle efficace et une gestion simplifiée des débordements. Par exemple, l’addition et la soustraction sont réalisées par le même circuit, et la détection de débordement est intégrée directement dans l’UAL (Unité Arithmétique et Logique) via le flag OF.

Cryptographie : Calculs Modulaires

En cryptographie, les calculs modulaires sont souvent réalisés en complément à deux. Par exemple, pour calculer \(15 \mod 7\) :

• \(15\) est représenté par \(00001111\).
• On soustrait \(2 \times 7 = 14\) de \(15\), ce qui donne \(1\) comme résultat final.

Les processeurs modernes intègrent des instructions dédiées à la cryptographie (comme AES-NI sur x86 ou les extensions cryptographiques d’ARMv8), qui exploitent le complément à deux pour des opérations rapides et sécurisées. Ces instructions permettent d’accélérer les calculs de chiffrement/déchiffrement, essentiels pour la sécurité des données.

Exercices Corrigés et Problèmes Avancés

Exercice 1 : Conversion en Complément à Deux

Représenter \(-42\) sur 8 bits en complément à deux.

Solution :

1. Écrire \(42\) en binaire sur 8 bits : \(00101010\).
2. Inverser les bits : \(11010101\).
3. Ajouter 1 : \(11010110\).

Exercice 2 : Multiplication avec l'Algorithme de Booth

Calculer \(-7 \times 5\) sur 8 bits.

Solution :

1. \(-7\) est représenté par \(11111001\).
2. \(5\) est représenté par \(00000101\).
3. L’algorithme de Booth produit le résultat \(11011101\), soit \(-35\).

Problème Avancé : Optimisation des Multiplications

Proposer un algorithme pour multiplier deux entiers de 64 bits en complément à deux, en minimisant le nombre d’opérations. Une approche possible consiste à utiliser l’algorithme de Booth optimisé, qui réduit le nombre d’additions en exploitant les séquences de bits consécutifs. Voici un exemple d’implémentation en Python :

def booth_multiplication(multiplicand, multiplier, bits):
    # Convertir en complément à deux si négatif
    if multiplicand < 0:
        multiplicand = (1 << bits) + multiplicand
    if multiplier < 0:
        multiplier = (1 << bits) + multiplier

    # Initialisation
    A = 0
    Q = multiplicand
    M = multiplier
    n = bits

    for _ in range(n):
        # Examiner les deux bits de poids faible de Q
        if (Q & 1) == 1 and (Q & 2) == 0:
            A += M
        elif (Q & 1) == 0 and (Q & 2) == 2:
            A -= M
        # Décalage arithmétique à droite
        A = (A >> 1) | ((A & 1) << (n-1))
        Q = (Q >> 1) | ((Q & 1) << (n-1))

    return A if A < (1 << (n-1)) else A - (1 << n)

Annexes : Preuves Supplémentaires et Codes Sources

Preuve de la Bijectivité en Complément à Deux

La fonction \(\phi: [-2^{n-1}, 2^{n-1}-1] \to \{0,1\}^n\) est bijective, car chaque entier dans la plage a une représentation unique, et chaque chaîne de bits correspond à un entier unique dans cette plage.

Code Source Complet

Les implémentations complètes en C, Python et Assemblage sont disponibles ici.

Références Académiques et Bibliographie

• Université de Lorraine - Arithmétique binaire et représentation des nombres relatifs
• Université de Toulon - Mathématiques pour l'informatique : Arithmétique
• Lycée Blaise Pascal - Représentation des nombres entiers relatifs
• Computer Arithmetic: Algorithms and Hardware Designs, B. Parhami, Oxford University Press, 2020.
• Norme IEEE 754 pour les nombres à virgule flottante.
• Master IMD - Interactions entre mathématiques et informatique
• Wikipédia - Algorithme de multiplication de Booth
• GeeksforGeeks - Booth’s Algorithm
• StudySmarter - Complément à deux
• Wikipédia - Indicateur de débordement
• Lyceum - Représentation des entiers relatifs

Glossaire des Termes Techniques

Terme	Définition
End-around carry	Report de sortie réinjecté dans l’addition, utilisé en complément à un.
Overflow flag (OF)	Indicateur de débordement arithmétique en Assemblage.
Algorithme de Booth	Algorithme d’optimisation pour la multiplication binaire, réduisant le nombre d’additions.
Complément à deux	Méthode de représentation des nombres relatifs qui élimine la double représentation du zéro et simplifie les opérations arithmétiques.
AES-NI	Jeu d’instructions x86 pour accélérer les opérations de chiffrement AES.
ARMv8	Architecture processeur ARM incluant des extensions cryptographiques.