转载

基础野:细说原码、反码和补码

Brief

说来惭愧虽然刚接触计算机时已经学过原码、反码和补码的内容,但最近重温时却发现“这是什么鬼东西”,看来当初只是应付了考试了而已。本篇将试图把他们说个明白,以防日后自己又忘记了。

在深入之前,我们先明确以下几点:

1. 本篇内容全部针对有符号数整数;

2. 对于有符号数整数,其在计算机中的存储结构是 符号位 + 真值域。其中符号位为0表示正数,1表示负数;

3. Q:既然已经有原码,那么为什么还要出现反码、补码等数值的编码方式呢?

A:由于为了降低当时计算机物理电路的设计难度,决定采用加法代替减法运算(因此计算机内部是没有减法运算的),即10-5被替换为10+(-5),而反码、补码就用于解决10+(-5)的问题的。

True Form

原码,就是直接将十进制数转换为二进制数形式。如7的原码为0111,-6的原码为1110。

注意:

1. 原码是区分+0和-0的,+0的原码为0000;-0的原码为1000;

2. 若存储空间为n bit,则原码的取值范围是 -2 n -1 ~ 2 n -1。

原码在以加法代替减法的运算中引起的问题:

例如在计算0 = 1-1 = 1+(-1) = 0001 + 1001 = 1010 = -2, 发现通过原码来运算时居然会得到0 == -2的结果。于是引入了反码。

One's Complement

原码转换成反码的规则如下:

1. 正整数原码的反码是其自身。如原码0001的反码是0001;

2. 负整数原码的反码则是对原码真值域的个位数取反即可。如原码1010的反码是1101。

那么将反码转换为原码的规则如下:

1. 正整数反码的反码是其自身。如反码0001的原码是0001;

2. 负整数反码的原码则是对反码真值域的个位数取反即可。如反码1101的原码是1010。

注意:

1. 反码是区分+0和-0的,+0的反码为0111;-0的反码为1111;

2. 若存储空间为n bit,则反码的取值范围是 -2 n -1 ~ 2 n -1。

反码在以加法代替减法的运算中引起的问题:

例如在计算0 = 1-1 = 1+(-1) = 0001 【原码】 + 1001 【原码】 = 0001 【反码】 + 1110 【反码】 = 1111 【反码】 = 1000 【原码】 = -0, 发现通过反码来运算时居然会得到0 == -0的结果。

看到采用反码运算的结果已经非常接近正确结果,但-0对于我们来说还是没有太多的意义。于是引入了补码。

Two's Complement

原码转换成补码的规则如下:

1. 正整数原码的补码是其自身。如原码0001的补码是0001;

2. 负整数原码的补码则是对原码真值域的个位数取反后,整体+1即可。如原码1010的补码是1111。

那么将补码转换为原码的规则如下:

1. 对补码再求一次补码则得到原码。

注意:

1. 补码是不区分+0和-0的,+0和-0的补码为0000;

2. 若存储空间为n bit,则反码的取值范围是 -2 n ~ 2 n -1。

3. 原码  + 其补码 = 0。

补码在以加法代替减法的运算的结果:

例如在计算0 = 1-1 = 1+(-1) = 0001 【原码】 + 1001 【原码】 = 0001 【反码】 + 1110 【反码】 = 0001 【补码】 + 1111 【补码】 = 0000 【补码】 = 0000 【原码】 =0, 发现通过补码来运算时结果恰恰正确。

真相:有符号整数其实是以补码的编码方式存储的 。因此C语言的int类型在32位OS上的值范围是:-2 n ~ 2 n -1。我们可以通过以下的C代码片段要验证:

 #include <stdout.h> #include <string.h>  int main(){   int f = -1;   unsigned long l;   int i;   char s[32];    memcpy(&l, &f, 4);    for (i = 31; i >=0; --i){        if (l % 2 == 1){          s[i] = '1';        }        else{          s[i] = '0';        }        l /= 2;   }   s[32] = '/0';   printf("%s/n", s);   return 0; } 

标准输出为:11111111111111111111111111111111(若为原码则应该是10000000000000000000000000001)

到这里我们对原码、反码和补码有一定程度的了解,并通过死记硬背的传统学习方法答对考题应该就不成问题了。但若要自圆其说则不可避免地需要解答以下问题:

1. 为什么补码的方式能解决以加法替代减法时所产生的问题?

下面我们一起来探讨和推导一下吧。

Theory

Modulus

模,是指一个计量系统的计数范围,而模则是产生“溢出”的量。

以时钟为例,时钟的计数范围是0~11,而模(产生“溢出”的量)是12。现在我们将时针从4点逆时针移动2格,和顺时针移动10格,得到的结果均是一样的。以算术公式表示则是4-2和4+10,一眼看出4-2明显不等于4+10,那为什么时钟上两者结果却是相同的呢?

那是“模”在作怪。当运算结果超出计数范围时,则会执行求模运算,4+10=14>12,12求模后得到2=4+(-2)。这时你会发现 负数的补数必定是正数 ,那么就解决了需要以正数表示负数的需求。接下来就要验证以补数解决以正数表示负数后,参与加法运算是否有问题了。

在深入之前,请大家先了解一下理论:

补数/补码/二补码,若A、B除以M为模执行求模运算后的结果相等,则A与B互为补数,公式:a≡b(mod m)。

求模公式:mod = a - m * La/mJ,其中LJ代表“取下界”符号。(注意:%是取余而不是取模数的运算符,而求模和取余在本质上是不同的)

以下以JS来描述

 /**  * @description 求模  * @method mod  * @public  * @param {Number} o - 操作数  * @param {Number} m - 模,取值范围:除零外的数字(整数、小数、正数和负数)  * @returns {Number} - 取模结果的符号与模的符号保持一致  */ var mod = (o/*perand*/, m/*odulus*/) => {     if (0 == m) throw TypeError('argument modulus must not be zero!')     return o - m * Math.floor(o/m) }  /**  * @description 求余  * @method rem  * @public  * @param {Number} dividend - 除数  * @param {Number} divisor - 被除数,取值范围:除零外的数字(整数、小数、正数和负数)  * @returns {Number} remainder - 余数,符号与除数的符号保持一致  */ var rem = (dividend, divisor) => {     if (0 == divisor) throw TypeError('argument divisor must not be zero!')     return dividend - divisor * Math.trunc(dividend/divisor)     } 

补数定理:

1. 反身性:a≡a(mod m)

2. 对称性:若a≡b(mod m)。则b≡a(mod m)

3. 传递性:若a≡b(mod m),b≡c(mod m)。则a≡c(mod m)

4. 补数式相加:若a≡b(mod m), c≡d(mod m)。则a+c≡b+d(mod m),a-c≡b-d(mod m)

5. 补数式相乘:若a≡b(mod m), c≡d(mod m)。则ac≡bd(mod m)

6. 互为补数的绝对值相加等于模数:若a≡b(mod m),则m = |a| + |b|

7. 若a、b均为正数,则mod(a + b, m) = mod(a, m) + mod(b, m)

Derivation

有了上述模数的理论后我们可以挽起衣袖开始推导了!

首先假设现在以n位二进制位来存储数据,其中最左一位为符号位,那么模则是2n-1。然后以a表示某正整数,b表示某负整数,并且c为b的补数。

1. 整理出 b≡c(mod 2 n-1 ),a≡(mod 2 n-1 )

2. 根据补数式相加得到 a+b≡a+c(mod 2 n-1 )

3. 即 mod(a+b, 2 n-1 ) = mod(a+c, 2 n-1 )

4. 回顾模的定义“模,是指一个计量系统的计数范围,而模则是产生“溢出”的量”,可知当运算过程中产生“溢出”操作,实质上就是执行取模运算。而我们的存储空间是固定为n位二进制位,因此 运算的最后一步默认就是取模运算 。因此a+b与a+c在存储空间固定的前提下,最终结果必然相等。

上面已经证明了以补数来实现减法加法化,以正数表示负数的有效性。那下面我们来看看将原码转换为补码的规则为什么是成立的。

假设以n位二进制位来存储数据,其中最左一位为符号位

模 = 2 n-1 = 1 + 1*2 + 1*2 2 + ...... + 1*2 n-2 + 1

某负数原码a = k 0 + k 1 *2 + k 2 *2 2 + ...... + k n-2 *2 n-2

根据“互为补数的绝对值相加等于模数:若a≡b(mod m),则m = |a| + |b|”

a的补码 = 2 n-1 - a = (1-k 0 ) + (1-k 1 )*2 + (1-k 2 )*2 2 + ...... + (1-k n-2 )*2 n-2 + 1

由于k 0 ,k 1 等的值不是0就是1,因此等价于作取反操作,然后最后再加1。

Conclusion

本文尝试以相对全面的角度描述原码、反码和补码,若有纰漏请给位指正。

尊重原创,转载请注明来自:肥子John^_^ http://www.cnblogs.com/fsjohnhuang/p/5060242.html

Thanks

http://baike.baidu.com/link?url=aGfE7C12rMLNpPVdMZcKlS9JkQnMRe9iiiUUTnQzLSO8PkKE5dbPtf_dtTUwDORVIehhAJ6jr4BK6v0JfyW9l_#4

http://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html

正文到此结束
Loading...