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

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），也可能是负7。相同的位模式，将其馈入加法逻辑，出现相同的结果，而得出的答案我可以选择将其解释为无符号或二进制补码（只要我将操作数和结果都解释为无符号或全部）作为补码）。二进制补码还具有以下特征：对于负数，最高有效位（msbit）被设置，对于正数，其为零。因此，它不是符号加幅度，但我们仍将msbit称为符号位，因为除了告诉我们的两个特殊数字（数字的符号）之外，其他位实际上是在告诉我们它们的幅度而不是像符号+大小符号那样的无符号幅度。

因此，解决整个问题的关键是了解您的限制。对于3位无符号数字，我们的范围是0到7、0b000到0b111。对于3位带符号（二进制补码）解释，我们的范围是-4到+3（0b100到0b011）。现在如果将7 + 1，0b111 + 0b001 = 0b1000加到3位，但是我们只有3位系统，即0b000，7 + 1 = 8，我们无法在系统中表示8，所以这是一个溢出，因为我们碰巧将这些位解释为无符号，我们看一下“无符号溢出”，也称为进位位或标志。现在，如果我们采用相同的位，但将它们解释为带符号，则0b111（-1）+ 0b001（+1）= 0b000（0）。减一加一为零。没有溢出，没有设置“签名溢出” ...什么是签名溢出？

首先，什么是“无符号溢出”。

无论寄存器中有多少位，“全部工作都相同”的原因与以10为基数（十进制）的小学数学没有什么不同。如果将9 + 1都加到“ 1”列中，则说9 + 1 = 0携带1。将1携带到tens列中，然后将1加0加0（在tens列中填入两个零）是1携带零。在tens列中有一个1，在that列中有一个0：

  1
  09
 +01
====
  10

如果我们声明在“ ones”列中仅限于数字该怎么办，那么十列就没有空间了。好吧，进位位为非零意味着我们有一个溢出，要正确计算结果，我们需要另一列，与binary相同：

  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。负三是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是另一个操作数，并返回结果。

   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，执行位和结果位为单列，则将您的头向左倾斜向左看，这是进位，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 add unsigned，这是mips的一个大问题，它确实使您陷入了错误的思维方式，无法理解这种简单的方法。导致人们相信，有符号加法和无符号加法之间没有区别。只是溢出标志的计算方式不同。现在相乘，除，绝对有一个二进制补码与一个无符号的差，理想情况下，您需要有符号的乘法和无符号的乘法，或者需要处理限制。

我建议您进行一次简单的练习（具体取决于您的位操作的强度和二进制补码），该练习可以用一些高级语言编写。基本上将0到7的无符号数字的所有组合加到0到7，然后保存结果。打印为十进制和二进制（操作数为三位，结果为四位），如果结果大于7，则也将打印溢出。使用带符号的变量重复此操作，使用加到-4至+3的数字-4至+3。同时打印带有+/-号的十进制和二进制。如果结果小于-4或大于+3，则打印溢出。从这两个表中，您应该能够看到上述规则是正确的。严格查看允许大小的操作数和结果位模式（在这种情况下为三位），您会发现加法运算对于给定的一对输入给出相同的结果，相同的位模式，而与这些位模式是否被认为是无符号的无关或补码。您还可以验证无符号溢出是当结果需要使用该第四列时，是否执行了msbit。对于进位与进位不匹配的带符号，您可以使用快捷方式查看操作数和结果的msbit来看到。更好的是让您的程序进行这些比较并打印出一些内容。因此，如果您在表中看到一个注释，结果大于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的无符号运算。我使用了一些二进制补码技巧来执行无符号运算，因为在这里无论我将操作数解释为带符号还是带符号，如果加或减，则适用相同的规则。我之所以说可能会将进位反转，是因为有些处理器将进位反转，有些则没有。它与级联操作有关，例如采用32位加法逻辑，并使用进位标志和带有借位进位或减法的加法指令创建64位加法或减法或基址寄存器大小的任意倍数。假设您在32位系统中有两个64位数字：a：b + c：d，其中a：b是64位数字，但是它保存在两个寄存器a和b中，其中a是上半部分，b是下半部分半。因此，在具有进位并加进位的32位无符号系统上，a：b + c：d = e：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操作数取反进行进取但是不将其取回进行。然后，当您要进行条件分支时，您需要知道进位标志的含义是大于还是小于（通常，语法在大于或小于的情况下会有一个分支，而在小于则分支，有时会告诉您如果进位是简化分支设置或分支（如果进位清零）。 （如果您没有“得到”我刚才说的话，那将是另一个同样长的答案，只要您正在学习技巧，就没有任何意义）。