使用二进制补码进行按位减法时出现溢出问题

Question

使用二进制补码进行按位减法时出现溢出问题

6

当使用二进制补码进行按位减法时，如何知道是否应忽略溢出？我阅读了几个网站，它们都指出可以简单地忽略溢出，但这并不总是适用的，比如在计算“-35 - 37”这类问题时，需要一个额外的数位来表示答案“-72”。下面是一个示例，使用上面的方程式。

把“35”转换为二进制 -> “100011”，找到二进制补码使其变为负数: “011101”。

把“37”转换为二进制 -> “100101”，找到二进制补码使其变为负数: “011011”。

执行上述项的加法（-35 - 37的二进制等效项）：

011101
011011
------
111000

采用二进制补码将其转化为正数：001000

许多网站（包括学术网站）都会这样说，忽略了溢出，认为上述答案是正确的。然而，这显然是不正确的。

- vaindil

1

显然，那些网站并没有描述如何按位计算“-32 - 37” :-) - Kerrek SB

2

这个答案在Stack Overflow上有提到，同时在这个学术网页的第四步也有说明。这个PowerPoint(Google Viewer链接)在第9页也有展示。 - vaindil

什么是按位减法？你是指二进制补码的减法吗？如果是这样，那么你的问题应该是，在负整数的二进制补码加法中，当宽度为N（例如）时何时会发生溢出？ - Khaled Alshaya

你能解释一下你对“按位”减法的期望吗？这与减法有什么不同吗？（你正在使用-运算符，所以我不知道你的“按位”是什么意思？）此外，在你的例子中我没有看到任何溢出？你可以在http://www.hackersdelight.org/这里查找一些方便的溢出检测算法。另外，根据你的硬件，有时会在溢出发生时设置一个寄存器位（但这只是在发生后）。 - Josh Petitt

刚刚在主帖中添加了一个使用“-35 - 37”的示例，这有帮助吗？ - vaindil

@StevenH 这有点帮助。你使用的位数（6位）与数字相关的问题是它违反了标准的有符号数字要求。根据C99-§6.2.6.2,2，你的有符号数字中的一个位必须被保留以表示符号状态。此外，同一部分规定，除去符号位，其余位的表示必须对应于剩余位数的关联无符号类型。你选择的位数和你试图在这些位中表示的值违反了标准的这一部分。讨厌这种情况发生。 - WhozCraig

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amdn · Accepted Answer

当结果无法在目标数据类型中表示时，会发生溢出。-72可以用char表示，char是一个带符号的8位数量...在您的示例中没有发生溢出。也许您在进行按位减法时考虑到了借位...当您从'0'中减去'1'时，需要从下一个更高的位位置借位。在做减法时不能忽略借位。

-35 decimal is   11011101 in two's complement 8-bit
+37 decimal is   00100101 in two's complement 8-bit

从最低有效位到最高有效位，您可以将+37中的每个位从-35中的每个位中减去，直到到达第5个位（从右边的第0个位开始计数）。在位位置5上，您需要从“0”中减去“1”，因此您需要从-35中的位位置6（下一个更高阶位）借位，这恰好是在借位之前的“1”。结果如下所示。

-35 decimal is   11011101 in two's complement 8-bit
+37 decimal is   00100101 in two's complement 8-bit
                 --------
-72 decimal is   10111000 in two's complement 8-bit

结果是负数，且您的8位二进制补码结果设置了高位（第7位）...这意味着它是负数，因此没有溢出。

更新：我想我知道混淆在哪里了，并且我声称这里的答案“添加和减去二进制补码”是错误的，当它说你可以丢弃进位（表示溢出）。在那个答案中，他们通过使用二进制补码将第二个操作数转换为负数，然后进行加法运算来进行减法。这很好-但在这种情况下，进位不表示溢出。如果您在N位中添加两个正数（标记为0到N-1），并且将此视为无符号算术范围0至（2 ^ N）-1，则如果从位位置N-1获得进位，则会发生溢出-两个正数的总和（解释为无符号以最大化可表示正数范围）不应在最高位（位N-1）产生进位。因此，当添加两个正数时，您通过以下方式识别溢出

将它们解释为无符号数字时，不能在N-1位上进行传递；
将其作为有符号数（二进制补码）解释时，位N-1中的结果必须为零。

请注意，但是，处理器不区分有符号和无符号的加法/减法...它们设置溢出标志以指示如果您将数据解释为有符号数，则结果可能无法表示（错误）。

这里是非常详细的关于进位和溢出标志的解释。从文章中得出的结论是：

在无符号算术中，观察进位标志以检测错误；
在无符号算术中，溢出标志不会告诉您任何有趣的事情；
在有符号算术中，观察溢出标志以检测错误；
在有符号算术中，进位标志不会告诉您任何有趣的事情。

这与维基百科上算术溢出的定义一致，其中说：

大多数计算机区分两种溢出情况。当将操作数和结果视为无符号数时，加法或减法的结果不适合结果时，会发生进位。因此，在将被解释为无符号值的数字相加或相减后，检查进位标志是有用的。当结果与操作数的符号预测不符时（例如，将两个正数相加得到负数），就会发生溢出。因此，在使用二补码形式表示数字（即这些数字被认为是有符号数）进行加法或减法后，检查溢出标志是有用的。