何为补码

补码,又称二补数(two’s complement),是一种二进制数字的数学运算,也是当今计算机系统中最流行的二进制有符号数的表示方法,其他表示方法还有原码(sign-and-magnitude)、反码(ones’ complement)等。

N位二进制数字的补码即其相对于2N的补,即2N减去该数的结果。补码另外一种等价的计算方式是取该数的反码,然后加上1,因为一个数与其反码的和的所有位为均为1(即2N-1)。大多数运算中,一个数的补码同这个数的负数在行为上是一致的。

在补码表示法中,正数以其自身表示,负数以其绝对值的补码表示。如在3位二进制运算中,为了表示-2,可做计算8-2=6,所以-2在补码中表示为:110。N位补码系统的整数的表示范围是从 −(2N − 1)  到+(2N − 1 − 1)。

为何使用补码

假设让你设计一个N位二进制有符号整数的表示方法,你会怎么做?

首先想到的也是最直观的做法是使用首位表示符号位,其余N-1位表示数值,即原码表示法。

但是在这种表示方法下,很多情况下两个整数直接运算得到的结果是不正确的,如下列加法运算:

   
   0  1  1 (3)
 + 1  0  1 (-1)
 ================
   0  0  0 (0)

因为符号位参与了运算,若要得到正确的运算结果,计算机需要考虑多种不同输入符号的情况,因为正数间的加法规则不适用于其他情况,进而要额外设计更复杂的电路才能实现运算。

原码表示法另外一个缺点是存在两种0的表现形式:正0和负0,这无疑增加了计算机逻辑判断的复杂性。

反码表示法因为也存在诸如0有多种表示以及需要循环进位等问题,因此也未被广泛使用。

补码的优势是补码可作为无符号二进制数进行加法、减法和乘法的基本算术运算(只要输入用同等位数的二进制表示并且结果中任何超过该位数溢出被舍弃)。这个特性让计算机系统实现更简单并能够容易地进行高精度运算。另外,补码系统不存在负0,0仅有一种表现形式。

补码的原理

要理解补码是如何工作的,不得不说说模运算(modular arithmetic)。

在模运算中,如果两个数被某个特定的数字N除后得到相同的非负余数,则这两个数是“等价”的。在数学术语中,我们称之为两数对于模N同余(congruent modulo)。

12小时制的钟表是模运算应用的一个很好的例子。在12小时钟表中,前进2小时、后退10小时、前进14小时是等价的:

3:00 + 2 hours = 5:00

3:00 + 14 hours = 5:00

3:00 – 10 hours = 5:00

换句话说,在基于12的模运算中,2、-10、14是相同数字的不同表现形式。

在计算机内部,数字是用固定数量的比特位表示的如32位或64位。数字的加法、减法和乘法运算就是基于无符号数的模运算。

举一个简单例子,3位二进制可以表示数字0到7。如果在固定位的二进制运算中,两个3位二进制数字相加或相乘,就会得到模运算的结果:

1 + 2 –> 3

4 + 5 -> 1

计算会循环取值(wrap around),因为任何大于7的结果不能用3位二进制表示,但得到的结果仍然是有意义的:

  • 实际的结果同预期的结果对于模8是等价的
    预期的结果是9,但是却得到1。9和1被8除会得到相同的余数1,即9和1对于模8同余。
  • 实际的结果表示了预期结果的最低三位
    对于4+5来说,  预期的结果为 1001,实际的结果舍弃了溢出位得到001。

对此,一种比较好的思考方式是首先想象一条无尽的数字线:

 

然后将该条数字线弯曲以使其变成1000与000重叠的圆环:

 

在3位二进制运算中,加法、减法和乘法运算是沿着一个由8个数字组成的闭环而不是一条无尽的直线移动,除此之外,其他同一般的运算无异。

补码表示法正是巧妙地利用了模运算将有符号数字间的运算转换为无符号数字间的运算:

对于给定的包含所有N位二进制值的集合,我们把低半部分二进制值(0到2N − 1 − 1)赋值给 0到 (2N − 1 − 1)之间的整数,把高半部分二进制值(2N − 1到2N-1)赋值给−2N − 1 到 −1之间的整数。高半部分可以用来表示从−2N − 1 到 −1之间的负数是因为对于模2N他们之间存在同余关系。也就是说,因为 i + j mod 2N = i + (j + 2N) mod 2N,任何在集合{ j + k 2N | k 是整数 } 中的值可以替换j。

以下表格展示了3位二进制分别作为无符号数和补码时所代表的值:

[table id=2 /]

可以发现,无符号数值和补码值对于模8同余,对于计算机的加法器而言,他们是相同的。所以在运算时,负数用补码表示,负数的加法实现不需要设计额外的用来检测操作数符号的电路,复杂的有符号数运算变成了简单的无符号数运算,并且计算机通过舍弃溢出位可得到正确的结果。如之前的加法运算:

   
   0  1  1 (3)
 + 1  1  1 (-1)
 ================
   0  1  0 (2)

参考

https://en.wikipedia.org/wiki/Two%27s_complement

http://igoro.com/archive/why-computers-represent-signed-integers-using-twos-complement/

Leave a Reply

Your email address will not be published. Required fields are marked *