Il existe trois manières différentes de représenter un entier signé (article) . a : bit signé, b : complément de 1 et c : complément de 2. Essayons de comprendre comment ces méthodes ont dérivé et pourquoi le complément à 2 est préféré aux autres.
Comme nous le savons, les données sont stockées en bits. Comment pouvons-nous stocker un entier signé dans la mémoire ? Pour résoudre ce problème, nous développerons d’abord une solution naïve, puis la répéterons jusqu’à ce que nous ayons la meilleure solution à notre problème.
a) Bit signé
Lorsque vous essayez de stocker un entier signé, il semble évident de réserver le bit le plus à gauche pour le signe et d'utiliser les bits restants pour stocker réellement les valeurs. Par exemple : dans un système 4 bits, le premier bit en partant de la gauche sera réservé au signe (0 représente positif alors que 1 représente négatif) et les 3 autres bits seront utilisés pour stocker les valeurs. De même, dans un système 8 bits, le premier bit en partant de la gauche sera utilisé pour le signe et les 7 restants seront utilisés pour les valeurs.
M. Non. | Représentation binaire | Valeur décimale |
UN | 0000 | +0 |
B | 0001 | +1 |
C | 0010 | +2 |
D | 0011 | +3 |
ET | 0100 | +4 |
F | 0101 | +5 |
g | 0110 | +6 |
H | 0111 | +7 |
je | 1000 | -0 |
J. | 1001 | -1 |
K | 1010 | -2 |
L | 1011 | -3 |
M | 1100 | -4 |
N | 1101 | -5 |
Ô | 1110 | -6 |
P. | 1111 | -7 |
En utilisant cette approche, nous sommes capables de représenter avec succès un entier signé. Mais en l’analysant de plus près, nous pourrions observer les inconvénients suivants :
1) Deux représentations de zéro :
Dans un système 4 bits, nous devrions pouvoir stocker 16 (24) valeurs, mais +1 à +7 et -1 à -7 ne sont que 14 valeurs. Où sont les deux valeurs restantes ? En observant attentivement le tableau, nous découvrirons que ces deux valeurs convergent vers 0. Ainsi, nous avons deux représentations de zéro, c'est-à-dire une représentation pour +0 et une autre pour -0.
Mais deux représentations de 0 sont-elles une grande préoccupation ? Et alors? Au lieu de 16 valeurs uniques, nous ne pouvons stocker que 15 valeurs. On peut se permettre de réduire la portée de 1, n’est-ce pas ? Pour le développeur de logiciels, cela n'est peut-être pas préoccupant, mais pour un concepteur de circuits, il peut être très frustrant de vérifier d'abord si la valeur est +0, puis de vérifier si elle est -0.
2) L’extension signée ne fonctionne pas pour les nombres négatifs :
La taille des données augmente rapidement. Il faudra parfois étendre le système de bits afin de pouvoir augmenter la gamme de données pouvant être stockées. En 2014, la vidéo Gangnam Style a dépassé la limite de vue de YouTube et a forcé YouTube à augmenter le nombre de vues de 32 bits à un nombre entier signé de 64 bits. De même, l'horloge Unix 32 bits débordera le 19 janvier 2038 car elle enregistre le temps en secondes dans un entier signé 32 bits.
Il est donc tout aussi important que notre système de représentation soit facilement extensible, ce qui n'est pas possible avec ce système de représentation.
Décimal | 4 bits | 5 bits | 6 bits |
+2 | 0010 | 00010 | 000010 |
+7 | 0111 | 00111 | 000111 |
-2 | 1010 | 10010 (!= 11010) | 100010 (!= 111010) |
-7 | 1111 | 10111 (!= 11111) | 100111 (!= 111111) |
3) L’addition binaire ne fonctionne pas :
Essayons d'ajouter deux nombres binaires :
Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | |||
Numéro 1 | 0010 | +2 | 0111 | +7 | 1101 | -5 | ||
Numéro 2 | 1010 | -2 | 1010 | -2 | 0011 | +3 | ||
Addition binaire | 1100 | -4 | 0001 | +1 | 0000 | +0 | ||
Addition décimale | +0 | +5 | -2 |
Pourquoi une simple addition binaire ne fonctionne-t-elle pas ici ? La raison en est que le bit de signe (le plus à gauche) n'est pas un bit ordinaire et ne fait pas partie du nombre réel. Imaginez la situation dans laquelle il faut concevoir les circuits matériels pour ignorer le bit de signe pour effectuer l'addition, puis ajouter le bit de signe.
C’était donc une manière naïve de représenter un entier signé. Le principal problème de cette approche est que nous avons cartographié les nombres négatifs vers le haut. Si nous modifions notre système de cartographie pour les rendre descendants, certains des problèmes ci-dessus seront résolus.
b) 1's Co mettre en œuvre
Si nous remappons nos nombres négatifs de haut en bas, nous obtiendrons le tableau binaire suivant :
Oui Non. | Représentation binaire | Valeur décimale | |
complément à 1 | Morceau signé | ||
UN | 0000 | +0 | +0 |
B | 0001 | +1 | +1 |
C | 0010 | +2 | +2 |
D | 0011 | +3 | +3 |
ET | 0100 | +4 | +4 |
F | 0101 | +5 | +5 |
g | 0110 | +6 | +6 |
H | 0111 | +7 | +7 |
je | 1000 | -7 | -0 |
J. | 1001 | -6 | -1 |
K | 1010 | -5 | -2 |
L | 1011 | -4 | -3 |
M | 1100 | -3 | -4 |
N | 1101 | -2 | -5 |
Ô | 1110 | -1 | -6 |
P. | 1111 | -0 | -7 |
Comment obtenir une représentation binaire d’un entier dans la méthode du complément à 1 ?
- Les nombres positifs sont représentés de la même manière que la méthode des entiers signés
- Les nombres négatifs sont représentés en inversant chaque bit du nombre positif correspondant (l'inversion peut facilement être effectuée en utilisant la porte NOT lors de la conception matérielle)
Analysons cela de près pour voir si nous avons obtenu des améliorations.
1) Deux représentations de zéro :
Dans cette approche, nous avons également deux représentations de zéro.
2) L'extension signée ne fonctionne pas pour les nombres négatifs :
L'extension signée fonctionne parfaitement pour les nombres négatifs.
Décimal | 4 bits | 5 bits | 6 bits |
+2 | 0010 | 00010 | 000010 |
+7 | 0111 | 00111 | 000111 |
-2 | 1101 | 11101 | 111101 |
-7 | 1000 | 11000 | 111000 |
3) L'addition binaire fonctionne avec des règles modifiées :
Binaire | Décimal | Binaire | Décimal | algorithmes de recherche binaire | Binaire | Décimal | ||
Numéro 1 | 0010 | +2 | 0111 | +7 | 1010 | -5 | ||
Numéro 2 | 1101 | -2 | 1101 | -2 | 0011 | +3 | ||
Addition binaire | 1111 | -0 | 0100 | +4 | 1101 | -2 | ||
Addition décimale | +0 | +5 | -2 |
La réponse n’est pas toujours correcte, mais elle est très proche de la bonne réponse. Nous pouvons le faire fonctionner si nous suivons la règle selon laquelle si vous avez généré un report sur votre bit le plus à gauche, ne le jetez pas, ramenez-le plutôt et ajoutez-le au bit le plus à droite.
Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | |||
Numéro 1 | 0111 | +7 | 1110 | -1 | 0111 | +7 | ||
Numéro 2 | 1101 | -2 | 1001 | -6 | 1011 | -4 | ||
Addition binaire | (1) 0100 | +4 | (1) 0111 | +7 | (1) 0010 | +2 | ||
Ajout d'un report en avant | 0101 | +5 | 1000 | -7 | 0011 | +3 |
La méthode du complément à 1 est définitivement meilleure que le bit signé. Nos soucis majeurs sont résolus mais restent problématiques (avoir deux représentations de zéro) et notre hack en complément binaire donne des indices pour améliorer la méthode du complément à 1. Reformulons ces phrases pour rendre les choses plus faciles.
- Nous avons une représentation supplémentaire de zéro qui n'est pas nécessaire
- Lors de l'ajout de deux nombres binaires, si nous avons un report dans le bit le plus à gauche, nous devons alors ajouter +1 au résultat, c'est-à-dire que la bonne réponse peut être trouvée en passant à la ligne suivante de la table binaire.
Les deux nous indiquent qu’une représentation supplémentaire de zéro est à l’origine du problème. Alors, supprimons ce zéro supplémentaire et déplaçons toutes les valeurs négatives vers la ligne suivante (-7 se déplacera de I -> J, -6 se déplacera de J -> K et ainsi de suite…)
c) Le complément à 2
Lorsque nous supprimons -0 du tableau du complément à 1 et décalons toutes les valeurs négatives d’une ligne ci-dessous, nous obtiendrons le tableau suivant appelé complément à 2 :
Oui Non. | Représentation binaire | Valeur décimale | |||
complément à 2 | complément à 1 | Morceau signé | |||
UN | 0000 | +0 | +0 | +0 | |
B | 0001 | +1 | +1 | +1 | |
C | 0010 | +2 | +2 | +2 | |
D | 0011 | +3 | +3 | +3 | |
ET | 0100 | +4 | +4 | +4 | |
F | 0101 | +5 | +5 | +5 | |
g | 0110 | +6 | +6 | +6 | |
H | 0111 | +7 | +7 | +7 | |
je | 1000 | -8 | -7 | -0 | |
J. | 1001 | -7 | = inverse de 7 + 1 bit | -6 | -1 |
K | 1010 | -6 | = inverse de 6 + 1 bit | -5 | -2 |
L | 1011 | -5 | = inverse de 5 + 1 bit | -4 | -3 |
M | 1100 | -4 | = inverse de 4 + 1 bit | -3 | -4 |
N | 1101 | -3 | = inverse de 3 + 1 bit | -2 | -5 |
Ô | 1110 | -2 | = inverse de 2 + 1 bit | -1 | -6 |
P. | 1111 | -1 | = inverse de 1 + 1 bit | -0 | -7 |
Comment obtenir une représentation binaire d’un entier dans la méthode du complément à 2 ?
- Les nombres positifs sont représentés de la même manière que la méthode des entiers signés
- Les nombres négatifs sont représentés en inversant chaque bit du nombre positif correspondant, puis en y ajoutant 1 bit.
1) Une représentation de zéro :
Nous n’avons maintenant qu’une seule représentation de zéro et cela nous permet de stocker total 16 valeurs uniques (+0 à +7 et -1 à -8).
2) L'extension signée fonctionne pour les nombres négatifs :
L'extension signée fonctionne parfaitement pour les nombres négatifs.
Décimal | 4 bits | 5 bits | 6 bits |
+2 | 0010 | 00010 | 000010 |
+7 | 0111 | 00111 | 000111 |
-2 | 1110 | 11110 | 111110 |
-7 | 1001 | 11001 | 111001 |
3) Addition binaire :
Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | ||||
Numéro 1 | 0010 | +2 | 0111 | +7 | 1011 | -5 | 1111 | -1 | |||
Numéro 2 | 1110 | -2 | 1110 | -2 | 0011 | +3 | 1010 | -6 | |||
Répondre | 0000 | +0 | 0101 | +5 | 1110 | -2 | 1001 | -7 |
4) Le premier bit est un bit signé :
Le complément de 2 a cette belle propriété que le premier bit est un bit de signe car tout positif commence par 0 alors que tout négatif par 1.
5) Vérification de dépassement de mémoire :
Lors de l'addition, nous nous sommes assurés que notre réponse se situait dans la plage, mais lors de la conception du matériel, un débordement de mémoire doit être détecté. Ce serait une très mauvaise idée pour les concepteurs de matériel de vérifier l'ampleur pour détecter un débordement. La méthode du complément de 2 fournit un moyen très simple de détecter un débordement de mémoire. je f le report sur le bit signé n'est pas égal à l'exécution du bit signé, il s'agit alors d'un débordement de mémoire c'est-à-dire que si le report sur le bit signé est 0 mais l'exécution est 1 ou si le report 1 mais l'exécution est 0, alors il s'agit d'un débordement de mémoire.
Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | Binaire | Décimal | ||||
Numéro 1 | 1011 | -5 | 0010 | 2 | 0111 | +7 | 1011pour la boucle en Java | -5 | |||
Numéro 2 | 1100 | -4 | 0110 | 6 | 1110 | -2 | 0011 | 3 | |||
Ajout | (1) 0111 | (0)1000 | (1)0101 | (0)1110 | |||||||
apporter pour signer le bit | 0 | débordement | 1 | débordement | 1 | Non | 0 | Non | |||
effectuer pour signer le bit | 1 | 0 | 1 | 0 |