Représentations de nombres signés - Signed number representations

En informatique , les représentations de nombres signés sont nécessaires pour coder les nombres négatifs dans les systèmes de nombres binaires.

En mathématiques , les nombres négatifs dans n'importe quelle base sont représentés en les préfixant d'un signe moins ("−"). Cependant, dans le matériel informatique , les nombres ne sont représentés que sous forme de séquences de bits , sans symboles supplémentaires. Les quatre méthodes les plus connues pour étendre le système de numération binaire pour représenter les nombres signés sont : le signe et la grandeur , le complément à un , le complément à deux et le binaire décalé . Certaines des méthodes alternatives utilisent des signes implicites au lieu d'explicites, comme le binaire négatif, en utilisant la base -2 . Des méthodes correspondantes peuvent être imaginées pour d' autres bases , qu'elles soient positives, négatives, fractionnaires, ou d'autres élaborations sur de tels thèmes.

Il n'y a pas de critère définitif par lequel l'une des représentations est universellement supérieure. Pour les nombres entiers, la représentation utilisée dans la plupart des appareils informatiques actuels est le complément à deux, bien que les mainframes de la série Unisys ClearPath Dorado utilisent le complément à un.

Histoire

Les premiers jours de l'informatique numérique ont été marqués par de nombreuses idées concurrentes sur la technologie matérielle et la technologie mathématique (systèmes de numérotation). L'un des grands débats était le format des nombres négatifs, certains des meilleurs experts de l'époque avaient des opinions très fortes et divergentes. Un camp supportait le complément à deux , le système qui domine aujourd'hui. Un autre camp a pris en charge le complément à un, où toute valeur positive est transformée en son équivalent négatif en inversant tous les bits d'un mot. Un troisième groupe prenait en charge "sign & magnitude" (sign-magnitude), où une valeur est changée de positive à négative simplement en basculant le bit de signe (de poids fort) du mot.

Il y avait des arguments pour et contre chacun des systèmes. Le signe et la magnitude permettaient de tracer plus facilement les vidages de mémoire (un processus courant dans les années 1960) car les petites valeurs numériques utilisent moins de 1 bits. En interne, ces systèmes effectuaient des calculs de complément à un, de sorte que les nombres devaient être convertis en valeurs de complément à un lorsqu'ils étaient transmis d'un registre à l'unité mathématique, puis reconvertis en grandeur de signe lorsque le résultat était transmis au registre. L'électronique nécessitait plus de portes que les autres systèmes - une préoccupation majeure lorsque le coût et l'emballage des transistors discrets étaient critiques. IBM a été l'un des premiers partisans de la grandeur du signe, avec ses ordinateurs des séries 704 , 709 et 709x étant peut-être les systèmes les plus connus pour l'utiliser.

Le complément à un permettait des conceptions matérielles un peu plus simples car il n'était pas nécessaire de convertir les valeurs lorsqu'elles étaient transmises vers et depuis l'unité mathématique. Mais il partageait également une caractéristique indésirable avec la grandeur du signe - la capacité de représenter un zéro négatif (-0). Le zéro négatif se comporte exactement comme le zéro positif ; lorsqu'il est utilisé comme opérande dans n'importe quel calcul, le résultat sera le même qu'un opérande soit un zéro positif ou négatif. L'inconvénient, cependant, est que l'existence de deux formes de même valeur nécessite deux plutôt qu'une seule comparaison lors de la vérification de l'égalité avec zéro. La soustraction du complément à un peut également entraîner un emprunt final (décrit ci-dessous). On peut affirmer que cela rend la logique d'addition/soustraction plus compliquée ou que cela la rend plus simple car une soustraction nécessite simplement d'inverser les bits du deuxième opérande lorsqu'il est transmis à l'additionneur. Le PDP-1 , série CDC 160 , CDC 3000 séries, CDC 6000 série , UNIVAC 1100 série, et les CLIC la représentation en complément à ceux de l' utilisation de l' ordinateur.

Le complément à deux est le plus facile à implémenter dans le matériel, ce qui peut être la raison ultime de sa grande popularité. Les processeurs des premiers ordinateurs centraux se composaient souvent de milliers de transistors – l'élimination d'un nombre important de transistors représentait une économie de coûts importante. Les ordinateurs centraux tels que l' IBM System/360 , la série GE-600 et les PDP-6 et PDP-10 utilisent le complément à deux, tout comme les mini-ordinateurs tels que les PDP-5 et PDP-8 et les PDP-11 et VAX . Les architectes des premiers processeurs à circuits intégrés ( Intel 8080 , etc.) ont choisi d'utiliser les mathématiques du complément à deux. Au fur et à mesure que la technologie des circuits intégrés progressait, pratiquement tous ont adopté la technologie du complément à deux. Les processeurs x86 , m68k , Power ISA , MIPS , SPARC , ARM , Itanium , PA-RISC et DEC Alpha sont tous complémentaires.

Représentation de la magnitude signée

Cette représentation est également appelée représentation « signe–amplitude » ou « signe et grandeur ». Dans cette approche, le signe d'un nombre est représenté par un bit de signe : en définissant ce bit (souvent le bit le plus significatif ) à 0 pour un nombre positif ou un zéro positif, et en le définissant sur 1 pour un nombre négatif ou un zéro négatif. Les bits restants dans le nombre indiquent l'amplitude (ou la valeur absolue ). Par exemple, dans un octet de huit bits , seuls sept bits représentent l'amplitude, qui peut aller de 0000000 (0) à 1111111 (127). Ainsi, des nombres allant de -127 ₁₀ à +127 ₁₀ peuvent être représentés une fois que le bit de signe (le huitième bit) est ajouté. Par exemple, −43 ₁₀ encodé dans un octet de huit bits est 1 0101011 tandis que 43 ₁₀ est 0 0101011. L'utilisation de la représentation de magnitude signée a de multiples conséquences, ce qui les rend plus complexes à mettre en œuvre :

Il existe deux façons de représenter zéro, 00000000 (0) et 10000000 ( -0 ).
L'addition et la soustraction nécessitent un comportement différent en fonction du bit de signe, tandis que le complément à un peut ignorer le bit de signe et effectuer simplement un report de fin, et le complément à deux peut ignorer le bit de signe et dépendre du comportement de débordement.
La comparaison nécessite également d'inspecter le bit de signe, alors que dans le complément à deux, on peut simplement soustraire les deux nombres et vérifier si le résultat est positif ou négatif.
Le nombre négatif minimum est de -127 au lieu de -128 dans le cas du complément à deux.

Cette approche est directement comparable à la manière courante de montrer un signe (en plaçant un « + » ou un « - » à côté de la magnitude du nombre). Certains premiers ordinateurs binaires (par exemple, IBM 7090 ) utilisent cette représentation, peut-être en raison de sa relation naturelle avec l'usage courant. La magnitude signée est la façon la plus courante de représenter la mantisse en valeurs à virgule flottante .

Complément à un

Complément à un de huit bits
Valeur binaire	Interprétation du complément à un	Interprétation non signée
00000000	+0	0
0000001	1	1
??	??	??
01111101	125	125
01111110	126	126
01111111	127	127
10000000	−127	128
10000001	-126	129
10000010	−125	130
??	??	??
11111101	-2	253
11111110	-1	254
11111111	−0	255

Alternativement, un système connu sous le nom de complément à un peut être utilisé pour représenter des nombres négatifs. La forme de complément à un d'un nombre binaire négatif est le NON au niveau du bit qui lui est appliqué, c'est-à-dire le "complément" de son homologue positif. Comme la représentation en signe et en grandeur, le complément à un a deux représentations de 0 : 00000000 (+0) et 11111111 ( −0 ).

A titre d'exemple, la forme complément à un de 00101011 (43 ₁₀ ) devient 11010100 (−43 ₁₀ ). La plage de nombres signés utilisant le complément à un est représentée par −(2 ^{N −1} − 1) à (2 ^{N −1} − 1) et ±0. Un octet conventionnel de huit bits est compris entre -127 ₁₀ et +127 _{10, le} zéro étant soit 00000000 (+0) ou 11111111 (-0).

Pour additionner deux nombres représentés dans ce système, on fait une addition binaire classique, mais il faut ensuite faire un report en boucle : c'est-à-dire ajouter tout report résultant dans la somme résultante. Pour voir pourquoi cela est nécessaire, considérons l'exemple suivant montrant le cas de l'addition de -1 (11111110) à +2 (0000010) :

    binary    decimal
   11111110     −1
+  00000010     +2
───────────     ──
 1 00000000      0   ← Not the correct answer
          1     +1   ← Add carry
───────────     ──
   00000001      1   ← Correct answer

Dans l'exemple précédent, la première addition binaire donne 00000000, ce qui est incorrect. Le résultat correct (00000001) n'apparaît que lorsque le report est rajouté.

Une remarque sur la terminologie : le système est appelé « complément à un » parce que la négation d'une valeur positive x (représentée par le NON au niveau du bit de x ) peut également être formée en soustrayant x de la représentation du complément à un de zéro qui est une longue séquence de uns (−0). L'arithmétique du complément à deux, d'autre part, forme la négation de x en soustrayant x d'une seule grande puissance de deux qui est congrue à +0. Par conséquent, les représentations du complément à un et du complément à deux de la même valeur négative différeront de un.

Notez que la représentation en complément à un d'un nombre négatif peut être obtenue à partir de la représentation signe-amplitude simplement en complétant la grandeur au niveau du bit (en inversant tous les bits après le premier). Par exemple, le nombre décimal -125 avec sa représentation signe-grandeur 11111101 peut être représenté sous forme de complément à un par 10000010.

Complément à deux

Complément à deux de huit bits
Valeur binaire	Interprétation du complément à deux	Interprétation non signée
00000000	0	0
0000001	1	1
??	??	??
01111110	126	126
01111111	127	127
10000000	-128	128
10000001	−127	129
10000010	-126	130
??	??	??
11111110	-2	254
11111111	-1	255

Les problèmes de représentations multiples de 0 et la nécessité du report final sont contournés par un système appelé complément à deux . En complément à deux, les nombres négatifs sont représentés par le motif binaire qui est supérieur d'un (dans un sens non signé) au complément à un de la valeur positive.

En complément à deux, il n'y a qu'un seul zéro, représenté par 00000000. La négation d'un nombre (négatif ou positif) se fait en inversant tous les bits, puis en ajoutant un à ce résultat. Cela reflète en fait la structure en anneau sur tous les entiers modulo 2 ^N : . L'addition d'une paire d'entiers en complément à deux est la même que l'addition d'une paire de nombres non signés (sauf pour la détection de débordement , si cela est fait) ; il en est de même pour la soustraction et même pour les N bits de poids faible d'un produit (valeur de multiplication). Par exemple, une addition de complément à deux de 127 et -128 donne le même motif binaire qu'une addition non signée de 127 et 128, comme on peut le voir à partir de la table de complément à deux de 8 bits. $\mathbb {Z} /2^{N}\mathbb {Z}$

Une méthode plus simple pour obtenir la négation d'un nombre en complément à deux est la suivante :

	Exemple 1	Exemple 2
1. En partant de la droite, trouvez le premier "1"	0010100 1	00101 1 00
2. Inversez tous les bits à gauche de ce "1"	1101011 1	11010 100

Deuxième méthode :

Inverser tous les bits par le nombre
Ajoute un

Exemple : pour +2, qui est 0000010 en binaire (le caractère ~ est l' opérateur C NON au niveau du bit , donc ~X signifie "inverser tous les bits de X") :

~0000010 → 11111101
11111101 + 1 → 11111110 (−2 en complément à deux)

Décalage binaire

Excès de huit bits-128
Valeur binaire	Excès-128 interprétation	Interprétation non signée
00000000	-128	0
0000001	−127	1
??	??	??
01111111	-1	127
10000000	0	128
10000001	1	129
??	??	??
11111111	+127	255

En binaire décalé (également appelé excès- K ou représentation biaisée), un nombre signé n est représenté par le motif binaire correspondant au nombre non signé n + K , K étant la valeur de biais ou décalage . Ainsi 0 est représenté par K , et − K est représenté par un motif binaire entièrement à zéro. Cela peut être vu comme une légère modification et la généralisation du complément à deux mentionné ci - dessus, qui est pratiquement la franchise prévue (2 ^{N -1} ) représentation avec négation bit le plus significatif .

Les représentations biaisées sont maintenant principalement utilisées pour l'exposant des nombres à virgule flottante . La norme à virgule flottante IEEE 754 définit le champ exposant d'un nombre simple précision (32 bits) comme un champ excédent-127 de 8 bits . Le champ d'exposant à double précision (64 bits) est un champ en excès de 1023 de 11 bits ; voir biais exposant . Il était également utilisé pour les nombres décimaux codés en binaire en excès-3 .

Base -2

Dans les systèmes de nombres binaires conventionnels, la base, ou base , est 2; ainsi, le bit le plus à droite représente 2 ⁰ , le bit suivant représente 2 ¹ , le bit suivant 2 ² , et ainsi de suite. Cependant, un système de nombres binaires en base -2 est également possible. Le bit le plus à droite représente (-2) ⁰ = +1 , le bit suivant représente (-2) ¹ = -2 , le bit suivant (-2) ² = +4 et ainsi de suite, avec signe alterné. Les nombres qui peuvent être représentés avec quatre bits sont indiqués dans le tableau de comparaison ci-dessous.

La plage de nombres pouvant être représentée est asymétrique. Si le mot a un nombre pair de bits, l'amplitude du plus grand nombre négatif pouvant être représenté est deux fois plus grande que le plus grand nombre positif pouvant être représenté, et vice versa si le mot a un nombre impair de bits.

Tableau de comparaison

Le tableau suivant montre les entiers positifs et négatifs qui peuvent être représentés à l'aide de quatre bits.

Représentations d'entiers à quatre bits
Décimal	Non signé	Signe et grandeur	Complément à un	Complément à deux	Excès-8 (biaisé)	Base -2
+16	N / A	N / A	N / A	N / A	N / A	N / A
+15	1111	N / A	N / A	N / A	N / A	N / A
+14	1110	N / A	N / A	N / A	N / A	N / A
+13	1101	N / A	N / A	N / A	N / A	N / A
+12	1100	N / A	N / A	N / A	N / A	N / A
+11	1011	N / A	N / A	N / A	N / A	N / A
+10	1010	N / A	N / A	N / A	N / A	N / A
+9	1001	N / A	N / A	N / A	N / A	N / A
+8	1000	N / A	N / A	N / A	N / A	N / A
+7	0111	0111	0111	0111	1111	N / A
+6	0110	0110	0110	0110	1110	N / A
+5	0101	0101	0101	0101	1101	0101
+4	0100	0100	0100	0100	1100	0100
+3	0011	0011	0011	0011	1011	0111
+2	0010	0010	0010	0010	1010	0110
+1	0001	0001	0001	0001	1001	0001
+0	0000	0000	0000	0000	1000	0000
−0	0000	1000	1111	0000	1000	0000
-1	N / A	1001	1110	1111	0111	0011
-2	N / A	1010	1101	1110	0110	0010
-3	N / A	1011	1100	1101	0101	1101
-4	N / A	1100	1011	1100	0100	1100
-5	N / A	1101	1010	1011	0011	1111
-6	N / A	1110	1001	1010	0010	1110
-7	N / A	1111	1000	1001	0001	1001
-8	N / A	N / A	N / A	1000	0000	1000
-9	N / A	N / A	N / A	N / A	N / A	1011
-10	N / A	N / A	N / A	N / A	N / A	1010
-11	N / A	N / A	N / A	N / A	N / A	N / A

Même tableau, vu de "compte tenu de ces bits binaires, quel est le nombre tel qu'interprété par le système de représentation":

Binaire	Non signé	Signe et grandeur	Complément à un	Complément à deux	Excès-8	Base -2
0000	0	0	0	0	-8	0
0001	1	1	1	1	-7	1
0010	2	2	2	2	-6	-2
0011	3	3	3	3	-5	-1
0100	4	4	4	4	-4	4
0101	5	5	5	5	-3	5
0110	6	6	6	6	-2	2
0111	7	7	7	7	-1	3
1000	8	−0	-7	-8	0	-8
1001	9	-1	-6	-7	1	-7
1010	dix	-2	-5	-6	2	-10
1011	11	-3	-4	-5	3	-9
1100	12	-4	-3	-4	4	-4
1101	13	-5	-2	-3	5	-3
1110	14	-6	-1	-2	6	-6
1111	15	-7	−0	-1	7	-5

Autres systèmes

Le "codage en zigzag" des tampons de protocole de Google est un système similaire au signe et à la grandeur, mais utilise le bit le moins significatif pour représenter le signe et a une seule représentation de zéro. Cela permet à un codage de quantité de longueur variable destiné aux entiers non négatifs (non signés) d'être utilisé efficacement pour les entiers signés.

Une méthode similaire est utilisée dans les normes de compression vidéo H.264/MPEG-4 AVC et H.265 High Efficiency Video Coding pour étendre le codage exponentiel-Golomb aux nombres négatifs. Dans cette extension, le bit le moins significatif est presque un bit de signe ; zéro a le même bit le moins significatif (0) que tous les nombres négatifs. Ce choix a pour résultat que le nombre positif représentable de plus grande amplitude est supérieur d'une unité au nombre négatif de plus grande amplitude, contrairement au complément à deux ou au codage en zig-zag des tampons de protocole.

Une autre approche consiste à donner à chaque chiffre un signe, ce qui donne la représentation à chiffres signés . Par exemple, en 1726, John Colson a préconisé de réduire les expressions à de « petits nombres », les chiffres 1, 2, 3, 4 et 5. En 1840, Augustin Cauchy a également exprimé sa préférence pour de tels nombres décimaux modifiés pour réduire les erreurs de calcul.

Voir également

Les références

Ivan Flores, La logique de l'arithmétique informatique , Prentice-Hall (1963)
Israel Koren, algorithmes arithmétiques informatiques , AK Peters (2002), ISBN 1-56881-160-8

Languages

In other projects