Qu’est-ce que “Complément de 2”?

Je suis dans un cours sur les systèmes informatiques et j’ai eu du mal , en partie, avec Two Complement . Je veux comprendre, mais tout ce que j’ai lu n’a pas rassemblé la photo pour moi. J’ai lu l’ article de Wikipedia et divers autres articles, y compris mon livre de texte .

Par conséquent, je voulais lancer cet article sur le wiki de la communauté pour définir le complément de Two, comment l’utiliser et comment il peut affecter les nombres lors d’opérations telles que les transtypages (signés ou non) et les opérations de décalage .

Ce que j’espère, c’est une définition claire et concise, facilement compréhensible par un programmeur.

    Le complément de Two est un moyen astucieux de stocker des entiers afin que les problèmes mathématiques courants soient très simples à mettre en œuvre.

    Pour comprendre, il faut penser aux nombres en binary.

    Il dit essentiellement,

    • pour zéro, utilisez tous les 0.
    • pour les entiers positifs, commencez à compter, avec un maximum de 2 (nombre de bits – 1) -1.
    • pour les entiers négatifs, faites exactement la même chose, mais changez le rôle des 0 et des 1 (donc au lieu de commencer par 0000, commencez par 1111 – c’est la partie “complément”).

    Essayons avec un mini-octet de 4 bits (nous l’appellerons un quartet – 1/2 octet).

    • 0000 – zéro
    • 0001 – un
    • 0010 – deux
    • 0011 – trois
    • 0100 à 0111 – quatre à sept

    C’est aussi loin que possible. 2 3 -1 = 7.

    Pour les négatifs:

    • 1111 – négatif
    • 1110 – deux négatifs
    • 1101 – négatif trois
    • 1100 à 1000 – négatif quatre à négatif huit

    Notez que vous obtenez une valeur supplémentaire pour les négatifs ( 1000 = -8) que vous n’utilisez pas pour les positifs. C’est parce que 0000 est utilisé pour zéro. Cela peut être considéré comme la ligne numérique des ordinateurs.

    Distinguer les nombres positifs et négatifs

    En faisant cela, le premier bit obtient le rôle du bit “sign”, car il peut être utilisé pour distinguer les valeurs décimales positives et négatives. Si le bit le plus significatif est 1 , alors le binary peut être considéré comme négatif, alors que si le bit le plus significatif (le plus à gauche) est 0 , vous pouvez dire discerner que la valeur décimale est positive.

    Je me demande si cela pourrait être mieux expliqué que l’article de Wikipedia.

    Le problème de base que vous essayez de résoudre avec la représentation du complément à deux est le problème du stockage des entiers négatifs.

    Considérons d’abord un entier non signé stocké sur 4 bits. Vous pouvez avoir le suivant

     0000 = 0 0001 = 1 0010 = 2 ... 1111 = 15 

    Ceux-ci ne sont pas signés car il n’y a aucune indication de leur caractère négatif ou positif.

    Signer l’ampleur et l’excès de notation

    Pour stocker des nombres négatifs, vous pouvez essayer un certain nombre de choses. Tout d’abord, vous pouvez utiliser la notation d’amplitude de signe qui assigne le premier bit comme bit de signe pour représenter +/- et les bits restants pour représenter la magnitude. Donc, en utilisant 4 bits à nouveau et en supposant que 1 signifie – et 0 signifie + alors vous avez

     0000 = +0 0001 = +1 0010 = +2 ... 1000 = -0 1001 = -1 1111 = -7 

    Donc, vous voyez le problème là-bas? Nous avons des valeurs positives et négatives 0. Le plus gros problème est d’append et de soustraire des nombres binarys. Les circuits à append et à soustraire en utilisant la magnitude du signe seront très complexes.

    Quel est

     0010 1001 + ---- 

    ?

    Un autre système est la notation excessive . Vous pouvez stocker des nombres négatifs, vous débarrasser du problème des deux zéros, mais l’addition et la soustraction restnt difficiles.

    Ainsi vient le complément à deux. Maintenant, vous pouvez stocker les entiers positifs et négatifs et effectuer l’arithmétique avec une relative facilité. Il existe un certain nombre de méthodes pour convertir un nombre en complément à deux. En voici un.

    Convertir décimal en complément à deux

    1. Convertissez le nombre en binary (ignorez le signe pour l’instant), par exemple 5 est 0101 et -5 est 0101

    2. Si le nombre est un nombre positif, vous avez terminé. par exemple 5 est 0101 en binary en utilisant la notation à deux complément.

    3. Si le nombre est négatif alors

      3.1 trouver le complément (inverser 0 et 1) par exemple -5 est 0101 donc trouver le complément est 1010

      3.2 Ajouter 1 au complément 1010 + 1 = 1011. Par conséquent, -5 en complément à deux est 1011.

    Alors, que faire si vous vouliez faire 2 + (-3) en binary? 2 + (-3) est -1. Que feriez-vous si vous utilisiez une magnitude de signe pour append ces chiffres? 0010 + 1101 =?

    En utilisant le complément à deux, considérez comme ce serait facile.

      2 = 0010 -3 = 1101 + ------------- -1 = 1111 

    Conversion du complément à deux en décimal

    Conversion de 1111 en décimal:

    1. Le nombre commence par 1, il est donc négatif, nous trouvons donc le complément de 1111, soit 0000.

    2. Ajoutez 1 à 0000 et nous obtenons 0001.

    3. Convertir 0001 en décimal, ce qui est 1.

    4. Appliquez le signe = -1.

    Tada!

    Comme la plupart des explications que j’ai vues, celles qui précèdent expliquent comment travailler avec le complément à 2, mais n’expliquent pas vraiment ce qu’elles sont mathématiquement. Je vais essayer de le faire, au moins pour les nombres entiers, et je couvrirai certains aspects qui sont probablement familiers en premier.

    Rappelez-vous comment cela fonctionne pour les décimales:
    2345
    est une façon d’écrire
    2 × 10 3 + 3 × 10 2 + 4 × 10 1 + 5 × 10 0 .

    De la même manière, binary est une manière d’écrire des nombres en utilisant juste 0 et 1 en suivant la même idée générale, mais en remplaçant les 10 ci-dessus par des 2. Puis en binary,
    1111
    est une façon d’écrire
    1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0
    et si vous y parvenez, cela équivaut à 15 (base 10). C’est parce que c’est
    8 + 4 + 2 + 1 = 15.

    Tout va bien pour les chiffres positifs. Cela fonctionne même pour les nombres négatifs si vous voulez juste coller un signe moins devant eux, comme le font les humains avec les nombres décimaux. Cela peut même se faire dans des ordinateurs, en quelque sorte, mais je n’ai pas vu un tel ordinateur depuis le début des années 70. Je vais laisser les raisons d’une discussion différente.

    Pour les ordinateurs, il s’avère plus efficace d’utiliser une représentation du complément pour les nombres négatifs. Et voici quelque chose qui est souvent négligé. Les notations de complément impliquent une sorte d’inversion des chiffres du nombre, même les zéros implicites qui précèdent un nombre positif normal. C’est gênant, car la question se pose: tous? Cela pourrait être un nombre infini de chiffres à considérer.

    Heureusement, les ordinateurs ne représentent pas l’infini. Les nombres sont limités à une longueur (ou largeur, si vous préférez). Revenons donc aux nombres binarys positifs, mais avec une taille particulière. J’utiliserai 8 chiffres (“bits”) pour ces exemples. Donc, notre nombre binary serait vraiment
    00001111
    ou
    0 × 2 7 + 0 × 2 6 + 0 × 2 5 + 0 × 2 4 + 1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0

    Pour former le négatif du complément à 2, nous complétons d’abord tous les chiffres (binarys) pour former
    11110000
    et append 1 pour former
    11110001
    mais comment pouvons-nous comprendre cela pour signifier -15?

    La réponse est que nous changeons la signification du bit de poids fort (le plus à gauche). Ce bit sera un 1 pour tous les nombres négatifs. Le changement sera de changer le signe de sa consortingbution à la valeur du nombre dans lequel il apparaît. Alors maintenant, notre 11110001 est censé représenter
    1 × 2 7 + 1 × 2 6 + 1 × 2 5 + 1 × 2 4 + 0 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0
    Notez que “-” devant cette expression? Cela signifie que le bit de signe porte le poids -2 7 , soit -128 (base 10). Toutes les autres positions conservent le même poids que dans les nombres binarys non signés.

    Travailler notre -15, c’est
    -128 + 64 + 32 + 16 + 1
    Essayez-le sur votre calculasortingce. c’est -15.

    Parmi les trois principales façons dont les nombres négatifs ont été représentés dans les ordinateurs, le complément à 2 est incontournable pour des raisons pratiques. Il y a une bizarrerie, cependant. Comme il est binary, il doit y avoir un nombre pair de combinaisons de bits possibles. Chaque nombre positif peut être associé à son négatif, mais il n’y a qu’un seul zéro. Négocier un zéro vous donne zéro. Donc, il y a une autre combinaison, le numéro avec 1 dans le bit de signe et 0 partout ailleurs. Le nombre positif correspondant ne correspondrait pas au nombre de bits utilisés.

    Ce qui est encore plus étrange à propos de ce nombre, c’est que si vous essayez d’en former un positif en le complétant et en en ajoutant un, vous obtenez le même nombre négatif. Il semble naturel que zéro le fasse, mais cela est inattendu et pas du tout le comportement auquel nous sums habitués car les ordinateurs mis à part, nous pensons généralement à une offre illimitée de chiffres, pas à cette arithmétique de longueur fixe.

    C’est comme la pointe d’un iceberg de bizarreries. Il y a plus de choses en attente sous la surface, mais cela suffit pour cette discussion. Vous pourriez probablement trouver plus si vous recherchez “débordement” pour l’arithmétique à virgule fixe. Si vous voulez vraiment y entrer, vous pouvez également faire des recherches sur «l’arithmétique modulaire».

    Le complément de 2 est très utile pour trouver la valeur d’un binary, cependant j’ai pensé à un moyen beaucoup plus concis de résoudre un tel problème (jamais vu quelqu’un d’autre l’a publié):

    prendre un binary, par exemple: 1101 qui est [en supposant que l’espace “1” est le signe] égal à -3 .

    en utilisant le complément à 2, nous ferions ceci … retourner 1101 à 0010 … append 0001 + 0010 ===> nous donne 0011. 0011 en binary positif = 3. donc 1101 = -3 !

    Ce que j’ai réalisé:

    au lieu de tous les renvois et ajouts, vous pouvez simplement faire la méthode de base pour résoudre un binary positif (disons 0101) soit (2 3 * 0) + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = 5.

    Faites exactement le même concept avec un négatif! (Avec une petite torsion)

    prenez 1101, par exemple:

    pour le premier nombre au lieu de 2 3 * 1 = 8 , faites – (2 3 * 1) = -8 .

    puis continuez comme d’habitude en faisant -8 + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = -3

    Imaginez que vous ayez un nombre fini de bits / sortingts / chiffres / peu importe. Vous définissez 0 comme tous les chiffres étant 0 et comptez naturellement vers le haut:

     00 01 02 .. 

    Finalement, vous allez déborder.

     98 99 00 

    Nous avons deux chiffres et pouvons représenter tous les nombres de 0 à 100. Tous ces nombres sont positifs! Supposons que nous voulons représenter des nombres négatifs aussi?

    Ce que nous avons vraiment, c’est un cycle. Le nombre avant 2 est 1. Le nombre avant 1 est 0. Le nombre avant 0 est … 99 .

    Donc, pour simplifier, disons que tout nombre supérieur à 50 est négatif. “0” à “49” représentent 0 à 49. “99” est -1, “98” est -2, … “50” est -50.

    Cette représentation est le complément à dix . Les ordinateurs utilisent généralement le complément à deux , ce qui est identique, sauf en utilisant des bits au lieu de chiffres.

    La bonne chose à propos de dix complément est que l’addition ne fonctionne que . Vous n’avez rien à faire de spécial pour append des nombres positifs et négatifs!

    Deux compléments sont découverts en ajoutant un à un complément du nombre donné. Disons que nous devons trouver deux compléments de 10101 puis trouver ses compléments, c’est-à-dire 01010 append 1 à ce résultat, soit 01010+1=01011 , qui est la réponse finale.

    Permet d’obtenir la réponse 10 – 12 sous forme binary en utilisant 8 bits: ce que nous allons vraiment faire est 10 + (-12)

    Nous devons obtenir la partie compliment de 12 pour le soustraire de 10. 12 en binary est 00001100. 10 en binary est 00001010.

    Pour obtenir la partie complémentaire de 12, il suffit d’inverser tous les bits, puis d’append 1. 12 en binary inversé est 11110011. C’est aussi le code Inverse (son complément). Maintenant, nous devons en append un, qui est maintenant 11110100.

    Donc 11110100 est le complément de 12! Facile quand on y pense de cette façon.

    Maintenant, vous pouvez résoudre la question ci-dessus de 10 à 12 sous forme binary.

     00001010 11110100 ----------------- 11111110 

    En regardant le système de complément à deux d’un sharepoint vue mathématique, cela a vraiment du sens. En dix points, l’idée est essentiellement d’isoler la différence.

    Exemple: 63 – 24 = x

    Nous ajoutons le complément de 24 qui est vraiment juste (100 – 24). Donc, tout ce que nous faisons, c’est d’append 100 des deux côtés de l’équation.

    Maintenant, l’équation est la suivante: 100 + 63 – 24 = x + 100, c’est pourquoi nous supprimons les 100 (ou 10 ou 1000 ou peu importe).

    En raison de la situation peu commode de devoir soustraire un nombre d’une longue chaîne de zéros, nous utilisons un système de «complément à base réduite», dans le système décimal, complément à neuf.

    Lorsqu’on nous présente un nombre soustrait d’une grande chaîne de neuf, il suffit d’inverser les chiffres.

    Exemple: 99999 – 03275 = 96724

    C’est la raison pour laquelle, après neuf compléments, nous ajoutons 1. Comme vous le savez probablement en mathématiques chez les enfants, 9 devient 10 en «volant» 1. Donc, en gros, il ne s’agit que de dix compléments.

    En binary, le complément à deux est adapté au complément à dix, tandis que le complément à neuf est complémentaire. La principale différence est qu’au lieu d’essayer d’isoler la différence avec des puissances de dix (en ajoutant 10, 100, etc. dans l’équation), nous essayons d’isoler la différence avec des puissances de deux.

    C’est pour cette raison que nous inversons les bits. Tout comme la façon dont notre menu est une chaîne de neuf en décimal, notre menu est une chaîne de bits en binary.

    Exemple: 111111 – 101001 = 010110

    Parce que les chaînes de 1 sont en dessous d’une belle puissance de deux, elles «volent» 1 de la différence comme neuf en décimal.

    Lorsque nous utilisons des nombres binarys négatifs, nous disons simplement:

    0000 – 0101 = x

    1111 – 0101 = 1010

    1111 + 0000 – 0101 = x + 1111

    Pour “isoler” x, nous devons append 1 car 1111 est un de 10000 et nous supprimons le premier parce que nous venons de l’append à la différence d’origine.

    1111 + 1 + 0000 – 0101 = x + 1111 + 1

    10000 + 0000 – 0101 = x + 10000

    Il suffit de supprimer 10000 des deux côtés pour obtenir x, c’est l’algèbre de base.

    Beaucoup des réponses expliquent bien pourquoi le complément à deux est utilisé pour représenter un nombre négatif, mais ne nous dit pas quel est le nombre à complément à deux, en particulier pas pourquoi un «1» est ajouté, et souvent ajouté de manière erronée.

    La confusion provient d’une mauvaise compréhension de la définition d’un nombre complémentaire. Un complément est la partie manquante qui rendrait quelque chose complet.

    Le complément de base d’un nombre à n chiffres x dans la base b est, par définition, b ^ nx. En binary 4 est représenté par 100, ce qui a 3 chiffres (n = 3) et une base de 2 (b = 2). Donc son complément de base est b ^ nx = 2 ^ 3-4 = 8-4 = 4 (ou 100 en binary).

    Cependant, en binary, obtenir un complément à la base n’est pas aussi facile que d’obtenir son complément à base diminuée, qui est défini comme (b ^ n-1) -y, seulement 1 de moins que celui du complément à la base. Pour obtenir un complément de base diminué, il vous suffit de retourner tous les chiffres.

    100 -> 011 (complément à la base diminué)

    pour obtenir le complément de radix (deux), nous ajoutons simplement 1, selon la définition définie.

    011 +1 -> 100 (complément à deux).

    Maintenant, avec cette nouvelle compréhension, prenons l’exemple de Vincent Ramdhanie (voir la deuxième réponse ci-dessus)

    / * début de Vincent

    Conversion de 1111 en décimal:

    Le nombre commence par 1, il est donc négatif, nous trouvons donc le complément de 1111, qui est 0000. Ajoutez 1 à 0000 et nous obtenons 0001. Convertissez 0001 en décimal, ce qui est 1. Appliquez le signe = -1. Tada!

    fin de Vincent * /

    Doit être compris comme

    Le nombre commence par 1, il est donc négatif. Donc, nous soaps que c’est un complément à deux d’une certaine valeur x. Pour trouver le x représenté par son complément à deux, il faut d’abord trouver son complément à 1.

    complément à deux de x: 1111 complément de x: 1111-1 -> 1110; x = 0001, (retourner tous les chiffres)

    appliquer le signe – et la réponse = -x = -1.

    C’est un moyen astucieux de coder des entiers négatifs de telle sorte qu’environ la moitié de la combinaison de bits d’un type de données est réservée aux entiers négatifs et que l’ajout de la plupart des entiers négatifs avec leurs entiers positifs correspondants entraîne un dépassement de capacité. cela laisse le résultat à zéro binary.

    Donc, en complément à 2 si on est 0x0001 alors -1 est 0x1111, car cela se traduira par une sum combinée de 0x0000 (avec un débordement de 1).

    Compléments de 2: Lorsque nous en appendons un avec les compléments du numéro 1, nous obtiendrons les 2 compléments. Par exemple: 100101 son complément à 1 est 011010 et le complément à 2 est 011010 + 1 = 011011 (en ajoutant un avec le complément à 1) Pour plus d’informations, cet article l’explique graphiquement.

    J’ai aimé la réponse de Lavinio, mais les changements de bits ajoutent de la complexité. Il y a souvent un choix de bits de déplacement tout en respectant le bit de signe ou en ne respectant pas le bit de signe. C’est le choix entre traiter les nombres comme signés (-8 à 7 pour un quartet, -128 à 127 pour les octets) ou les nombres non signés sur toute la plage (0 à 15 pour les quartets, 0 à 255 pour les octets).

    J’ai eu le même problème il y a quelques semaines. J’ai fini par lire à ce sujet en ligne à partir de diverses sources, en essayant de rassembler les pièces et en écrivant à ce sujet, juste pour m’assurer de bien le comprendre. Nous utilisons deux compléments pour deux raisons principales:

    1. Pour éviter les représentations multiples de 0
    2. Eviter de garder un suivi du bit de retenue (comme dans son complément) en cas de débordement.
    3. Effectuer des opérations simples comme l’addition et la soustraction devient facile.

    Si vous voulez une explication plus détaillée du problème, essayez l’article que j’ai écrit ici . J’espère que cela aide!

    J’ai lu une explication fantastique sur Reddit en utilisant jng, en utilisant le compteur kilomésortingque comme une analogie.

    entrer la description de l'image ici

    C’est une convention utile. Les mêmes circuits et opérations logiques qui ajoutent / soustraient des nombres positifs en binary fonctionnent toujours sur les nombres positifs et négatifs si vous utilisez la convention. C’est pourquoi elle est si utile et omniprésente.

    Imaginez l’odomètre d’une voiture, il roule à (disons) 99999. Si vous augmentez 00000, vous obtenez 00001. Si vous décrémentez 00000, vous obtenez 99999 (en raison du retournement). Si vous en ajoutez un à 99999, il revient à 00000. Il est donc utile de décider que 99999 représente -1. De même, il est très utile de décider que 99998 représente -2, etc. Vous devez vous arrêter quelque part, et aussi par convention, la moitié supérieure des nombres est considérée comme négative (50000-99999), et la moitié inférieure positive représente elle-même (00000-49999). Par conséquent, le chiffre supérieur compris entre 5 et 9 signifie que le nombre représenté est négatif, et que 0 à 4 signifie que le nombre représenté est positif – exactement le même que le bit supérieur représentant le nombre binary à complément à deux.

    Comprendre cela était difficile pour moi aussi. Une fois que je l’ai eu et que je suis retourné pour relire les articles et les explications des livres (il n’y avait pas d’internet à l’époque), il s’est avéré que beaucoup de ceux qui le décrivaient ne le comprenaient pas vraiment. J’ai ensuite écrit un livre qui enseignait le langage d’assemblage (qui s’est très bien vendu pendant 10 ans).

    Référence: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

    J’inverse tous les bits et ajoute 1. Par programme:

      // in C++11 int _powers[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; int value=3; int n_bits=4; int twos_complement = (value ^ ( _powers[n_bits]-1)) + 1; 

    Vous pouvez également utiliser une calculasortingce en ligne pour calculer la représentation binary du nombre à deux décimales: http://www.convertforfree.com/twos-complement-calculator/

    La réponse la plus simple:

    1111 + 1 = (1) 0000. Donc 1111 doit être -1. Alors -1 + 1 = 0.

    C’est parfait pour comprendre tout cela pour moi.