补码

转载需首行注明原地址

本章参考 车向泉老师的公开课《计算机系统中的数据表示》

目标：真正理解为什么要有补码，明白补码的各种性质

目录

1. 原码
2. 模运算
3. 补码
4. 补码的性质

1. 计算机不会存小数点， 多一个小数点，意味着数据需要多占一位，而且计算起来，需要拆分小数点后进行运算，所以计算机存的都是定点数（提前就拆分好，避免运算时拆分）。
   而浮点数可以用两个定点数表示，所以以下我们研究的各种存储编“码”都是针对定点数而言。

1. 原码

大家都知道计算机里面存的是2进制，而实际的数据是有正负之分的，为了标识正负，很容易想到给数加上一个进制位。
于是就有了原码，规定加0表示正数，加1表示负数。

• 定义：

  
  

• 整体来讲：
  原码就是首位用0表示正数，1表示负数，所以非常简单直观。
  这种简单和直观会带来很多个头疼的问题：
  1 +0和-0,0不唯一了
  2 加减运算及其复杂
  例如：要计算 A - B，首先要判断A和B的数的正负和大小，以此来判断最终的正负及运算规则，比如A>B,A+B- (+表示正，A+表示A是正数，同理，B-表示B是负数)，那么实际上算A+|B|，如果A<B,A+B+，那么实际上应该算 B-A，结果上放上负号，如果....
  无疑，这样的设计放到运算器上，可能今天就没有PC了，那么这种运算最致命的地方在哪里？ 为什么会如此复杂？
  其根源在于： +-号无法带入运算，这时，数可能是正负，运算可能是加减，同时A，B本身还有大小，则可能出现2²2共计16种情况。

• 那么如何把+-号带入计算机呢？
  首先必须了解计算最基本的运算，然后带入正负，通过正数求负数。

2. 模运算

计算机有个非常讨人厌的且无可避免的情况，“溢出“,因为计算机的字长是有限的，而计算的数可以生成无限的结果。那么当计算出来的数超过字长，应该怎么处理呢?

• 一般来说有两个处理方法，一个返回错误，一个将无法表示的位丢弃(溢出)。
• 返回错误这当然没什么好说，尽管"溢出"同样让人"不爽"。但是还是应该研究溢出，建立“溢出”模型。

于是便有了模运算（这并不是历史，我是瞎推测的）

模运算定义：
在一个运算系统内，若A、B、M满足以下关系：A=B+K*M (K为整数)，则记作A≡B(mod M)。

一个很形象的例子：时钟，我把时钟上任意一个时间，拨动一圈，它又回到拨动前的时间。而“溢出”的就是一个天的时间，这和计算机内部非常像。

3. 补码

知道了计算机最基本的运算规则：有模运算。那么应该带入正号来求出负数。
首先，还是规定首位为0就是正数。例如正数A。
那么负数可以看成：-A（0<=A<M,M为模）
已知：A=B+K*M ，可得 ：-A = -A + M ，
同时：已知0<=A<M , 可得 ：(-A+M) > 0。
这相当于用一个正数 (-A+M) 表示出一个负数 -A 。
同理可得，A = A+M。

由此，可以得出补码的定义：
对于任意一个数 X ，都有X = X + M （X mod M）。

推广到计算机（假设字长为n），可以得到定义：

（注意：负数部分=号，是强制规定，例如8位字长机器码对应10000000，我们强制认定为-128）

4.补码的性质

4.1 补码的符号位

由此可知，首位0一定是正数，首位1一定是负数。

4.2 补码中的0唯一

4.3 补码的范围

假设机器字长为n。

• 定点小数：
  -1 <= x < 1- 2^(-(n-1)) ==> 1.0 ~ 0.111....1 (n-1个1)

• 定点整数：
  -2^(n-1) <= x <= 2^(n-1)-1 ==>1000...0 ~ 0999..9

4.4 补码、真值、原码间的相互转换

4.4.1 真值 => 补码

x为真值

• 当 x >= 0 ，补码==真值==原码
• 当 x <= 0

假设字长为n， |x|代表数值位
小数：

      x补 = 2 + x  // -1 <= x <=  2^(-(n-1)
          = 1+(1-2^(-(n-1)))-|x| + 2^(-(n-1)) // 1+ 0.111...1 - |x| + 0.000...1          
          = 符号位为一 + |x|全部位按位取反 + 末位加一 

          //x为-1时，|x|=1，溢出了，结果为0。按位取反+1后继续溢出为0，符号位设置1，结果刚好对-1（主要原因是-1这个是强制认定的值）

整数：

      x补 = 2^n + x // -2^(n-1) <= x < 0
          =2^(n-1) + (2^(n-1)  - 1) - |x|  + 1
          =符号位为一 + |x|全部位按位取反 + 末位加一 

由此，得到一个经验"按位取反，末尾加一"

然而，这个多了一个“加一”，计算机多跑了一次，有办法优化吗？

我们发现，可以从左往右早第一个1，1和1右边的不变，左边的按位取反。
例如 ，-0.10100100 ，可以一步写出答案1.01011100。

4.4.2 补码 => 真值

假设字长为n，x为补码
小数：

x真 = x - 2
    = -(1-2^(-(n-1)) - (x-1) +  2^(-(n-1))  // -(0.111..1 - 数值位 + 0.000...1)
    = -(补码数值位按位取反 + 0.000...1)

整数:

x真 = x - 2^n
    = -(2^(n-1)-1 - (x-2^(n-1)) + 1)// -(111...1 - 数值位 + 1)
    =- (补码数值位按位取反 + 1)

同 真值转补码，补码转真值也可以优化：
从左往右早第一个1，1和1右边的不变，左边的按位取反，再加上-号。

4.5 符号的扩展

原则：扩展后，不能影响大小。

正数：
小数尾位补0，整数高位补0，因为补码等于真值，所以扩展后保持不变。

负数：

• 小数：末尾补0
• 整数：高位补1

简单证明下整数：（注意，x为什么可以替换，因为我们是扩展符号位，而x扩展前后必须想等）

4.6 补码的算术右移

所以，定点小数，正数右移高位补0，负数高位补1

我们推导一下定点整数：
正数：

[1/2x补] = 1/2x = 1/2x补

负数：

[1/2x补] = 2^n + 1/2x
         =2^n + 1/2(-2^n + x补)
         =2^(n-1) + 1/2x补

所以，定点整数，正数右移高位补0，负数高位补1

由此，可以得到结论，正数右移，高位补0，负数右移高位补1。

4.7 补码的算术左移

这里主要的问题：算术左移会让模变大，否则溢出。