信息存储

现代计算机通常以 8bit 的块或者字节(byte)作为最小的可寻址内存单位,机器级程序将内存视为一个非常大的内存数组,称为 虚拟内存(virtual memory),内存中的每个字节由唯一 地址(address)标识,所有可能地址的集合称为 虚拟地址空间(virtual address space)。C 语言一个指针的值指向某个存储块的第一个字节的虚拟地址,C 编译器通过指针和指针的类型信息生成不同的机器级代码访问存储在指针所指向位置的值。

十六进制表示法

一个字节由8位组成,其在二进制表示中的值域为 \(00000000_2 \sim 11111111_2 \) ,十进制值域为 \(0_{10 } \sim 255_{10}\) ,两种符号表示法描述位模式比较不方便,因此引入了以16为基数的十六进制(hex)表示法,一个字节的值域用十六进制表示为:\( 00_{16} \sim FF_{16}\) 。C 语言以 0x开头的数字常量表示十六进制的值,如:0xFa1D37D。

image-20191123160456667

通过上表,可以轻松完成十六进制和二进制的转换,如下:

image-20191123160827700

二进制到十六进制的转化先以4位为一组分组再进行转换:

image-20191123160843651

当值x是2的非负次幂时,即 \(x=2^n\) ,x的二进制表示是1后面 n 个0,十六进制数字0代表4个二进制0,因此,当 n 表示 \(i+4j\),其中 \(0{\leq}i{\leq}3\) 时,可以把 x 写成开头为数字 1(i=0), 2(i=1), 4(i=2), 8(i=3),后面跟着 j 个十六进制 0 的格式,如 \(2048=2^{11}\),即\(n=11=3+4*2\) ,即其十六进制表示为 0x800。

十六进制和十进制的转换,如下:

  • 十进制转十六进制:反复用16 除十进制数 x,得到商 q和余数 r,即 \(x=q*16+r\) ,之后,十六进制数将 r 作为低位数字,并反复对 q 执行这个过程,如下:

image-20191123164358055

得到十进制数 314156 的十六进制表示为:0x4cb2c。

  • 十六进制转十进制:用相应 16 的幂乘十六机制数对应的位,如 0x7ae,其相应的十进制数为:\(7*16^2+10*16+15=1967\)

字数据大小

虚拟地址空间的最大大小取决于计算机的字长(word size),对于一个 \(\omega\) 位的机器而言,虚拟地址范围为 \(0 \sim 2^{\omega}-1\) ,程序最多访问 \(2_{\omega}\)个字节。

计算机和编译器支持多种不同方式编码的数字格式,以下为基本C数据类型的在 32bit和64bit 程序的典型值:

image-20191123165236594

寻址和字节顺序

跨多字节的程序对象,我们建立了两个规则:即对象的地址,以及在内存中如何排列这些字节。

如一个int类型的变量 x ,其地址 &x 为 0x100,则其4个字节被存储在 0x100, 0x101, 0x102, 0x103 4个地址上。考虑一个 \(\omega\) 位的整数,位表示为\([x_{\omega-1}, x_{\omega-2}, ..., x_1, x_0]\) ,其排列方式有以下两种:

  • 小端法(little endian):在内存中按照从最低有效字节到最高有效字节存储对象

image-20191123204634811

  • 大端法(big endian):在内存中按照最高有效字节到最低有效字节存储对象

image-20191123204614720

字节顺序在以下几种情况会成为问题:

  • 在不同机器间传递二进制数据
  • 阅读调试机器级程序
  • 编写规避正常的类型系统程序

以下是一段 C 代码程序,其用强制类型转换来规避类型系统,展现了在不同的机器上运行的结果:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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++) {
    // %.2x 表示整数必须用至少两个数字的十六进制格式输出
    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 *));
}

// 打印示例数据对象的字节表示
void test_show_bytes(int val) {
  int ival = val;
  float fval = (float) ival;
  int *pval = &ival;
  show_int(ival);
  show_float(fval);
  show_pointer(pval);
}

image-20191123234219186

Linux32, Window, Linux64 中,最低有效位 0x39 最先输出,说明它们是小端法机器,而 Sun 则相反,为大端法机器,指针的地址在不同机器/操作系统有不一样的值,其位数和其所使用的机器息息相关。

表示字符串

C 语言的字符串是以 null (其值为0) 字符结尾的字符数组。所有字符都由标准编码表示,如 ASCII 字符码。字符码和字节顺序及字大小规则无关,因而文本数据比二进制数据具有更强的平台独立性。

表示代码

不同的机器类型使用不同的且不兼容的指令和编码方式,因此二进制代码是不兼容的。

计算机的一个基本概念是:从机器的角度来看,程序仅仅只是字节序列。机器没有关于原始源程序的任何信息。

布尔代数(Boolean algebra)简介

二进制是计算机编码、存储和操作信息的核心,通过将逻辑值 TRUE(真)和 FALSE(假) 编码二进制值,研究逻辑推理,最简单的布尔代数是在二元集合 {0, 1} 的基础上定义的。

image-20191124000516641

布尔代数的运算

将布尔运算扩展到位向量运算上,位向量即固定长度为 \({\omega}\) 、由 0 和 1 组成的串。位向量运算可以定义成参数的每个对应元素之间的运算,即对于位向量 a 和 b 分别表示位\([a_{\omega-1}, a_{\omega-2}, ..., a_0]\)\([b_{\omega-1}, b_{\omega-2}, ... b_0]\),即 a&b 定义为长度为 \({\omega}\) 的位向量,其中第 i 个元素等于 \(a_i \& b_i, 0{\leq}i<{\omega}\),类似的运算可以扩展到 |, ^, ~上。