补数complement)是对于给定的进位制,相加后能使自然数 a 的位数增加 1 的最小的数。可以在计算电路中,代替减的操作,而仅仅使用加法器组件(加法器)的“加上的补数(无视最高位的进位)”,达到相同的效果。

定义

编辑

b 进制表示自然数 a 至少需要 n 位数字,规定

  •   是      “b 进制数 a 的关于基数的补数b 的补数)”
  •   是“b 进制数 a 的关于减基数的补数b - 1 的补数,简称减补数侪补数)”。

例如,十进制自然数 61 关于基数 10 的补数是  。二进制自然数   关于基数 2 的补数是  

由定义可以得出,a基数的补数 加上 a,可以得到位数多一位的最小的自然数( )。a减基数的补数 加上 a ,可以得到位数不增加的最大的自然数( )。

基数 b 在上下文中明确的时候,“在b 进制中”的描述通常被省略。

但是,在基数不明确的情况下,“  的补数”表示的可以是  进制的减基数的补数,也可是   进制的基数的补数,从而产生歧义(这两者的值不一定是相等的)。例如,仅仅说“9的补数”,无法确定指的是“10进制中的减基数的补数”还是“9进制中的基数的补数”。

在英文中,十进制的基数的补数记为 ten's complement,减基数的补数称为 nines' complement。二进制中,基数的补数称为 two's complement,减基数的补数称为 ones' complement。其他进制也有类似的称法。一些人,如高德纳,建议采用撇号区分。这样,four's complement指的是四进制中的基数的补数。而fours' complement指的是五进制中的减基数的补数。但是,这并不是普遍的做法,而且在几乎所有情况下进制是明确的。多数作者写做 one'snine's complement,一些格式手册建议采用 onesnines complement,不采用撇号。

计算方法

编辑

对于N进制的自然数a,从个位开始的各位数字

 

规定 不能为0。规定 的各位为:

bi = (N + 1) + ai

这时,N进制形如的

 

  即称为“  的关于   的补数”。

10进制的举例

编辑

十进制数 2304671 的补数。由于 9 = 2 + 7 = 3 + 6 = 0 + 9 = 4 + 5 = 6 + 3 = 7 + 2 = 1 + 8 ,令N=9时,自然数2304671对应的补数为 7695328 。 7695328 + 1 = 7695329 ,因此N=10时,自然数2304671对应的补数是 7695329

2进制的举例

编辑

二进制中有 1 + 1 = 0, 1 + 0 = 1,求1的补数只需简单地将0与1相互替换位操作中的逻辑非运算)。

补码(即补码),只需要将1的补数加1。

  • 二进制的 101010110 对应的1的补数是 010101001。
  • 2 的补数是 010101001 + 1 = 010101010。

参考文献

编辑

JIS X 0005:2002 情报処理用语(データの表现) 05.08

Donald E. Knuth ‘The Art of Computer Programming Vol. 2 Seminumerical Algorithms Third Ed. 日本语版’ アスキー、2004年、191页。 (ISBN 4-7561-4543-4)

相关条目

编辑