这篇博客将根据《深入理解计算机系统》(Computer Systems: A Programmer’s Perspective, CS: APP)总结“第二章: 信息的表示和处理”的知识点。

信息的表示和处理

信息存储

基本概念

大多数计算机使用8位的块，也可以叫做字节(byte)，来作为最小的可寻址的存储器单位。

机器程序将存储器视为一个很大的字节数组，也被称之为虚拟存储器(virtual memory)。

存储器的每一个字节都由一个唯一的数字来标识，称为地址(address)。所有可能的地址集合被称为虚拟地址空间(virtual address space)。

编译器和运行时系统的一个任务就是将这个存储空间划分为更可管理的单元，来存放不同的程序对象(program object)，这种管理完全是在虚拟地址空间里完成的。C语言中的一个指针的值(无论它指向的是整数、结构还是其他信息)都是某个存储块的第一个字节的虚拟地址。

C编译器会把每个指针和类型信息联系起来，这样就可以根据指针的类型生成不同的机器级代码来访问存储在指针所指向位置处的值。

进制

一个字节包括8位，在二进制表示法中，它的值域就是$00000000_2 \sim 11111111_2$，如果看成十进制整数，值域就是$0_{10} \sim 255_{10}$，16进制可以更好的来描述位模式，它的值域是$00_{16} \sim FF_{16}$。我们会在一个数字前加上0b表示这个数是二进制，加上0x表示这个数是十六进制。

对于二进制和十六进制的转化非常简单，因为我们只需要记住十六进制数字0代表四个二进制0就可以。也就是说我们可以简单理解为十六进制的1个位数可以转化为二进制的4个位数。而对于十进制转化成二进制或十六进制也十分简单。比如$x = 2048 = 2^{11}$，我们有$n = 11 = 3 + 4 * 2$，于是可以得到十六进制的表示$0x800$。

使用二进制和十六进制表示的场景

使用二进制表示的场景:

  • 位操作和位掩码: 二进制表示法非常适合进行位操作，例如按位与、按位或、按位异或和移位操作。使用二进制表示可以更直观地看到各个位的状态。
  • 嵌入式编程: 在嵌入式编程中，直接操作硬件寄存器往往需要使用二进制表示，因为每个位代表特定的硬件功能或状态。
  • 调试和分析:当需要调试或分析低级数据（例如，网络协议中的位字段，图像处理中的像素数据），使用二进制表示可以更清晰地看到每个位的值。

使用十六进制表示的场景:

  • 使用大整数: 使用十六进制表示可以更简洁地表示较大的整数值。每个十六进制数字表示四个二进制位，因此相比二进制表示法更紧凑。
  • 内存地址: 内存地址通常用十六进制表示，因为这样更紧凑且易于阅读。调试工具和内存查看器通常使用十六进制来显示内存地址。
  • 颜色值: 在图形编程和网页设计中，颜色值通常使用十六进制表示，因为每个颜色通道（红、绿、蓝）可以用两个十六进制数字表示。
  • 表示字节数据: 在处理字节数据（如文件头、网络包、加密数据）时，十六进制表示更紧凑且易于与规范文档对照。
  • 编码和解码: 在数据编码和解码过程中，十六进制表示常用于表示原始字节数据。

数据大小

每台计算机都有一个字长(word size)，来指明整数和指针数据的标称大小(nominal size)。字长决定的最终逃的系统参数就是虚拟地址空间的最大大小。换言之，对于一个字长为n的机器而言，虚拟地址的范围为$0 \sim 2^n - 1$

我们说的32位计算机和64位计算机，指的是32位的处理器和64位的处理器，这里的位是字长。计算机字长(机器字长)取决于数据总线的宽度，通常就是CPU一次能处理的数据的位数(CPU位数)。下面有一个等式关系:

​ CPU位数 = CPU中寄存器的位数 = CPU能够一次并行处理的数据宽度(位数) = 数据总线宽度

虽然64位处理器可以支持非常大的虚拟地址空间，但操作系统和硬件实际分配和使用的虚拟地址空间会受限于当前技术和需求。例如，一些操作系统可能只实现了48位或52位的虚拟地址空间，即使处理器支持更大的范围。也就是说64位处理器的理论上虚拟空间可以达到$2^{64}$，不过目前情况下许多现代操作系统在64位模式下实现了48位的虚拟地址空间，提供$2^{48}$字节（256TB）的虚拟地址空间。

通过一个例子可以非常直观的理解上面的概念。假如有一个32位处理器，它的最大虚拟地址空间为$2^{32} = 4GB$，那么如果给他分配一个8GB的内存条，由于32位处理器的地址总线限制，它们最多只能直接寻址4GB的物理内存，也就是其无法处理超过4GB的那部分内存。

过去32位处理器一直都是标准的情况。32位处理器中C语言的long int是4 bytes，而64位处理器中C语言的long int是8 bytes，等等。这种不一致会导致之前在32位处理器编写的程序如果移植到64位处理器中时，就会因为字长的问题导致错误。

寻址和字节顺序

对于跨越多字节(大于1字节)的程序对象，我们需要建立规则:这个对象的地址是什么，我们在存储器中该如何对这些字节进行排序。在几乎所有的机器上，多字节对象都被存储为连续的字节序列。对象的地址为所使用字节序列中最小的地址。例如一个类型为int的变量x的地址是0x00，那么表达式&x的值为0x00，x的四字节将被存储在存储器的0x100、0x101、0x102和0x103的位置。

对表示一个对象的字节序列排序，有两种通用规则。例如一个w位的整数，有位表示$[x_{w-1}, x_{w-2}, …, x_1, x_0]$，其中$x_{w-1}$是最高有效位，而$x_0$是最低有效位。假设w是8的倍数，那么这些位就被分组成为字节。，其中最高有效字节包含了位$[x_{w-1}, x_{w-2}, …, x_{w-8}]$，而最低有效字节包含位$[x_7, x_6, …, x_0]$。某些机器选择在存储器中按照从最低有效字节到最高有效字节的顺序存储对象，而一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则被称为小端法(little endian)，后一种规则被称为大端法(big endian)。

运算

下面的运算是C语言的语法:

  • 二进制值1和0表示逻辑值True和False.运算符~、&、|、和^一次表示逻辑运算NOT, AND, OR和EXCLUSIVE-OR(异或，相同为True，不相同为False).
  • 与逻辑运算不同，布尔运算是对二进制中的每一个位进行的运算。这些运算能运用到任何的“整形”数据类型上。
  • 逻辑运算符||、&&和!分对应于命题逻辑的OR、AND和NOT运算。逻辑运算认为所有非零的参数都表示为True。此外，在多个逻辑判断中，如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。

C语言还提供了一系列的移位运算。对于一个位表示为$[x_{n-1}, x_{n-2}, …, x_0]$的运算符$x$，$x « k$会生成一个值，其位表示为$[x_{n-k-1}, x_{n-k-2}, …, x_0, 0, …, 0]$。简而言之，x向左移动k位，丢弃k个最高位，并在右端补了k个0。移位运算从左至右，运算符的优先级为: 1«5-1应该按照1«(5-1)而不是(1«5)-1。

对于右移运算，机器支持逻辑右移运算和算数右移运算。逻辑右移在左端补k个0，得到的结果是$[0, …, 0, x_{n-1}, x_{n-2}, …, x_n]$。算数右移是在左端补k个最高有效位的拷贝，得到的结果是$[x_{n-1}, …, x_{n-1}, x_{n-1}, x_{n-2}, …, x_k]$。这种做法看上去比较奇特，但是我们会发现它对于有符号整数数据的运算十分有用。

C语言的标准并没有明确定义应该使用哪种类型的右移。对于无符号的数据(以限定词unsigned声明的整型对象)，右移必须是逻辑的。而对于有符号数据(默认)，算数的活着逻辑的右移都可以。然而，这意味着任何假设一种或者另一种右移形式的代码都会潜在的遇到可移植性问题。实际上，几乎所有编译器/机器组合都对有符号数据使用算数右移。简而言之我们可以记为: 无符号数据使用逻辑右移，有符号数据使用算数右移。

补充: 取模运算可能会遇到负数问题(取模主要是用于计算机术语中。取余则更多是数学概念)，泛化取模计算公式如下: $$ x \mod y = x - \lfloor x / y \rfloor \times y $$ 例如: $$ 5 \mod 3 = 5 - \lfloor 5 / 3 \rfloor \times 3 = 2 \ 5 \mod -3 = 5 - \lfloor 5 / (-3) \rfloor \times (-3) = -1 \ -5 \mod 3 = -5 - \lfloor -5 / 3 \rfloor \times 3 = 1 \ -5 mod -3 = -5 - \lfloor -5 / (-3) \rfloor \times (-3) = -2 $$

编码表示

无符号二进制表示

如果一个整数数据类型有w位，我们可以将位向量写成$\vec{x}$来表示整个向量，或者写成$[x_{w-1}, x_{w-2}, …, x_0]$来表示向量中的每一位。把$\vec{x}$看做一个写成二进制表示的数，我们就获得了$\vec{x}$的无符号表示。我们用函数$B2U_w$(代表“无符号的二进制”，长度为w)来表示这种形式

$$ B2U_w(\vec{x}) \doteq \sum_{i=0}^{w-1}x_i2^i $$ 这个等式中$\doteq$表示左手边被定义为右手边。函数$B2U_w$将一个长度为$w$的0、1串映射到非负整数。它的最小值用位向量$[00\dots0]$，它的最大值是用位向量$[11 \dots 1]$来表示，也就是$\sum^{w-1}_{i=0} 2^i = 2^w - 1$。所以，函数$B2U_w$能够被定义为一个(双)映射:

$$ B2U_w: {0, 1}_w \longleftrightarrow { 0, \dots 2^w - 1 } $$

二进制补码(two’s-complement)

如果要表示负数值的话，最常见的有符号数的计算机表示方式就是二进制补码形式。对于有符号的数来说，最高位会被定义为负权(negative weight)，用于表示正负号。我们用函数$B2T_w$(表示“二进制到二进制补码”，长度为w)来表示这种解释: $$ B2T_2(\vec{x}) \doteq -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i2^i $$ 最高有效位也被称为符号位(sign bit)。当被设置为1时，表示值为负，当被设置为0时，表示为正。它能表示的最小值是位向量$[10\dots0]$，其整数值为$TMin_w \doteq -2^{w-1}$，最大值是位向量$[01\dots1]$，其整数值为$TMax_w \doteq \sum^{w-2}_{i=0}2^i = 2^{w-1} - 1$。所以函数$B2T_w$也同样是一个(双)映射: $$ B2U_w: { 0, 1 }^w \longleftrightarrow { -2^{w-1}, \dots, 2^{w-1} - 1} $$ 更直观的求某个负整数的二进制的方式(求这个负整数去掉负值的对应正整数的补码)是先得到这个负整数去掉负数部分的二进制值，然后对这个值的每一个位取反(0->1, 1->0)，然后在得到的结果上加1，就是这个负整数的二进制表示。补码表示法使得加法和减法运算可以统一处理，不需要单独处理减法。即A - B可以表示为A + (-B)。

二进制反码(one’s-complement)与符号数值（Sign-Magnitude)

二进制反码和二进制补码类似，不过最高有效位的权是$-(2^{w-1}-1)$而不是$-2^{w-1}$: $$ B2O_w(\vec{x}) \doteq -x_{w-1}(2^{w-1} - 1) + \sum^{w-2}_{i=0}x_i2^i $$ 简而言之，二进制反码就是对某个负整数求去掉符号位的数的每一个位取反，并不需要在之后的结果上加1。

符号数值的表示为: 最高有效位是符号位，剩下的位则不变: $$ B2S_w(\vec{x}) \doteq (-1)^{x_{w-1}} \cdot (\sum^{w-2}_{i=0}x_i2^i) $$