Comment est-débordement détecté au niveau binaire?

Toutes les fois que vous voulez traiter avec ce genre d'alu points de il ajouter, soustraire, multiplier, etc, commencer avec 2 ou 3 bits, beaucoup plus facile d'obtenir une poignée sur 32 ou 64 bits. après 2 ou 3 bits, qu'il n'importe pas si c'est 22 ou 2200 bits tout cela fonctionne exactement de la même. Fondamentalement, vous pouvez à la main si vous voulez faire une table de tous les opérandes 3 bits et leurs résultats tels que vous pouvez examiner toute la table visuellement, mais une table de tous les opérandes 32 bits contre tous les 32 bits les opérandes et leurs résultats, ne peuvent pas le faire à la main dans un délai raisonnable et ne peuvent pas examiner toute la table visuellement.

maintenant deux compléments, c'est juste un schéma pour représenter des nombres positifs et négatifs, et ce n'est pas quelque chose d'arbitraire qu'il a une raison, la raison de la folie est que votre logique d'adder (qui est aussi ce que le soustracteur utilise qui est le même genre de chose que le multiplicateur utilise) ne se soucie pas de non signé ou signé. Il ne sait pas la différence. VOUS le programmeur soucis dans mes trois bits du monde de la bit patter 0b111 pourrait être un postitive sept (+7) ou il pourrait être négatif. Même bit pattern, l'alimenter à la logique d'ajout et la même chose sort, et la réponse qui sort, je peux choisir d'interpréter comme non signé ou deux complément (à condition que j'interprète les opérandes et le résultat tout comme soit non signé ou tous comme deux complément). Le complément de deux a également la caractéristique que pour les nombres négatifs le bit le plus significatif (msbit) est mis, pour les nombres positifs c'est zéro. Donc ce n'est pas signe plus magnitude mais nous parlons encore du msbit étant le bit de signe, parce qu'à l'exception de deux nombres spéciaux qui est ce qu'il nous dit, le signe du nombre, les autres bits nous disent en fait la magnitude qu'ils ne sont tout simplement pas une magnitude non signée comme vous pourriez avoir dans la notation de signe+magnitude.

Donc, la clé de cette question est de comprendre vos limites. Pour un nombre 3 bits non signé notre gamme est de 0 à 7, 0b000 à 0b111. pour une interprétation à 3 bits (complément twos) notre gamme est de -4 à +3 (0b100 à 0b011). Pour l'instant nous nous limitons à 3 bits si vous ajoutez 7+1, 0b111 + 0b001 = 0b1000 mais nous avons seulement un système de 3 bits qui est 0b000, 7+1 = 8, nous ne pouvons pas représenter 8 dans notre système donc c'est un débordement, parce que nous nous trouvons à interpréter les bits comme non signé, nous regardons le "débordement non signé" qui est également connu sous le port bit ou drapeau. Maintenant, si nous prenons ces mêmes bits mais les interprétons comme signés, puis 0b111 (-1) + 0b001 (+1) = 0b000 (0). Moins un plus un, c'est zéro. Aucun débordement, le "débordement signé" n'est pas défini...Qu'est-ce que la signature de débordement?

tout d'abord, qu'est-ce que le "débordement non signé"?

la raison pour laquelle "tout fonctionne de la même façon", peu importe le nombre de bits que nous avons dans nos registres, n'est pas différente des mathématiques de l'école primaire avec des nombres de base 10 (décimaux). Si vous ajoutez 9 + 1 qui sont tous les deux dans la colonne uns vous dites 9 + 1 = Zéro porter le 1. vous portez un plus à la colonne des dizaines puis 1 plus 0 plus 0 (Vous avez rempli deux zéros dans la colonne des dizaines) est 1 porter le zéro. vous avez un 1 dans la colonne des dizaines et un zéro dans ceux de la colonne

  1
  09
 +01
====
  10

et si nous déclarions que nous étions limités aux seuls nombres dans la colonne un, il n'y a pas de place pour une colonne des dizaines. Eh bien ce carry bit étant un non-zéro signifie que nous avons un débordement, pour calculer correctement le résultat nous avons besoin d'une autre colonne, même avec binaire

  111 
   111
 + 001
=======
  1000

7 + 1 = 8, mais nous cant do 8 si nous déclarons un système 3 bits, nous pouvons faire 7 + 1 = 0 avec le port de bit réglé. C'est là la beauté de complément à deux:

  111 
   111
 + 001
=======
   000

si vous regardez l'addition de trois bits ci-dessus, vous ne pouvez pas dire en regardant si c'est 7 + 1 = 0 avec le bit de portage ou si c'est -1 + 1 = 0.

donc pour l'addition non signée, Comme nous le savons depuis l'école primaire qu'un report dans la colonne suivante de quelque chose d'autre que zéro signifie que nous avons débordé que beaucoup des espaces réservés et besoin de plus d'espace réservé, une colonne, d'organiser la réponse réelle.

débordement signé. Le type de réponse académique est si le carry in de la colonne msbit ne correspond pas au carry out. prenons quelques exemples dans notre de 3 bits monde. Ainsi, avec deux compléments, nous sommes limités à -4 à +3. donc si on ajoute -2 + -3 = -5 ça ne marchera pas correctement? Pour comprendre ce que moins deux est nous faisons un invert et Ajouter un 0b010, inversé 0b101, ajouter un 0b110. moins trois c'est 0b011 - > 0b100 -> 0b101

donc maintenant, nous pouvons faire ceci:

  abc
  100 
   110
 + 100
======
   010

si vous regardez le numéro sous le b qui est le "carry in" à la colonne msbit, le numéro sous le a le 1, est le carry out, ces deux-là ne correspondent pas donc nous savons qu'il y a un "signed overflow"

essayons 2 + 2 = 4

  abc
  010
   010
 + 010
======
   100

vous pouvez dire mais cela semble juste, bien sûr non signé, mais nous faisons des calculs signés ici, donc le résultat est en fait un -4 pas un 4 positif. 2 + 2 != - 4. le transporter dans ce qui est sous le b est à 1, le report de la msbit est un zéro, à la réaliser en et les ne correspondent pas. signé débordement.

il y a un raccourci pour calculer le débordement signé sans avoir à regarder le carry in (ou le carry out). si ( msbit(opa) == msbit(opb) ) && ( msbit(res) != msbit (opb)) dépassement signé, sinon pas de dépassement signé. opa être un opérande, opb l'autre et res le résultat.

   010
 + 010
======
   100

Prenez ceci +2 + +2 = - 4. msbit(opa) et msbit (opb) sont égaux, et le résultat msbit n'est pas égal à msbit opb, donc il s'agit d'un débordement signé. Vous pourriez y penser en utilisant cette table

x ab cr 
0 00 00
0 01 01
0 10 01
0 11 10 signed overflow
1 00 01 signed overflow
1 01 10
1 10 10
1 11 11

ce tableau est toutes les combinaisons possibles si carry in bit, operand a, operand b, carry out et résultat bit pour une colonne simple tourner la tête à gauche pour voir ce x est le carry in, Les colonnes a et b sont les deux opérandes. cr comme une paire est le résultat xab de 011 moyens 0+1+1 = 2 décimales qui est binaire 0b10. Donc prendre la règle qui nous a été dictée, que si le carry in et le carry out ne correspondent pas, c'est un débordement signé. Eh bien, les deux cas où l'article dans la colonne x ne correspond pas à l'article dans la colonne c sont indiqués. ce sont les cas où les entrées a et b correspondent l'une à l'autre, mais le bit de résultat est le contraire de a et B. Donc, en supposant que la règle est correcte ce raccourci rapide qui ne nécessite pas de savoir ce que sont les bits de transport, vous dira s'il y avait un signé débordement.

Maintenant vous lisez un livre de H&P. Ce qui signifie probablement mips ou dlx, ni mips ni dlx ne traitent avec carry et signed flags comme le font la plupart des autres processeurs. mips n'est pas le meilleur premier jeu D'instructions IMO principalement pour cette raison, leur approche n'est pas erronée en aucune façon, mais étant l'oddball, vous passerez l'éternité à penser différemment et avoir à traduire lorsque vous allez à la plupart des autres processeurs. Où si vous avez appris les drapeaux typiques znvc (zero flag, négatif drapeau, v=signé débordement, c=porter ou non signé de débordement), alors vous n'avez qu'à traduire quand va mips. Normalement, ceux-ci sont calculés sur chaque opération alu (pour les processeurs de type non mips), vous verrez le débordement signé et non signé être calculé pour ajouter et soustraire. (Je suis habitué à un vieux mips, peut-être que cette génération de livres et le jeu d'instructions actuel a quelque chose de différent). L'appeler addu ajouter non signé dès le début de mips après avoir appris tout ce qui précède sur la façon dont un Adder circuit ne se soucie pas signé vs non signé, est un énorme problème avec mips il vous met vraiment dans le mauvais état d'esprit pour comprendre quelque chose d'aussi simple. On croit qu'il y a une différence entre l'ajout signé et l'ajout non signé lorsqu'il n'y en a pas. Seuls les indicateurs de débordement sont calculés différemment. Maintenant, multipliez, et divisez il y a certainement un complément de deux contre une différence non signée et vous avez idéalement besoin d'une multiplication signée et une multiplication non signée ou vous avez besoin pour faire face à la limitation.

je recommande un exercice simple (en fonction de la force de votre manipulation de bits et de votre complément de deux) que vous pouvez écrire dans un langage de haut niveau. Essentiellement prendre toutes les combinaisons de numéros non signés 0 à 7 ajoutés à 0 à 7 et enregistrer le résultat. Imprimez à la fois en tant que décimal et en tant que binaire (trois bits pour les opérandes, quatre bits pour le résultat) et si le résultat est supérieur à 7. Répétez ceci en utilisant les variables signées nombres -4 à +3 ajouté à -4 à +3. imprimer les décimales avec un signe +/- et le binaire. Si le résultat est inférieur à -4 ou supérieure à +3 impression de débordement. À partir de ces deux tableaux, vous devriez être en mesure de voir que les règles ci-dessus sont vraies. En regardant strictement les patrons de bits opérande et résultat pour la taille permise (trois bits dans ce cas) vous verrez que l'opération d'addition donne le même résultat, même patron de bits pour une paire donnée d'entrées indépendamment de si ces patrons de bits sont considéré comme non signé ou deux compléments. En outre, vous pouvez vérifier que le débordement non signé est lorsque le résultat doit utiliser cette quatrième colonne, Il ya un carry off de la msbit. pour signé lorsque le carry in ne correspond pas au carry out, que vous voyez en utilisant le raccourci en regardant les msbits des opérandes et le résultat. Encore mieux, c'est d'avoir votre programme à faire ces comparaisons et d'imprimer quelque chose. Donc, si vous voyez une note dans votre table que le résultat est supérieur à 7 et une note à votre table le bit 3 est défini dans le résultat, alors vous verrez pour la table non signée qui est toujours le cas (limité à des entrées de 0 à 7). Et le plus compliqué, signed overflow, est toujours quand le résultat est inférieur à -4 et supérieur à 3 et quand les bits supérieurs de l'opérande correspondent et que le bit supérieur du résultat ne correspond pas aux opérandes.

je sais que c'est très long et très élémentaire. Si j'ai totalement manqué la marque ici, s'il vous plaît commenter et je vais supprimer ou réécrire ceci réponse.

l'autre moitié des deux complète la magie. le matériel n'a pas soustraire à la logique. une façon de" convertir "en complément par deux est de"l'inverser et en ajouter un". si je voulais soustraire 3-2 en utilisant le complément de deux ce qui se passe réellement est que c'est la même chose que +3 + (-2) droite, et pour obtenir de +2 à -2 nous inversons et ajoutons un. En regardant notre école primaire de plus, avez-vous remarqué le trou dans la transporter dans la première colonne?

  111H
   111
 + 001
=======
  1000

j'ai mis un H ci-dessus où le trou est. Bien que transporter dans bit est ajouté à l'opérande de droite? notre plus logique n'est pas une entrée adder c'est un trois entrées additionneur oui? la plupart des colonnes doivent ajouter trois nombres d'un bit afin de calculer deux opérandes. Si nous utilisons un trois entrées additionneur sur la première colonne, nous avons une place pour ... pour en ajouter un. Si je voulais soustraire 3 - 2 = 3 + (-2) = 3 + (~2) + 1 qui est:

    1
  011
+ 101
=====

avant de commencer et rempli c'est:

 1111
  011
+ 101
=====
  001

3 - 2 = 1.

Ce que la logique est la suivante:

si add puis carry in = 0; l'opérande b n'est pas inversée, l'carry out n'est pas inversée. si soustract puis carry in = 1; l'opérande b est inversé, le carry out peut être inversé.

l'addition ci - dessus montre un carry out, Je n'ai pas mentionné qu'il s'agissait d'une opération non signée 3-2 = 1. J'ai utilisé deux trucs de complément pour effectuer une opération non signée, parce que là encore, peu importe si j'interprète les opérandes comme signé ou non signé les mêmes règles s'appliquent si vous additionnez ou soustrayez. Pourquoi j'ai dit que le carry out pourrait être inversé est que certains processeurs inversent le carry out et certains dont. il s'agit d'opérations en cascade, en prenant par exemple une logique d'addition 32 bits et en utilisant le drapeau carry et un add avec l'instruction carry ou soustract avec l'instruction borrow créant un 64 bit add ou soustract, ou n'importe quel multiple de la taille du registre de base. supposons que vous ayez deux nombres 64 bits dans un système 32 bits a: b + c:D où a:b est le nombre 64 bits numéro, mais elle est tenue dans les deux registres a et b où a est la moitié supérieure et b est la moitié inférieure. donc a: b + c:d = e:F sur un système 32 bits non signé qui a un bit de carry et ajouter avec carry:

add f,b,d
addc e,a,c

l'add laisse son bit carry out de la voie la plus haute dans le drapeau carry dans le registre d'état, l'instruction addc est add with carry prend les opérandes a+c et si le bit carry est mis, il en ajoute un de plus. A+c+1 Mettre le résultat en e et effectuer dans le carry drapeau,

add f,b,d
addc e,a,c
addc x,y,z

est un ajout de 96 bits, et ainsi de suite. Ici encore quelque chose de très étranger aux mips puisqu'il n'utilise pas de drapeaux comme les autres processeurs. Lorsque l'inverse ou ne pas l'inverse entre pour l'exécution signée est sur la soustraction avec emprunt pour un processeur particulier. pour soustraire:

si soustraire puis carry in = 1; l'opérande b est inversée, l'carry out peut être inversée.

pour soustraire avec l'emprunt vous devez dire si le drapeau de porter de la registre d'état indique un emprunter ensuite la réaliser en est une 0 sinon la réaliser en est une de 1, et vous devez obtenir la mener à bien dans le registre d'état pour indiquer l'emprunter.

en gros pour une normale de soustraire certains processeurs inverser b opérande et continuer sur le chemin et continuer sur le chemin, certains processeurs inverser le b opérande et d'effectuer dans la manière, mais ne pas inverser les mener sur le chemin. Ensuite, lorsque vous voulez faire une branche conditionnelle, vous devez savoir si le transporter flag signifie plus ou moins que (souvent la syntaxe aura une branche si plus grande ou une branche si moins que et parfois vous dire laquelle est la branche simplifiée si carry set ou la branche si carry clear). (si vous ne "obtenez" pas ce que je viens de dire là qui est une autre réponse tout aussi longue qui ne signifie rien tant que vous étudiez mips).