数学 细说计算机底层整型编码机制

lanzhiheng · 2019年02月14日 · 最后由 heroyct 回复于 2019年02月25日 · 6900 次阅读

computed

如今计算机的抽象级别越来越高,越发少人关注在计算机底层发生了什么事情,其实底层也有些很有意思的东西。这篇文章主要想科普一下整型在计算机硬件中的相关实现,它是以什么方式来存储的?如何区别正负数?硬件会怎么去解释相关的位串?

无符号数

在现代编程语言中,支持无符号数的语言已经比较少了。常见的就只有 C/C++,它们可以通过unsigned关键字定义无符号相关的数据类型。无符号整型与有符号整型最大的区别就是对相同的二进制位串解读方式不一样。所有的无符号数都是非负数,因为它是没有符号的。如果我们要用位长为w的空间来存储整型,以无符号的方式来解读的话第k位的权重都是2 ^ k,其中最高有效位的权重为2 ^ (w - 1)

举个具体点的例子,假设二进制串11000001所代表的是一个无符号数,由于它是 8 位长,所以最高有效位的权重是2 ^ (8 - 1) = 128,第 0 位的权重是2 ^ 0 = 1,第一位的权重是2 ^ 1 = 2,以此类推。最终代入公式可得

2 ^ 7 * 1 + 2 ^ 6 * 1 + 2 ^ 5 * 0 + 2 ^ 4 * 0 + 2 ^ 3 * 0 + 2 ^ 2 * 0 + 2 ^ 1 * 0 + 2 ^ 0 * 1 = 193

因此,二进制串11000001所对应的无符号数为193。还可以猜测出在 8 位的空间内最小的无符号数是 0,它的二进制表示为00000000,最大的无符号数是 255,它的二进制表示为11111111

虽说,在日常的业务逻辑中用到无符号数的机会已经不多了,不过在计算机底层你还是可以经常看到它的身影。假设我们要用以下的 16 位的二进制串来代表整型

11100000 10000000

其中高 8 位为11100000,低 8 位为10000000。不管这个 16 位的位串最终会被解读成有符号数还是无符号数,低 8 位始终都可以看作一个无符号数128。同理,如果是一个代表整型的 32 位二进制串

11100000 10000000 11100000 10000000

那么它的低 24 位就可以看作一个无符号数了。从这个角度来看,虽说我们平时不会直接操作无符号数,但实际上无符号数在计算机底层还是“大量存在”的。

有符号数 - 原码,反码,补码

如果在整型的世界中只有无符号数的话,那么似乎难以构建一个庞大的系统,毕竟有许多数据或者运算都要借助负数。接下来我想简单介绍一下在计算机底层要表示一个有符号的整型主要有哪些策略。

1. 原码(Sign-Magnitude)

这种编码方式比较好理解,前面所说的无符号数之所以无法表示负数,那是因为我们并没有留下一个特殊的位置用于标识它到底是大于 0 的还是小于 0 的。而原码的基本原理其实就是分配一个位用来标识该数到底是正数还是负数

同样用 8 位空间来举例子,采用最高有效位来作为符号位,其他位用于权重计算,那么不难看出它所能表示的最大的数就是01111111,最小的数就是11111111。它们的值分别为127-127,不过如今的大多数机器都不是以这种方式来表示有符号整型的。而且这种方式还有个比较突出的特性,如果要表示数字 0,将有两种二进制编码方式,+0 会表示为00000000,-0 会表示为10000000。也许这种不唯一性也是它没有在整型的领域被广泛采用的原因吧。不过原码这种编码方式在浮点数里面会用到,这个以后有机会再说。

2. 反码 (Ones' complement)

记得是小学数学里面就已经出现了减法运算了,但是我是到了初中才接触到负数的概念。一个负数其实就是某个特定正数的相反数。正数56的取反结果就是-56,那么在二进制里面怎么取反呢?一个可行的办法就是按位取反,这也是反码的最直观的特征。00111000所代表的数值是56,如果要用反码来表示-56直接把56的二进制串按位取反即可11000111

不过上面所说的只是反码给人最直观的感觉,实际上它还是需要一定的数学支持的。在反码里面最高有效位的权重为- (2 ^ (w - 1) - 1),如果是一个 8 位的位串,最高有效位的权重为-127,其他位的计算方式跟无符号数一样。那么把前面所得的11000111二进制串代入公式可得

-(2 ^ 7 - 1) * 1 + 2 ^ 6 * 1 + 2 ^ 5 * 0 + 2 ^ 4 * 0 + 2 ^ 3 * 0 + 2 ^ 2 * 1 + 2 ^ 1 * 1 + 2 ^ 0 * 1 = -56

结果刚好是-56。这个时候,不难推断出一个字节所能表示的最大值为127(01111111),最小值为-127(10000000)。反码所能够表示的数值范围跟原码一样,只是某些数值在底层的编码方式会有所不同。此外,它跟原码都有同样的问题,就是对数字 0 有两种不同的二进制表示方式。在反码中 +0 表示为00000000,-0 表示为11111111

3. 补码 (Two's complement)

理论上,原码和反码都能够用来表示有符号数,不过他们都有奇怪的属性,就是对数字 0 分别会有两种不同的位模式。而这里要说的补码就能很好地解决这种问题。

与原码,反码类似,补码也是要靠最高有效位来影响数值的正负。对于长度为 w 位的补码表示,最高有效位为w - 1,最高有效位的权重为2 ^ (w - 1)。不难推断出在一个字节长的空间内,补码所能够表示的有符号数最大值为127(011111111),最小值为-128(11111111)。

如果要用补码来表示整型56,它所对应的二进制串依然是00111000。如果要表示-56则有

- 2 ^ 7 * 1 + 2 ^ 6 * 1 + 2 ^ 5 * 0 + 2 ^ 4 * 0 + 2 ^ 3 * 1 + 2 ^ 2 * 0 + 2 ^ 1 * 0 + 2 ^ 0 * 0 = -56

因此,-56的补码表示为11001000。在补码下-5656两个数值对应的位模式之间有以下关系

11001000 + 00111000 = 1 00000000

它们相加恰好等于1 00000000,然而在底层我们只用了一个字节的空间来存储它们相加的结果,因此需要对最终结果进行截断处理。最终得到的结果是00000000。是不是有点意思?截断之后恰好就是56 + (-56) = 0,这也是补码优雅之处。

与原码,反码相比,补码较大的好处就是映射具有唯一性,对于数值 0 不会再有两种不同的表示方式了。在位长为w的空间中,补码能够多表示一个数值- 2 ^ (w - 1)。此外,它能表示的数值恰好一半是非负数0 ~ 2 ^ (w - 1) - 1,另一半是负数- (2 ^ (w - 1)) ~ -1。对 8 位二进制串来说则是非负数范围是0 ~ 127,负数范围是-128 ~ -1

无符号与补码的关系

在相同的位模式下,无符号表示与补码表示最大的区别就是最高有效位的权重不同。位长为w的无符号表示中,最高有效位的权重为2 ^ (w - 1),而补码表示的最高有效位权重为-2 ^ (w - 1)。当最高有效位为 0 时,它们所表示的数值相同。只有在最高有效位为 1 的时候,两者之间所表示的数值才会有所不同,这个时候它们所表示的数值之间相差|2 ^ (w - 1) - (- 2 ^ (w - 1))| = 2 ^ w

简单举两个例子

a. 最高位为 0

以无符号的方式来解读二进制位模式00011110,代入公式可得

2 ^ 7 * 0 + 2 ^ 6 * 0 + 2 + 2 ^ 5 * 0 + 2 ^ 4 * 1 + 2 ^ 3 * 1 + 2 ^ 2 * 1 + 2 ^ 1 * 1 + 2 ^ 0 * 0 = 30

以补码的方式来解读可得

-2 ^ 7 * 0 + 2 ^ 6 * 0 + 2 + 2 ^ 5 * 0 + 2 ^ 4 * 1 + 2 ^ 3 * 1 + 2 ^ 2 * 1 + 2 ^ 1 * 1 + 2 ^ 0 * 0 = 30

此时最高有效位为 0,因此它的权重对大局来说没有任何影响。二进制位模式00011110无论是以无符号的方式去解读还是以补码,原码,反码的方式去解读,它所代表的数值都是30

b. 最高位为 1

当最高有效位为 1 的时候两者之间差别就比较大了。这个时候补码所表示的总是负数。

对二进制位模式10001001,以无符号的形式进行转换,代入公式可得

2 ^ 7 * 1 + 2 ^ 6 * 0 + 2 ^ 5 * 0 + 2 ^ 4 * 0 + 2 ^ 3 * 1 + 2 ^ 2 * 0 + 2 ^ 1 * 0 + 2 ^ 0 * 1 = 137

而以补码的方式去解读则会有

- 2 ^ 7 * 1 + 2 ^ 6 * 0 + 2 ^ 5 * 0 + 2 ^ 4 * 0 + 2 ^ 3 * 1 + 2 ^ 2 * 0 + 2 ^ 1 * 0 + 2 ^ 0 * 1 = -119

两种换算方式所得到的数值相差甚远,前面推导过两者相差2 ^ w。这个例子中就是137 - (-119) = 256,恰好是2 ^ 8

总结

这篇文章主要简单介绍一下在要用二进制来表示整数有哪几种不同的编码策略,虽说大多数情况下我们都不需要关心底层到底发生了什么(除非你是在用 C/C++ 来编写代码),不过当作简单的科普知识来了解一下还是挺有趣的。

写的挺好

【编码的奥秘】感觉这本书写的很通俗易懂,有兴趣的可以看看

heroyct 回复

上京东看了一下这本书已经缺货了。🐄

原码中的 -0 应该为 1000000 吧。文中写的是 11111111

glz1992 回复

对的,已经更正。

理解了这个以后,就能明白整数加整数可能会是负数是什么原因

#include <stdio.h>

int main()
{
    int f1 = 2147483647;
    int f2 = 1;

    printf("%d", f1 + f2);

    return 0;
}

输出 -2147483648
需要 登录 后方可回复, 如果你还没有账号请 注册新账号