二进制的编码

时间:2021-02-09 21:00:08

  通常计算机系统中讨论二进制的编码问题涉及到的有:原码、反码、补码,这里简单探讨一下他们之间的关系。

 

原码与反码

  原码是最先被提出的一种编码方式,使用最高位表示符号(0表示正,1表示负),其余位表示数值。原码存在一个问题,就是自然界中 +0 和 -0 是相同的,但 +0 的原码是 0b00,而 -0 的原码是 0b10,这样 0 出现两种编码方式。

  反码是从原码到补码的过渡阶段,对于任意一个整数 n ,它的反码:

  • n > 0:n的反码和原码相同
  • n < 0:n的反码等于原码进行如下变换:1.符号位不变,2.其余位按位取反;

反码同样没有解决 0 编码格式不唯一的问题,但它只是一个中间过渡;

 

模数与补数

  补码是系统使用的编码形式,在介绍补码前,需要了解一下模数和补数的概念。

  通常称:

  x % y = z

  为 x 模 y,其中 % 是取模运算符,y 称为模数,z 称为 x 在模 y 下的补数。

  我们来看下面的时钟,当前指向 8 点,如果只考虑小时的话,那么时钟的模数就是12,对于当前指向 8 点的时针,假如我们希望它走到 6 点,则至少有两种方法:

二进制的编码

  1. 8 + (- 2) = 6

  2. (8 + 10) % 12 = 6

也就是说,如果定义顺时针为正,逆时针为负的话,我们可以顺时针转动时针10个小时,也可以逆时针移动时针2个小时,时针最终都会停留在6点上。

  此时对于 -2 而言,它的补数就是 10,10 = 12 - |-2|,也就是说 一个负数的补数 等于 模数 减去 负数 的绝对值。之所以引入补数,是希望在一个类似钟面这样刻度有限、会出现循环往复的系统中,将减法和加法统一起来,使得减法运算可以一致的使用加法运算来处理。

 

补码

  在计算机系统内,补码和补数的概念是一致的,那模数是什么?以一个32位长度的整数而言,模数就是 2^32。就好比把一个圆盘分成了2^32份,在这个系统中,最小值是 0 ,最大值是2^32-1,当2^32-1再向前走1位时,又回到了0。这种使用定长内存表示数值的方式使得补码成为合适的编码方式。

  

  回到之前的介绍上来,对于任意一个整数 n ,它的补码:

  • n 为正数,补码就是其原码;
  • n 为负数,补码 = (n的反码 + 1) = (n的原码的符号位不变(为1),其余位取反) + 1 = (n的绝对值的原码按位取反) + 1
  • n 为 0,补码唯一确定为 0 ;

  对于一个负数,它的反码是自己绝对值的原码按位取反后加1,为什么?

  前面已经介绍过,负数的补数等于模数减去其绝对值,即 32 位负整数 n 的反码就是 2^32 - |n|,等于 (2^32-1) - |n| + 1。而 2^32-1 使用二进制表示刚好为32位1,它减去 |n|,其实就是对 n 的绝对值按位取反了!

  此外,对于 -0 的二进制原码 0b100...00,其补码为 0b1111...11 + 1 等于0,而 +0 的补码还是0,从而避免了正负0的编码结果不同的问题。

  总结起来,正数和0的补码就是其原码,而知道了原码、反码、补码之间的关系和补数是怎么求的,就不难求得负数的补码了。补码之间一致地使用加法运算,即加上一个负数(减法),等于加上这个负数的补码。而拿到一个负数的补码,再对这个补码进行一遍求补的运算,就可以得到原数的原码了!

  还是由于补码成立的基础,即使用定长的位数表示一个整数,也不难理解为什么补码的运算不可避免的会存在溢出——负 + 负变正 或 正+正变负 的情况了。