关于二进制补码运算如何解决溢出问题的研究

柏刚+程兰

摘要：计算机中用补码来表示和存储数值，而在进行数值的算术运算时由于机器字长的限制往往会出现补码溢出，导致计算结果错误。针对这个问题，提出了一种根据溢出结果得到正确结果的计算方法：两个正数相加溢出时，将错误解加上2n+1即为正确解；两个负数相加溢出时，将错误解减去2n+1即为正确解，并给出了一般性证明。

关键词：二进制；有符号数；补码；溢出；求补运算

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）33-0208-02

Abstract：Complement is used to represent and store the value in computers.But the problem of complement overflow often happens in numerical arithmetic because of the limit of word length， which leads to calculation errors. To solve this problem， a new method is proposed to get the correct result according to the overflow result，in which the error solution can turn out to be correct by plus 2n+1 when it's two positive numbers' additive overflow or minus 2n+1 when it's two negative number's additive overflow， and gives a general proof.

Key words： Binary； Signed number ； Complement； Overflow； Complementary operation

1 补码概述

二进制补码是计算机中采用的数制，用来表示有符号二进制数。在二进制补码这一数制中，一切数（被加数、加数及和；被减数、减数及差；被乘数、乘数及积；被除数、除数、商及余数；求补运算前的数及求补运算后的结果等） 都是用二进制补码来表示的[1]。补码问题既是数字电子技术课程和微机原理课程的教学难点之一，也是软件开发中常常遇到的问题之一[2]。

对于有符号数，用0表示正数的符号位，1表示负数的符号位。对于n+1（变量用斜体）位字长的有符号二进制数，其补码是这样定义的：若该数的原码为非负数，则其补码与其原码表示相同；若该数的原码为负，则其补码的数据位为其原码表示的数据位逐位求反后加1，而符号位为1[2]。其公式如下：（n表示数值位的位数）

2 补码溢出问题

两个用补码表示的有符号数进行加、减运算时，其特点是把符号位上表示正、负的“0”和“1”也看成数，与数值部分一起进行运算，所得的结果也为补码形式。结果的符号位为“0”，表示正数；结果的符号位为“1”，表示负数[3]。

两个有符号数X和Y相加时，先将两数转换成补码形式，然后进行补码运算，所得结果为和的补码，即：[X+Y]补=[X]补+[Y]补。两个有符号数X和Y相减时，可看成X+（-Y）分别将X和-Y表示成补码形式再进行运算，所得结果为差的结果，即：[X-Y]补=[X]补+[-Y]补。

由于补码的表示范围为：-2n～ 2n-1。当两个有符号数进行补码运算时，若结果的绝对值超出运算装置容量，数值部分就会发生溢出，占据符号位的位置，导致错误的结果[3]。

因为计算机中的减法也看作加法，因此我们只讨论加法。下面分3种情况来讨论两个有符号数X和Y相加（转换成补码后，用n位数值位1位符号位表示）。

1）. X和Y均为正数，当X+Y大于2n-1时，结果溢出。

2）. X和Y均为负数，当X+Y小于-2n时，结果溢出。

3）. X和Y两数中只有一个数为正，另一个数为负。符号不同的两个数相加是不会产生溢出的[4]。

3 如何从补码溢出结果得到正确结果

下面将讨论两种溢出的情况，并提出解决溢出问题的方法。

1） X和Y均为正数，当X+Y大于2n-1时，结果将溢出。

例2：使用7位数值位，1位符号位的二进制数来表示，其补码表示范围为：-128D ～ 127D

计算70+85，由于70+85=155，155大于127，结果将溢出。

即：70+85=-1100101= -101，显然发生溢出，结果错误。

为了给出解决方法，先给出两个结论：

结论一：两正数相加最高位（符号位）一定不会进位。

证明：两正数的符号位都是零，如果符号位溢出，次高位必须要进2，在最理想的情况（两个数的次高位都是1），次高位要进2必须要求次次高位进2，以此类推，必须要求最低位进2，才能使得较高位进2，而最低位最多只能进1。

由此例可知，即使数值位都为1，符号位也不会产生进位。

结论二：两正数相加溢出一定是由于次高位（数值部分最高位）向符号位有进位。

证明：根据双高位判别法（计算机中常用的溢出判别称为双高位判别法，即：最高位（符号位）有进位而次高位无进位或最高位（符号位）无进位而次高位有进位 [3]。）及结论一，可知溢出一定是因为次高位有进位，而且只能进1，所以符号位一定是1。

下面推导出解决正数相加溢出的公式。

设X和Y都为正数，转换成二进制补码后用n位数值位1位符号位表示，且X+Y大于2n-1，即溢出。为了避免可能产生的溢出错误，有必要扩展二进制补码的码位数，即在进行求补运算之前，使二进制补码扩展符号位：将二进制补码的原符号位向左 （高位） 重复写一位，形成新的符号位。扩展符号位以后的二进制补码，真值不变。扩展符号位能够保证 n位二进制补码的每一个数求补运算的正确性[1]。结果将不会溢出。

即：（1）用n+1位数值位1位符号位表示[X]补+[Y]补时不会溢出，得到的结果为正确结果，令正确结果为Co。

（2）用n位数值位1位符号位表示[X]补+[Y]補时会溢出，得到的结果为错误结果，令错误结果为Er。

在结论一和结论二的条件下，Er是将Co的最高位当成了符号位，把Er当成负数，再求补码从而得到原码。即：

例4中-76+（-90）转换成补码运算后等于+1011010即+90。

将90代入（5）式：90-28=-166，结果正确。

结论四：负数的补码运算溢出时，将溢出结果减去2n+1可以得到正确结果。

4 结论

本文讨论了有符号数的补码溢出问题，并给出了根据溢出结果得到正确结果的方法。两个正数相加溢出时，将错误解加上2n+1即为正确解；两个负数相加溢出时，将错误解减去2n+1即为正确解。本文方法可以在不增加字长的情况下解决溢出问题。

参考文献：

[1] 查振亚. 关于二进制补码数制中求补运算的研究[J]. 华中理工大学学报， 1997（3）：106-110.

[2] 孙开放. 对二进制补码数的进一步研究[J]. 电气电子教学学报，2002（3）：35-36.

[3] 马春燕. 微机原理与接口技术（基于32位机）[M]. 北京：电子工业出版社，2013：14-17.

[4] 曹建芳. 二进制定点整数补码运算中“丢失”与“溢出”问题的研究[J]. 晋东南师范专科学校学报，2003（2）：68.