Zohar's blog

信息的表示与处理 - 数的编码

Computercomputernumber codingSign-MagnitudeOnes's ComplementTwo's-complementIntegerFloating Point NumberOffset binary计算机组成数的编码原码反码补码整数浮点数移码偏置码

对于拥有十只手指的人类而言,十进制是理所当然的存在。但对于计算机而言,二进制是最优雅最无可挑剔的存在。或许转向二进制,是人类世界的下一次革命

信息存储

基本内存单位与内存地址

由于当代计算机是基于二进制的机器,因此计算机的最小表示单位为{位}(Bit),又称比特

由于我们需要准确地在找到我们存储在计算机上的每一个信息,因此我们需要进行寻址操作。但基于位的寻址操作带来的后果是, 我们需要使用太多的位来来记录每一个地址空间,例如一个 1MB 的存储空间我们需要使用 即 24 bit 长的数来表示每一个位的地址。 这显然是极不划算的。

因此当代绝大多数计算机使用 8 bit 的块,即{字节}(Byte) 作为最小的可寻址单位,即每 8 个连续的 bit 作为基本内存单位, 这样 1MB 的存储空间我们只需要 即 21 bit 长度的数来表示每一个字节的地址。

因此,基本所有程序都将内存视为一个庞大且连续的字节数组,我们称之为{虚拟内存}(Virtual Memory),每一个字节都由唯一的整数序号进行标识, 我们称之为{内存地址}(Vertual Address),所有可能地址的集合我们称之为{虚拟地址空间}(Virtual address space)。

指针作为 C/C++ 的重要特性,用来指向其他变量的内存地址。也是变量的一种,其类型为所指向对象的类型,其值为所指向对象的地址。 而在其他语言中的“引用”概念与之类似,而 C++ 中本来就有对“引用”的定义。引用本质上是指针的一种。即值不为空的常指针。也就是引用是不可变的, 引用并不等于变量,Java 中变量名代表对象,实际上是变量中值保存为对象的引用,非常量的值是可以改变的,因此变量可以重新赋值为另一个对象的引用, 而引用 一直都没变,是不可变的。

字长

我们使用字节作为内存的基本单位,每个内存基本单位都有唯一的内存地址,如 0001, 0002, ..., 1111,因此我们需要使用一个整数类型来存储和表示这些内存地址。 而这个整型的长度我们称之为{字长}(word size),用于指明指针数据的{标称大小}(nominal size)。对于操作系统而言,32 位系统表示该系统字长为 32, 64位系统表示该系统字长为 64。

对于一个字长为 的机器,其虚拟地址范围为 ,如 32 位系统的可控内存长度就为 。64 位系统的可控内存长度为 16EB,约 Bytes。

字长较长的机器可以运行字长较短的程序,这是一种向后兼容,因为短字长机器的地址范围仅仅只是长字长机器地址范围的一小部分,而短字长机器是无法正常运行为高字长机器编写的程序的。

以下是在 32 位与 64 位操作系统中 C 语言各类型变量的存储空间大小

char short int long int32_t int64_t char* float double
1 2 4 4 4 8 4 4 8
1 2 4 8 4 8 8 4 8

寻址与字节顺序

对于{整型}(integer),我们常采用 4bytes 的空间来存储,因此整型共 32bit,按照基本内存单位分为 4 个部分,如 为:0x1A2B3C4D0x1A0x2B0x3C0x4D 组成,在内存中我们有两种存储方法,即两种字节顺序表示:

  • 0x1A 0x2B 0x3C 0x4D
  • 0x4D 0x3C 0x2B 0x1A

前者存储方式高位在前,我们称之为{大端法}(big endian),后者存储方式低位在前,我们称之为{小端法}(small endian)。

术语”大端“、”小端“源自于格列佛游记,记载了两个派别由于”该从哪一端打鸡蛋“这一问题从争执发展到战争。事实上对于字节顺序而言,大端小端同样是无意义的争论。 就算有争论,争得也是在计算机领域的发言权与影响力,而非大端小端这种问题。

无论是哪一种字节顺序,4 个部分在内存中是连续的这一点是毫无疑问的。因此,我们只需要知道确定第一个部分的地址,便可以根据类型连续读取这四个字节以或者这一整型变量。 因此我们所采用的寻址方式就如同指针的工作方式,存储该变量的类型 + 首个内存地址,我们即可正确的进行变量读写。

最为直观的是数组这一数据类型,面对成百上千个的数组成员,由于数组的实现同样是基于连续的内存空间,因此我们仅需获取 4 个数据就能正确的操作数组: 数组长度、数组变量类型、数组首个元素首个字节的地址(即数组的地址)、待操作元素的索引。

布尔代数

{布尔代数}(Boolean algebra)诞生于 1850 年左右,是定义在二元集合 {0, 1} 上的,为:

  • NOT:

  • AND:

  • OR:

  • EXCLUSIVE-OR:

以上四个布尔运算可以拓展到位向量的运算,位向量是固定长度为 、由 0 和 1 组成的串。 位向量的布尔运算可以定义成两个操作数的每个对应元素之间的运算。如 , 则

程序语言中的位运算中的 NOTANDORXOR 基于位向量的布尔运算,程序语言中的逻辑运算基于二元集合 {0, 1} 的布尔运算,为逻辑与&&、 逻辑或 ||、逻辑非 !

布尔环

移位运算

大多数编程语言提供了移位运算,对变量的位进行向左、向右的位移动。

  • 左移:对于一个操作数 a << k 的结果为

    即相当于把数 a 所有位数往左推 k 位,后面的低位补 k 个 0。若未溢出,相当于 a 乘以 ,若溢出,则高位丢弃,数可能变小也可能变大。

  • 右移:以左移类推,如 a >> k 般的右移就是把数 a 所有位数往右推动 k 位,同理可理解为 a 除以 ,但对于右移而言,计算机支持两种移动方式

    • 逻辑右移:左端高位补 k 个 0。
    • 算术右移:左端高位补 k 个最高有效位的值,即原最高位的值。

    有符号整数采用最高位表示数的正负,算术右移的目标就是为了保持右移之后该数的正负与原先一致,且这一点在以补码表示数值的机器上非常有用,补码在下文会有详细介绍。

    操作 [0110 0011] 99 [1001 0101] -107
    x « 4 [0011 0000] 48 [0101 0000] 80
    x » 4(逻辑右移) [0000 0110] 6 [0000 1001] 9
    x » 4(算术右移) [0000 0110] 6 [1111 1001] -7

    第三、五列是这些二进制以补码解释对应的十进制值,可以看到,0b(1001 0101) 算术右移四位的结果最终仍为负数。

    部分语言仅支持右移中的某一种,而基本上所有这些语言都采用的了算术右移这种方式。且对于无符号数而言,算术右移的效果等同于逻辑右移。 而另一部分语言选择了二者都支持,如 Java 采用 >> 表示算术右移,采用 >>> 表示逻辑右移。

整数表示

无符号数编码

把向量 中每一个元素都取值 0 或 1,当作是表示二进制的数, 那么 就可以看作是一个数的二进制表示了。我们可以定义一个函数 用于计算无符号数编码的十进制表示:

即二进制转十进制的常用方法,每一个元素代表 2 的幂方,运算后相加,代码实现为:

int B2U(char byte) {
    if (byte > 0) return byte;
    int res = 0;
    for (int i = 0; i < 8; ++i) {
        res += ((byte >> i) & 1) << i;
    }
    return res;
}