logo

Complément à deux

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

1011

pour 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