如何在二进制级别检测到溢出？

Question

我正在阅读Hennessey和Patterson的教科书计算机组织和设计(第4版).在225页,他们描述了如何在带符号的2的补码算术中检测到溢出.我甚至无法理解他们在谈论什么.

"我们如何检测[溢出]当它没有发生？显然,添加或从其减去两个32位的数字可以产生需要33位得到充分表达的结果."

当然.并且它不需要34位,因为即使最小的34位数也是最小的33位数的两倍,我们正在添加32位数.

"缺少第33位意味着当溢出发生时,符号位设置为结果的值而不是结果的正确符号."

这是什么意思？符号位设置为结果的"值"...意味着它被设置为好像结果是无符号的？如果是这样,那么缺少第33位会如何呢？

"由于我们只需要一个额外的位,只有符号位可能是错误的."

那就是他们完全失去了我的地方.

我从中得到的是,当添加有符号数时,当且仅当符号位错误时才会出现溢出.因此,如果你添加两个正数并得到负数,或者如果你添加两个负数并获得正数.但我不明白他们的解释.

此外,这仅适用于无符号数字,对吧？如果你要添加带符号的数字,那么检测溢出肯定要简单得多.如果ALU的后半个加法器设置进位,则会出现溢出.

注意:我真的不知道哪些标签适合这里,随意编辑它们.

Answer 1

任何时候你想要处理这些alu项目,它是加,减,乘等,从2或3位数开始,比32位或64位数更容易获得处理.在2或3位之后无论是22位还是2200位都无关紧要,它从外面完全相同.基本上你可以手工制作一个包含所有3位操作数及其结果的表格,以便你可以直观地检查整个表格,但是所有32位操作数对应所有32位操作数及其结果的表格,不能通过在合理的时间内手,不能视觉检查整个表.

现在两个补码,这只是一个表示正数和负数的方案,并且它不是一些任意的东西它有一个理由,疯狂的原因是你的加法器逻辑(这也是减法器使用的是同样的乘数用的东西)不关心未签名或签名.它不知道区别.程序员在我的三位世界中关注位模式0b111可能是7(+7)或者可能是负数.相同的位模式,将其提供给添加逻辑,同样的事情出来了,我可以选择解释为无符号或二进制补码的答案(只要我将操作数和结果全部解释为无符号或全部作为两个补充).二进制补码还具有以下特征:对于负数,设置最高有效位(msbit),对于正数,它为零.所以它不是符号加幅度,但我们仍然谈论msbit是符号位,因为除了它告诉我们的两个特殊数字,数字的符号,其他位实际上告诉我们它们的大小只是不是像符号+幅度表示法那样的无符号幅度.

所以,整个问题的关键是理解你的极限.对于3位无符号数,我们的范围是0到7,0b000到0b111.对于3位有符号(二进制补码)解释,我们的范围是-4到+3(0b100到0b011).现在将自己限制为3位如果添加7 + 1,0b111 + 0b001 = 0b1000,但我们只有3位系统,因此0b000,7 + 1 = 8,我们不能在系统中代表8,这样就是溢出因为我们碰巧将这些位解释为无符号,所以我们看一下"无符号溢出",也称为进位或标志.现在,如果我们采用相同的位但将其解释为有符号,则0b111(-1)+ 0b001(+1)= 0b000(0).减1加1是零.没有溢出,"签名溢出"没有设置...签名溢出是什么？

首先是什么是"无符号溢出".

无论我们在寄存器中有多少位,"它都工作相同"的原因与具有基数10(十进制)数字的小学数学没有什么不同.如果你添加9 + 1这两个都在一列你说9 + 1 =零携带1.你带一个到十列然后1加0加0(你在十列中填入两个零)是1携带零.你在十列中有一个1,在一列中有一个零

  1
  09
 +01
====
  10

如果我们宣布我们仅限于列中的数字,那么就没有任何空间可以存在数十列.好吧,进位是非零意味着我们有溢出,正确计算结果我们需要另一列,与二进制相同

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

7 + 1 = 8,但如果我们声明一个3位系统,我们就不能做8,我们可以设置进位位来做7 + 1 = 0.这里是两个补充之美的地方:

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

如果你看一下上面的三位加法,你不能通过查看是否7 + 1 = 0并设置进位位或者如果是-1 + 1 = 0来判断.

因此,对于无符号加法,正如我们从小学时就已经知道的那样,将一个非零的东西延伸到下一列意味着我们已经溢出了许多占位符并需要一个占位符,一个列,以保持实际的答案.

签名溢出.这种学术答案是msbit列的进位与执行不匹配.让我们在3位世界中举一些例子.因此,对于二进制补码,我们限制在-4到+3.所以,如果我们加上-2 + -3 = -5那不正常吗？为了弄清楚减去二是什么我们做反转并添加一个0b010,倒置0b101,添加一个0b110.减3是0b011 - > 0b100 - > 0b101

所以现在我们可以这样做:

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

如果你查看b下的数字是"进入"到msbit列,a下的数字是1,是执行,这两个不匹配所以我们知道有一个"签名溢出"

让我们尝试2 + 2 = 4

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

你可能会说,但看起来是正确的,确实无条件它,但我们在这里做了签名数学,所以结果实际上是-4而不是正数4. 2 + 2!= -4.在b下的进位是1,msbit的进位是零,进位和进位不匹配.签名溢出.

有一个快捷方式可以找出已签名的溢出而无需查看进位(或执行).if(msbit(opa)== msbit(opb))&&(msbit(res)!= msbit(opb))有符号溢出,否则没有符号溢出.opa是一个操作数,opb是另一个操作数,结果是res.

   010
 + 010
======
   100

取此+2 + +2 = -4.msbit(opa)和msbit(opb)相等,结果msbit不等于opb msbit,因此这是一个带符号的溢出.您可以使用此表来考虑它

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

这个表是所有可能的组合,如果进位,操作数a,操作数b,执行和单个列的结果位将你的头侧向左转来看看这个x是进位,a和b列是两个操作数.cr作为一对是结果xab为011表示0 + 1 + 1 = 2小数,即0b10二进制.因此,采用已经指示给我们的规则,如果进位和执行不匹配,那就是签名溢出.那么x列中的项与c列中的项不匹配的两种情况表示a和b输入彼此匹配的情况,但结果位与a和b相反.所以假设规则是正确的,这个快速的快捷方式不需要知道进位是什么,它会告诉你是否有签名溢出.

现在你正在阅读一本H&P书.这可能意味着mips或dlx,mips或dlx都不像大多数其他处理器那样处理进位和签名标志.mips不是最好的第一个指令集IMO,主要是因为这个原因,他们的方法在任何方面都没有错,但作为一个古怪的,你会花费不同的思维方式,并且在去大多数其他处理器时必须翻译.如果你学习了典型的znvc标志(零标志,负标志,v =有符号溢出,c =进位或无符号溢出),那么你只需要在转到mips时进行转换.通常这些是在每个alu操作上计算的(对于非mips类型处理器),您将看到为加法和减法计算有符号和无符号溢出.(我习惯了一个较老的mips,也许这一代书和当前的指令集有些不同).在学习了以上关于加法器电路如何不关心有符号和无符号的所有上述内容之后,调用它addu在mips开头添加无符号权限,这对mips来说是一个很大的问题,它真的让你错误地理解了这个简单的事情.导致认为在没有签名加法和无符号加法之间存在差异.只有溢出标志的计算方式不同.现在乘以,并且除了肯定有二进制补码与无符号差值,你理想情况下需要有符号乘法和无符号乘法,或者你需要处理限制.

我推荐一个简单的(取决于你的位操作有多强和二重补充)练习,你可以用一些高级语言写.基本上将无符号数0到7的所有组合添加到0到7并保存结果.打印出十进制和二进制(操作数为3位,结果为4位),如果结果大于7次打印溢出.使用带符号变量重复此操作,使用数字-4到+3添加到-4到+3.使用+/-符号和二进制文件打印十进制.如果结果小于-4或大于+3打印溢出.从这两个表中,您应该能够看到上述规则是正确的.严格考虑允许大小的操作数和结果位模式(在这种情况下为三位),您将看到加法运算给出相同的结果,给定输入对的相同位模式,与这些位模式是否被认为是无符号无关或两个补充.您还可以验证无符号溢出是否在结果需要使用第四列时,有一个执行关闭msbit.当进位不匹配执行时签名,您可以使用快捷方式查看操作数和结果的msbits.更好的是让你的程序进行那些比较并打印出一些东西.因此,如果您在表中看到结果大于7的注释并且表中的注释在结果中设置了第3位,那么您将看到无符号表总是如此(仅限于0的输入)到7).更复杂的一个是有符号溢出,总是在结果小于-4且大于3且当操作数高位匹配且结果高位与操作数不匹配时.

我知道这是超长而且非常基础的.如果我完全错过了这里的标记,请发表评论,我将删除或重写此答案.

另外两个人补充了魔法.硬件没有减法逻辑."转换"为二进制补码的一种方法是"反转并添加一个".如果我想使用二进制补码减去3 - 2,实际发生的是+3 +( - 2)右边,并且从+2到-2得到反转并加一.看着我们小学的补充,您是否注意到第一列中的进位孔？

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

我把一个H放在洞的上方.那么携带位是否添加到操作数对吧？我们的加法逻辑不是双输入加法器它是三输入加法器是吗？大多数列必须添加三个一位数才能计算两个操作数.如果我们在第一列使用三输入加法器,我们现在有一个地方...添加一个.如果我想减去3 - 2 = 3 +( - 2)= 3 +(~2)+ 1这是:

    1
  011
+ 101
=====

在我们开始并填写之前是:

 1111
  011
+ 101
=====
  001

3 - 2 = 1.

逻辑的作用是:

如果加上则进位= 0; b操作数不反转,执行不反转.如果减去则进位= 1; b操作数被反转,执行MIGHT BE反转.

上面的添加显示了一个执行,我没有提到这是一个无符号操作3 - 2 = 1.我使用了一些二进制补充技巧来执行无符号运算,因为这里无论我是否将操作数解释为有符号或无符号操作如果添加或减去相同的规则适用.为什么我说执行MIGHT BE反转是一些处理器反转执行,有些不执行.它与级联操作有关,比如32位加法逻辑,使用进位标志和带有进位或减法的加法,借用指令创建64位加法或减法,或基址寄存器大小的任意倍数.假设你在32位系统中有两个64位数a:b + c:d其中a:b是64位数,但它保存在两个寄存器a和b中,其中a是上半部分,b是下部半.所以a:b + c:d = e:在32位无符号系统上的f,它有一个进位并加上进位:

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

添加从状态寄存器中的进位标志中的最高位通道离开其进位位,addc指令加上进位取操作数a + c,如果进位位置位则再加一位.a + c + 1将结果放入e并且在进位标志中执行,所以

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

是96位添加,依此类推.这里再次提到一些非常陌生的东西,因为它不像其他处理器那样使用标志.对于特定处理器,对于有符号执行的反转或不反转进入减去借位.减去:

如果减去则进位= 1; b操作数被反转,执行MIGHT BE反转.

借用借位减去你必须说如果状态寄存器中的进位标志表示借位,则进位输入为0,否则进位输入为1,你必须将进位输入状态寄存器以指示借位.

基本上对于正常的减法有些处理器反转b操作并在进出的路上进行,有些处理器反转b操作进入但不进行反向执行.然后,当你想要做一个条件分支时,你需要知道进位标志是否大于或小于(通常语法将有一个分支,如果更大或分支如果小于,有时告诉你哪一个是简化分支,如果携带设置或分支,如果携带清楚).(如果你没有"得到"我刚才所说的那是另一个同样长的答案,只要你正在研究mips就不会有任何意义).