第二章：信息的表示和处理

本章介绍了计算机上如何表示数字和其他形式数据的基本属性，以及计算机对这些数据执行操作的属性。

2.1 信息存储

2.1.1 十六进制表示法

2.1.2 字数据大小

基本 c 数据类型的典型大小 (以字节为单位)。
分配的字节数受程序是如何编译的影响而变化。
本图给出的是 32 位和 64 位程序的典型值

2.1.3 寻址和字节顺序

关于大端法和小端法

最低有效字节在最前面的方式，称为小端法 (little endian)
最高有效字节在最前面的方式，称为大端法 (big endian)

假设变量 x 的类型为 int, 位于地址 0x100 处，它的十六进制值为 0x012345670 地址范围 0x100 ~ 0x103 的字节顺序依赖于机器的类型:

我们可以执行下面这段程序。打印程序对象的字节表示

 # include <stdio.h>
int main(){
    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]);
            //C格式化指令 %.2x 表明整数必须用至少两个数字的十六进制格式输出。
        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);
    }
 
    test_show_bytes(12345);
    return 0;
}

参数 12345 的十六进制表示为 0x00003039
在我的 Linux 64 上，最低有效字节值 0x39 最先输出，这说明它是小端法机器

练习题 2.58

写一个函数返回所使用机器的大小端类型，示例代码如下：

 // 示例代码
#include <stdio.h>
int is_little_endian(void){
    union w
    {
        int a;
        char b;
    }c;
    c.a = 1;
    return (c.b == 1); // 小端返回TRUE,大端返回FALSE
 }
int main(int argc, char *argv[]) {
    if(is_little_endian())
        printf("Little Endian\n");
    return 0;
}

在 Ubuntu 22.04.5 LTS x86_84 环境下，输出：Little Endian

解释：

联合体（Union）：在 C 语言中，联合体允许多个变量共享同一内存位置。在这段代码中，union w 里面有一个 int a 和一个 char b，它们共用相同的内存空间。关键是对 a 或 b 的修改会影响另一个。
给 a 赋值为 1：当你把 1 赋值给 a 时，内存中的表示方式会因字节序的不同而有所不同：
- 小端字节序：最低有效字节（LSB）存储在最前面，所以 1 的内存表示就是 0x01 存储在 b 所代表的位置。
- 大端字节序：最高有效字节（MSB）存储在最前面，所以 1 的内存表示是 0x00 存储在 b 所代表的位置。
检查 b 的值：然后程序检查 b 的值。如果是小端字节序，b 将是 1；如果是大端字节序，b 将是 0。因此，is_little_endian() 函数返回 1 表示小端字节序，返回 0 表示大端字节序。

2.1.4 表示字符串

C 语言中字符串被编码为一个以 null(其值为 0) 字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是 ASCII 字符码。

2.1.5 表示代码

计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列

2.1.6 布尔代数

2.1.7 C 语言中的位级运算

C 语言支持按位布尔运算

| 或
& 与
~ 取反
^ 异或

2.1.8 C 语言中的逻辑运算

逻辑运算符：

|| 或
&& 与
！ 非

逻辑运算很容易和位级运算相混淆，但是它们的功能是完全不同的。
逻辑运算认为所有非零的参数都表示 TRUE, 而参数 0 表示 FALSE，它们返回 1 或者 0, 分别表示结果为 TRUE 或者为 FALSE。
以下是一些表达式求值的示例。

表达式	结果
! 0x41	0x00
! 0x00	0x01
!! 0x41	0x01
0x66 && 0x55	0x01
0x66 \|\| 0x55	0x01

逻辑运算符 && 和 || 与它们对应的位级运算 & 和 | 之间第二个重要的区别是
如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。
因此，表达式 a&&5/a 将不会造成被零除，而表达式 p&&*p++ 也不会导致间接引用空指针。

2.1.9 C 语言中的位移运算

左移
逻辑右移：在左端补 k 个 0
算术右移：在左端补 k 个最高有效位的值

操作	值
参数 X	[01100011] [10010101]
x << 4	[0011000] [01010000]
x >> 4 (逻辑右移)	[00000110] [00001001]
x >> 4 (算数右移)	[00000110] [11111001]

C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移 —— 算术右移或者逻辑右移都可以。
不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。
然而，实际上，几乎所有的编译器 / 机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。
另一方面，对于无符号数，右移必须是逻辑的。

2.2 整数表示

整数的数据与算术操作术语。下标砂表示数据表示中的位数

2.2.1 整数数据类型

32 位程序上 C 语言整型数据类型的典型取值范围

64 位程序上 C 语言整型数据类型的典型取值范围

C 语言的整型数据类型的保证的取值范围。
C 语言标准要求这些数据类型必须至少具有这样的取值范围

2.2.2 无符号数的编码

2.2.3 补码编码

C 语言标准并没有要求要用补码的形式来表示有符号整数，但是几乎所有的机器都是这么做的。

2.2.4 有符号数和无符号数之间的转换

C 语言允许在各种不同的数字数据类型之间做强制类型转换。

对于大多数 C 语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是: 数值可能会改变，但是位模式不变。

这个特性就会导致部分数在转换前后值不相同
例如：

 short int v =-12345;
unsigned short uv = (unsigned short) v;
printf("v = %d , uv = %u\n", v, uv);

在一台采用补码的机器上，上述代码会产生如下输出:
v = -12345, uv = 53191

我们看到，强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。
-12345 的 16 位补码表示与 53191 的 16 位无符号表示是完全一样的:1100 1111 1100 0111

 unsigned u = 4294967295u; /* UMax */
int tu = (int) u;
printf("u = %u, tu = %d\n", u, tu);

在一台采用补码的机器上，上述代码会产生如下输出:
u = 4294967295, tu = -1

我们可以看到，对于 32 位字长来说，无符号形式的 4294967295 (UMax32) 和补码形式的 - 1 的位模式是完全一样的。
将 unsigned 强制类型转换成 int, 底层的位表示保持不变

原书描述了转化公式，详情参考原文 2.2.4

2.2.5 C 语言中的有符号数和无符号数

通常，大多数数字都默认为是有符号的。例如，当声明一个像 12345 或者 0x1A2B 这样的常量时，这个值就被认为是有符号的。
要创建一个无符号常量，必须加上后缀字符 u 或者 U, 例如，12345U 或者 0x1A2Bu。

由于 C 语言对同时包含有符号和无符号数表达式的这种处理方式，出现了一些奇特的行为。
当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么 C 语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。
就像我们将要看到的，这种方法对于标准的算术运算来说并无多大差异，但是对于像 < 和 > 这样的关系运算符来说，它会导致非直观的结果。

非直观的情况标注了 *

考虑比较式 -1<0U
因为第二个运算数是无符号的，第一个运算数就会被隐式地转换为无符号数，因此表达式就等价于 4294967295U < 0U, 因为 T2U(-1)=UMax

2.2.6 扩展一个数字的位表示

简单来说，无符号数的扩展是添加 0，补码数值的扩展是扩展最高有效位（符号位）

详情参见原文 2.2.6

2.2.7 截断数字

减少一个数字的位数的操作就是截断数字
依然遵循着数值可能会改变，但是位模式不变的规则。

我们用这段程序为例，解释一下原理：

 int x = 53191;
short sx = (short) x; /*-12345*/
int y = sx; /*-12345*/

当我们把 x 强制类型转换为 short 时，我们就将 32 位的 int 截断为了 16 位的 short int。
就像前面所看到的，这个 16 位的位模式就是 - 12345 的补码表示。当我们把它强制类型转换回 int 时，符号扩展把高 16 位设置为 1, 从而生成 - 12345 的 32 位补码表示。

原文中采用了取模运算的方式定义了截断数字的运算函数，这个过程非常的有趣且巧妙。

2.2.8 关于有符号数与无符号数的建议

书中的两道例题很好的说明了了某些由于隐式强制类型转换和无符号数据类型造成的细微的错误

练习题 2.25

考虑下列代码，这段代码试图计算数组 a 中所有元素的和，其中元素的数量由参数 length 给出。

 /*WARNING:This is buggy code*/
float sum_elements(float a[], unsigned length){
    int i;
    float result = 0;
 
    for(i = 0; i <= length-1; i++){
        result += a[i];
    }
    return result;
}

当参数 length 等于 0 时，运行这段代码应该返回 0.00。
但实际上，运行时会遇到一个内存错误。
请解释为什么会发生这样的情况，并且说明如何修改代码。

答：

设计这个问题是要说明从有符号数到无符号数的隐式强制类型转换很容易引起错误。
将参数 length 作为一个无符号数来传递看上去是件相当自然的事情，因为没有人会想到使用一个长度为负数的值。停止条件 i<=length-1 看上去也很自然。但是把这两点组合到一起，将产生意想不到的结果！
因为参数 length 是无符号的，计算 0-1 将使用无符号运算，这等价于模数加法。结果得到 UMax。 <= 比较同样使用无符号数比较，而因为任何数都是小于或者等于 UMax 的，所以这个比较总是为真！
因此，代码将试图访间数组 a 的非法元素。

有两种方法可以改正这段代码，其一是将 length 声明为 int 类型，其二是将 for 循环的测试条件改为 i<length。

练习题 2.26

现在给你一个任务，写一个函数用来判定一个字符串是否比另一个更长。前提是你要用字符串库函数 strlen, 它的声明如下:

  /* Prototype for library function str|en */
 size_t strlen(const char *s) ;

最开始你写的函数是这样的:

 /* Determine whether string s is Ionger than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, Char *t) {
    return strlen(s) - strlen(t) > 0;
}

当你在一些示例数据上测试这个函数时，一切似乎都是正确的。进一步研究发现，在头文件 stdio.h 中数据类型 size_t 是定义成 unsignedint 的。
A. 在什么情况下，这个函数会产生不正确的结果？
B. 解释为什么会出现这样不正确的结果。
C. 说明如何修改这段代码好让它能可靠地工作。

答：

这个例子说明了无符号运算的一个细微的特性，同时也是我们执行无符号运算时不会意识到的属性。这会导致一些非常棘手的错误。
A：当 s 比 t 短的时候，该函数会不正确地返回 1。
B：由于 strlen 被定义为产生一个无符号的结果，差和比较都采用无符号运算来计算。当 s 比 t 短的时候，strlen(s)-strlen(t) 的差会为负，但是变成了一个很大的无符号数，且大于 0。
C：将测试语句改成:return strlen(s) > strlen(t)。

2.3 整数运算

2.3.1 无符号加法

无符号数加法、溢出检查、无符号数求反的具体算法见原文

2.3.2 补码加法

补码加法、溢出检查具体算法见原文

2.3.3 补码的非

补码非的位级表示：

方法一：对每一位求补，再对结果加 1。
方法二：建立在将位向量分为两部分的基础之上，假设 k 是最右边的 1 的位置，我们对位 k 左边的所有位取反即可。

这里我们要知道一点就是：最小补码（TMin）是自己加法的逆元
也就是说：TMin = -TMin

2.3.4 无符号乘法

2.3.5 补码乘法

简单来说，乘法与加法类似，按照数学原理进行乘法，最后进行取模运算处理溢出。

2.3.6 乘以常数

乘以 2 的幂

进行向左移位运算

2.3.7 除以常数

除以 2 的幂也可以用移位运算来实现，只不过我们用的是右移，而不是左移。
无符号和补码数分别使用逻辑移位和算术移位来达到目的。

2.3.8 关于整数运算的最后思考

正如我们看到的，计算机执行的 "整数" 运算实际上是一种模运算形式。
表示数字的有限字长限制了可能的值的取值范围，结果运算可能溢出。
我们还看到，补码表示提供了一种既能表示负数也能表示正数的灵活方法，同时使用了与执行无符号算术相同的位级实现，这些运算包括像加法、减法、乘法，甚至除法，无论运算数是以无符号形式还是以补码形式表示的，都有完全一样或者非常类似的位级行为。
我们看到了 C 语言中的某些规定可能会产生令人意想不到的结果，而这些结果可能是难以察觉或理解的缺陷的源头。
我们特别看到了 unsigned 数据类型，虽然它概念上很简单，但可能导致即使是资深程序员都意想不到的行为。我们还看到这种数据类型会以出乎意料的方式出现，比如，当书写整数常数和当调用库函数时。

2.4 浮点数

这一小节我们必须要掌握 IEEE 浮点标准

2.4.1 二进制小数

2.4.2 IEEE 浮点表示

2.4.3 数字示例

2.4.4 舍入

2.4.5 浮点运算

注意：浮点加法不满足结合律

2.4.6 C 语言中的浮点数

所有的 C 语言版本提供了两种不同的浮点数据类型: float 和 double.
在支持 IEEE 浮点格式的机器上。这些数据类型就对应于单精度和双精度浮点。另外，这类机器使用向偶数舍入的方式。
不幸的是，因为 C 语言标准不要求机器使用 IEEE 浮点，所以没有标准的方法来改变舍入方式或者得到诸如 -0、 +∞、-∞或者 NaN 之类的特殊值。大多数系统提供 include('.h') 文件和读取这些特征的过程库，但是细节随系统不同而不同。

2.5 小结

计算机将信息编码为位 (比特), 通常组织成字节序列。有不同的编码方式用来表示整数、实数和字符串。不同的计算机模型在编码数字和多字节数据中的字节顺序时使用不同的约定
C 语言的设计可以包容多种不同字长和数字编码的实现。64 位字长的机器逐渐普及，并正在取代统治市场长达 30 多年的 32 位机器。由于 64 位机器也可以运行为 32 位机器编译的程序，我们的重点就放在区分 32 位和 64 位程序，而不是机器本身。64 位程序的优势是可以突破 32 位程序具有的 4GB 地址限制。
大多数机器对整数使用补码编码，而对浮点数使用 IEEE 标准 754 编码。在位级上理解这些编码，并且理解算术运算的数学特性，对于想使编写的程序能在全部数值范围上正确运算的程序员来说，是很重要的。
在相同长度的无符号和有符号整数之间进行强制类型转换时，大多数 C 语言实现遵循的原则是底层的位模式不变。在补码机器上，对于一个 w 位的值，这种行为是由函数 T2U 和 U2T, 来描述的。C 语
言隐式的强制类型转换会出现许多程序员无法预计的结果，常常导致程序错误。
由于编码的长度有限，与传统整数和实数运算相比，计算机运算具有非常不同的属性。当超出表示范围时，有限长度能够引起数值溢出。当浮点数非常接近于 0.0, 从而转换成零时，也会下溢。
和大多数其他程序语言一样，C 语言实现的有限整数运算和真实的整数运算相比，有一些特殊的属性。例如，由于溢出，表达式 x*x 能够得出负数。但是，无符号数和补码的运算都满足整数运算的许多其他属性，包括结合律、交换律和分配律。这就允许编译器做很多的优化。例如，用 (x<<3)-x 取代表达
式 7*x 时，我们就利用了结合律、交换律和分配律的属性，还利用了移位和乘以 2 的幂之间的关系。
我们已经看到了几种使用位级运算和算术运算组合的聪明方法。例如，使用补码运算，~x+1 等价于 -x. 另外一个例子，假设我们想要一个形如 [0, ⋯, 0, 1, ⋯, 1] 的位模式，由 w-k 个 0 后面紧跟着 k 个 1 组成。这些位模式有助于掩码运算。这种模式能够通过 C 表达式 (1<<k)-1 生成，利用的是这样一个属性，即我们想要的位模式的数值为 2^k-1。例如，表达式 (1<<8)-1 将产生位模式 0xFF。
浮点表示通过将数字编码为 × * 2^y 的形式来近似地表示实数。最常见的浮点表示方式是由 IEEE 标准 754 定义的。它提供了几种不同的精度，最常见的是单精度 (32 位) 和双精度 (64 位)。IEEE 浮点也能够表示特殊值 +∞、-∞和 NaN
必须非常小心地使用浮点运算，因为浮点运算只有有限的范围和精度，而且并不遵守普遍的算术属性，比如结合性。

以上小结内容节选自原文 2.5

参考资料

Computer Systems: A Programmer's Perspective, 3/E (CS:APP3e) -- Randal E. Bryant and David R. O'Hallaron, Carnegie Mellon University

深入理解计算机系统 - CSAPP 重点导读

2015 CMU CSAPP 深入理解计算机系统课程视频

累计阅读量： 48

2025 年 1 月
一	二	三	四	五	六	日
		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