第 2 章信息的表示和处理

在第一章中提到，计算机是以二进制（位）进行存储信息，然而，当把位组合在一起，再加上某种解释（interpretation），即赋予不同的可能位模式以含意，我们就能够表示任何有限集合的元素。

在本章中着重讲解如何进行解释，研究三种重要的数字表示方式：

无符号（unsigned）：基于传统的二进制表示法，表示大于或者等于零的数字
补码（two’s-complement）：是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。
浮点数（floating-point）：表示实数的科学记数法的以 2 为基数的版本。

数字表示时要注意溢出的问题

2.1 信息存储

大多数计算机使用 8 位的块，或者字节（byte），作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。顾名思义，这个内存地址空间只是一个展现给机器级程序的概念性映像。

2.1.1 十六进制表示法

2.1.2 字数据大小

每台计算机都有一个字长（32位或64位），指明指针数据的标称大小。因为虚拟地址是以一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的大小。也就是说，对于一个字长为 ${\omega}$ 的机器而言，虚拟地址的范围为 $0$ 到 $2^{\omega} - 1$ ，程序最多访问 $2^{\omega}$ 个字节。

为什么字长是关键参数

操作系统映射：操作系统通过页表将虚拟地址映射到物理内存，但页表结构和分页规则可能进一步限制实际可用空间

硬件限制：CPU的地址总线宽度由字长决定，直接限制了虚拟地址的位数

由于同一数据类型在不同的编译器或者操作系统下可能占据不同的大小，ISO C99引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化。如，int32_t 和 int64_t分别为4个字节和8个字节。

2.1.3 寻址和字节顺序

排列表示一个对象有两个通用规则。

小端法：选择在内存中按照从低到高的顺序存储对象
大端法：选择在内存中按照从最高有效字节到最低有效字节存储
在上图的例子中，int 型变量位于地址0x100 处，它的十六进制数值为0x01234567,小端法中低位字节在低地址，而大端法则是高位字节在低地址。

注意：在十六进制数 0x01234567 中，低位字节是 0x67。而在内存中，低地址是0x100

不同的字节顺序可能带来的问题：

网络传输中，从一个小端法机器产生的数据被传送到大端法机器中

#include <stdio.h>

typedef unsigned char *byte_pointer; // 定义了字节指针类型，用于以字节为单位访问内存数据（无符号保证正确显示二进制补码）
void show_bytes(byte_pointer start, size_t len)
/*
 * 接收任意内存地址的起始指针
 * 按字节遍历内存区域
 */
{
    size_t i;
    for (i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x) { show_bytes((byte_pointer)&x, sizeof(int)); }
void show_float(float x) { show_bytes((byte_pointer)&x, sizeof(float)); }
void show_pointer(void *x) { show_bytes((byte_pointer)&x, sizeof(void *)); }

int main()
{
    int x = 12345;
    byte_pointer p = (byte_pointer)&x;
    show_bytes(p, 4); // 显示int类型的4字节内存布局

    show_int(-12345);    // 负数补码测试
    show_float(12345.0); // 浮点数表示测试
    
    int *ptr = &x;
    show_pointer(ptr); // 指针地址测试
}

程序运行的结果如下：

$ ./2_1_3
 39 30 00 00    // main()中的show_bytes(p,4)
 c7 cf ff ff    // show_int(-12345)
 00 e4 40 46    // show_float(12345.0)
 bc ae 5f 6b 01 00 00 00  // show_pointer(ptr)

十进制的 12345 在 16 进制中表示为：0x3039，说明在我的计算机中数据以小端法进行存储（低位字节在低地址），即内存布局为[0x39][0x30][0x00][0x00]。

负数补码测试
1
c7 cf ff ff

十进制-12345的补码计算：
- 原码：0x3039 → 00110000 00111001
- 反码：11001111 11000110
- 补码：11001111 11000111 → 0xFFFFC7CF
小端存储：0xCF 0xC7 0xFF 0xFF → 逆序显示为 c7 cf ff ff

浮点数测试
1
00 e4 40 46

12345.0的IEEE754表示：
- 二进制：1.00110000011001×2¹³
- 指数：127 + 13 = 140 → 0x8C
- 尾数：00110000011001000000000
完整32位：0 10001100 00110000011001000000000 → 0x4640E400
小端存储：00 e4 40 46

指针测试
1
bc ae 5f 6b 01 00 00 00

64位系统指针示例：
- 假设实际地址：0x000000016B5FAEBC
- 小端存储分解：
  1
  bc ae 5f 6b 01 00 00 00 // 低地址 → 高地址
每个字节对应地址的16进制段

关键发现

字节序验证：所有输出均呈现小端模式特征（低位在前）

类型差异：相同数值（12345）在不同类型中的二进制表示完全不同

地址长度：指针输出显示8字节，表明是在64位系统下编译

而在不同的机器中，显示如下图：

2.1.4 表示字符串

C 语⾔中字符串被编码为⼀个以 null（其值 0 ）字符结尾的字符数组。字符一般以ASCII字符码表示。

2.1.5 表示代码

相同代码在不同平台编译后的机器码可能完全不一样，因此二进制代码很少能在不同的机器和操作系统组合之间移植。

2.1.6 布尔代数简介

最后一个是异或

2.1.7 C语言中的位级运算

C语言的一个很有用的特性就是它支持按位布尔运算。

Q2.10

void inplace_swap(int *x, int *y) {
	*y = *x ^ *y;
	*x = *x ^ *y;
	*y = *x ^ *y;
}

基于 a ^ a = 0这一特性实现两个数字的交换。

Q2.11

void reverse_array(int a[], int cnt) {
	int first, last;
	for (first = 0, last = cnt - 1; fitst <= last; first++, last--) {
		inplace_swap(&a[first], &a[last]);
	}
}

上面这个数组逆序的代码，偶数时可以正常工作，但是基数时，如1,2,3处理后会得到3，0，1。修改办法也很简单，将判断条件修改为first < last。

2.1.8 C语言的逻辑运算

2.1.9 C语言中的移位运算

有符号数：用符号位（正数为0，负数为1）填充（算术右移）。
无符号数：用0填充（逻辑右移）。例如：-5 >> 1（补码11111011右移1位）结果为11111101（补码，十进制-3）。

深入理解计算机系统（二）—— 信息存储

第 2 章 信息的表示和处理