CSAPP-信息的表示和处理

现代计算机系统存储和处理信息以二值信号表示，或者称为位(bit)。孤立的讲单独每个位是没有什么意义的，当将所有的位组合在一起并加上某种解释，即赋予不同的可能位模式及含义，就能够表示任何有限集合的元素。这一章主要研究三种最重要的数字编码表示 —– 无符号(unsigned)编码、补码(two’s-complement)编码、浮点数(floating-point)编码 （实数的科学计数法以2为基数的版本）。

计算机使用有限的数位来表示一个数字编码，因此当结果太大以至不能表示的时候，某些计算位就会溢出。整数的计算机计算满足熟知的计算特点（交换律和结合率）。即使计算结果溢出最后得到的错误结果也会保持一致。浮点数的运算有完全不同数学属性，溢出会产生正无穷大的特殊值，同时由于表示的精度有限，浮点运算不可结合。整数运算和浮点运算会有不同的数学属性是因为它们处理数字表示的有限性方式的不同—–整数对数的表示是精确的，但是只能表示一个相对较小的数值范围；而浮点数的表示是近似的，但是可以编码一个很大的数值范围。

GCC 经过了一段很长时间的的发展可以通过像编译器添加一些指令来制定编译器使用的编译版本。

| C版本 ｜ GCC命令行选项 ｜
| :- | :- |
| GNU 89 | 无, -std=gnu89 |
| ANSI, ISO C90 | -ansi, -std=c89 |
| ISO C99 | -std=c99 |
| ISO C11 | -std=c11 |

1. 信息的存储

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

C语言的一个指针的值（无论它是指向一个整数、一个结构或者是某个其他程序对象）都是存储块的第一个字节的虚拟地址。C编译器还把每个指针和类型联系起来。这样就可以根据指针类型，生成不同的机器代码来访问存储在指针所指位置处的值。

指针是C语言的一个重要特性。它提供了引用数据结构（包括数组）的元素机制。与变量类似的，指针也包含两个方面内容：值和类型。它的值表示某个对象的位置，而它的类型表示那个位置上所存储的变量类型。

1.1 字数据的大小

每台计算机都会有一个 字长（word size） ，表明指针数据的标称大小，因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。我们可以使用编译器来指定编译出来的程序是在32位机器或者64位机器上，因此将程序称为 “32位程序”或者“64位程序”时，主要区别在于程序是如何编译的，而不是指程序运行的机器类型。C语言支持整数和浮点数等多种数据格式。下表展示了C语言各种数据类型分配的字节大小：

｜ C声明 —– 有符号 ｜ C声明 —– 无符号 ｜ 字节数 —– 32位 ｜ 字节数 —– 64位 ｜
｜ :- | :- | :- | :- |
| char | unsigned char | 1 | 1 |
| short | unsigned short | 2 | 2 |
| int | unsigned int | 4 | 4 |
| long | unsigned long | 4 | 8 |
| int32_t | uint32_t | 4 | 4 |
| int64_t | uint64_t | 8 | 8 |
| char * | | 4 | 8 |
| float | | 4 | 4 |
| double | | 8 | 8 |

从上表可以看出有一些数据类型的确切字节数依赖程序是如何被编译的。我们给出的是32位和64位程序的典型值。ISO C99 引入了一类数据类型，其数据大小是固定的，不随编译器和机器的设置而变化。其中包含数据类型 int32_t int64_t 等等。

对于 char的数据类型，尽管大多数数编译器和机器将它视为有符号数，但是C语言标准不保证这一点。

1.2 寻址和字节顺序

对于跨越多个字节的程序对象，必须建立两个规则：这个对象的地址是什么，以及在内存中是如何排列这些字节。

可以通过命令 man ascii 来得到一张 ASCII 字符码的表

1.3 表示字符串

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

十进制数字x的ASCII码正好是0x3x，而终止字符\0的16进制表示为 0x00。

ASCII编码：C语言中字符的编码方式。Unicode编码是一种常用的广泛的编码标准，包含了近 100 000 个字符常用的字符，常用的有UTF-8 。

1.4 表示代码

不同的机器类型使用不同的且不兼容的指令和编码方式。即使完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制编码是不兼容的。从机器的角度来看，程序仅仅只是字符序列。机器没有关于原始程序的任何信息，除了可能用来帮助调试的辅助表以外。

1.5 布尔代数简介

布尔代数运算：

  • NOT : ~0 = 1 ~1 = 0
  • AND : 0&0 = 0 0&1 = 0 1&0 = 0 1&1 = 1
  • OR : 0|0 = 0 0|1 = 1 1|0 = 1 1|1 = 1
  • EXCLUSIVE-OR : 0^0 = 0 1^0 = 1 0^1 = 1 1^1 = 0

布尔环 a^a = 0

1.6 C语言中的位运算

C语言支持按位进行布尔运算，其中运算符分别是 : ~(NOT) &(AND) |(OR) ^(EXCLUSIVE-OR)

 可以通过下面算法不使用第三个数交换两个数的值。(布尔环)

1
2
3
4
5
6
void inplace_swap(int *x, int *y)
{
  *y = *x^*y;
  *x = *x^*y;
  *y = *y^*x;
}

1.7 C语言的逻辑运算

C语言还提供了逻辑运算符 ||(OR) , &&(AND) , !(NOT)

逻辑运算符号 || 和 && 的运算中如果第一个参数就能确定结果，表达式将不会求第二个参数的值。如 a&&5/a 将不会应为a的值为0而失败

1.8 C语言的移位运算

C语言还提供了一组移位运算，向左（<<）或者向右（>>）移动的模式。一般来说有两种形式的右移：

  • 逻辑右移：移动后在左端补上k个0 。 01100011 >> 4 = 00000110 10011100 >> 4 = 00001001
  • 算数右移：移动后在左端补上k个1 。 01100011 >> 4 = 00000110 10011100 >> 4 = 11111001

C语言的标准并没有定义 >> 对于有符号数使用那种形式的右移。但一般来说对于有符号数采用算数右移，对于无符号数采用逻辑右移。

在C语言中当移动一个w位的值k个长度的时候，实际位移量是k%w。例如当对int的数据类型移动33位时实际移动量为1 。

2. 整数的表示

2.1 整型数据类型

C语言支持多种整数数据类型 —- 表示有限范围的整数。

指示符long的取值范围与机器有关。大多数的64位机器采用8个字节表示，比32位机器上使用4个字节的取值范围要大很多。

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

C数据类型 最小值 最大值
char -128 127
unsigned char 0 255
short -32768 32767
unsigned short 0 65535
int -2 147 483 648 2 147 483 647
unsigned int 0 4294967295
long -2 147 483 648 2 147 483 647
unsigned long 0 4294967295
int32_t -2 147 483 648 2 147 483 647
uint32_t 0 4294967295
int64_t -9 223 372 036 854 775 808 9 223 372 036 854 775 807
uint64_t 0 18 446 744 073 709 551 615

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

C数据类型 最小值 最大值
char -128 127
unsigned char 0 255
short -32768 32767
unsigned short 0 65535
int -2 147 483 648 2 147 483 647
unsigned int 0 4294967295
long -9 223 372 036 854 775 808 9 223 372 036 854 775 807
unsigned long 0 18 446 744 073 709 551 615
int32_t -2 147 483 648 2 147 483 647
uint32_t 0 4294967295
int64_t -9 223 372 036 854 775 808 9 223 372 036 854 775 807
uint64_t 0 18 446 744 073 709 551 615

上面两张表可以看出一个十分值得注意的特点：有符号数的取值范围不是对称的—-负数的范围比正数的范围大1

C语言标准定义了每种数据类型必须能够表示的最小取值范围。如下表所示。这里我们可以发现在C语言标准中除了固定大小的数据类型例外，其他数据类型的正数和负数的取值范围是对称的。除此之外，数据类型int还可以通过2个字节来表示，这主要应用在16位机器上面。

C数据类型 最小值 最大值
char -127 127
unsigned char 0 255
short -32767 32767
unsigned short 0 65535
int -2 147 483 647 2 147 483 647
unsigned int 0 4294967295
long -2 147 483 647 2 147 483 647
unsigned long 0 4294967295
int32_t -2 147 483 648 2 147 483 647
uint32_t 0 4294967295
int64_t -9 223 372 036 854 775 808 9 223 372 036 854 775 807
uint64_t 0 18 446 744 073 709 551 615

C和C++ 都支持有符号数（默认）和无符号数。Java只支持有符号数

2.2 无符号数的编码

无符号数的编码具有唯一性。

2.3 补码编码

对于许多实际应用的情况，我们还希望表示数据的负值。最常见的有符号数的计算机表示方法就是 补码 。在这个定义中将字的最高有效位解释位负权（negative weight）。

根据原理可以知道补码的表示范围是不对称的 : |TMin| = |TMax| + 1 ， 也就是说TMin 没有与之对应的正数。

从补码的原理可以得出，0在这种编码模式中表示的是正数。这也导致了能表示的整数比负数少一个。

对于有符号数还有一些其他的表示方法：（这两种编码方式对于0都存在不唯一的编码）

  • 反码： 最高有效的权要小于补码，其他一致。
  • 原码： 最高有效为符号位，用来确定剩下的位应该取正权还是负权。

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

C语言允许在不同的数据类型之间做强制类型转换，例如，假设变量x声明为int， 变量u声明为unsigned int，表达式(unsigned int) x会将x的值转换成为一个无符号的数值； 而表达式(int) u可以将u的值转换成为一个有符号的整数。这里将负数转换成无符号的数字可能会得到0，如果要转换的无符号数太大超出了补码能表示的范围可能会得到TMax。 对于大多数C语言的实现来说，对这个问题的回答都是从位级角度来看的，而不是数的角度。

强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。

例如下面代码，在一台采用补码表示负数的机器上面会产生如下的输出 x = -12345, y = 53191。这里-12345和数字53191的16位无符号表示是完全一样的，将short强制转换为unsigned short只是改变了数据的解释方式，但并没有改变数据的位表示。

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdint.h>

int main(void)
{
    int16_t x = -12345;
    uint16_t y = (uint16_t)x;

    printf("x = %d, y = %u",x,y);

}

2.5 C语言中有符号数和无符号数

C语言支持所有的整型数据类型的有符号和无符号运算，尽管C语言标准没有指定有符号的数需要采用那种表示方式，但是几乎所有的机器对于有符号数都是采用补码。通常，大多数数字都默认采用有符号数字，如果需要创建一个无符号的常量，必须在后面显示的加上后缀U或者u。

C语言允许无符号的数和有符号的数之间的转换。虽然C标准没有精确的定义如何进行这种转换，但是大多数系统遵循的原则就是保持底层的位表示不变。其中发生转换主要有下面几种情况：

  • 显示强制数据转换：
  • 隐式强制数据转化：当一种类型的表达式被赋值给另一种表达式的时候发生。

printf没有使用任何类型信息，所以它可以使用%u来输出类型int的数值，也可以使用%d来输出unsigned类型的数值。　

由于C语言同时包含有符号和无符号的数的表示处理方法，这就导致会出现一些奇特的行为。当执行一个运算的时候如果它的一个运算是有符号的而另一个是无符号的，那么C语言就会隐含的将有符号参数强制转换为无符号数。如在C语言中运算式-1 < 0U的期望结果就是false。

2.6 扩展一个数的位表示

将一个无符号的数据转换成为一个更大的数据类型的时候，我们只需要简单的在开头添加0。这种运算方法被称为零扩展（zero extension）。要将一个二进制的补码转换成为一个更大的数据类型规则是执行一个符号扩展（sign extension）， 在表示中添加最高有效位/符号位的值。

2.7 截断数字

当将一个w位的数字截断成为一个k位数字的时候，我们会丢弃高w-k位数字，截断一个数字可能会改变它的值—-可以理解截断为溢出的一种形式。

2.8 关于有符号数和无符号数的建议

避免隐式强制类型转换的方法就是绝不使用无符号数字。实际上除了C语言以外很少有语言支持无符号整数。因为使用它们的麻烦要比益处多很多。在这里建议无符号数仅仅用作表示位的集合而不是任何有意义的数字。

3. 整数的运算

在C语言中整数运算中可能会出现两个正数做加法最后的得出一个负数，同时也可以出现x<y和表达式x-y<0产生不同的结果。这些属性是计算机运算有限性造成的。因此理解计算机运算的细微之处能够帮助程序员编写更可靠的代码。

3.1 无符号加法

当两个无符号的数字相加时可能会发生溢出的情况，这样会截断最高位，例如下面的伪代码：

1
2
3
uint4_t a = 9;
uint4_t b = 12;
a+b = 21-2^4 = 5;

3.2 补码加法

大多是计算机使用同样的机器指令来执行有符号数和无符号数的加法，所以从理解上面我们可以先将有符号数看作二进制的表示形式然后在按无符号数的加法规则做加法。

3.3 补码的非

对于执行二进制的非的运算技术是对每个位取反或者说取补然后将结果加一。

3.4 无符号乘法

两个w位的数据相乘得到的结果可能会出现2w位的情况，这时候在C语言中会取低w位来表示乘法的结果。

3.5 补码的乘法

对于C语言来说无符号的二进制乘法和二进制补码的乘法，运算中表示的位级都是一样的；同时对于两个已截断乘积的结果的位表示也是相同的（完整的位级表示可能会不同）。

3.6 乘以2的幂

因为在大多数的机器上，整数的乘法运算相当地慢，需要12或者更多的时钟周期，因此编译器使用的一项重要的优化就是尝试使用移位或者加法运算的组合来代替常数因子的乘法。对于C语言来说一个数乘以2的幂编译器会尝试将这个运算优化成为一个数的左移运算，如求a^(2^k)可以等价位运算 a < k， 当然这样的运算也会出现溢出截断的问题。

3.7 除以2的幂

对于除法运算大多数机器执行的运算效率更加的缓慢，大约需要30个或者更多的时钟周期来完成这一操作。所以编译器也会尝试使用移位操作来优化数的除法运算。简单说就是下面的式子 (x<0?(x + (1<<k) -1):x) >> k

1
2
3
4
5
6
int arith(int x, int y)
{
  int result = 0;
  result = x*16 + y/4;
  return result;
}

例如上面的这段代码就有可能被编译器优化成下面这样：

1
2
3
4
5
6
7
8
9
int arith(int x, int y)
{
  int t = x;
  x <<= 4;
  x -= t;
  if(y<0) y+= 3;
  y >>= 2;
  return x+y;
}

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

假设我们在对有符号值使用二进制补码运算的32位机器上运行下面代码，其中该机器对有符号的值使用的是算数右移，而对无符号的值使用的是逻辑右移，变量的声明和初始化如下：

1
2
3
4
5
int x = foo();
int y = bar();

unsigned int ux = x;
unsigned int uy = y;

对下面每个C表达式，是否存在使他为假的x和y的值：

  1. (x >= 0) || (2*x < 0) x=0xBFFFFFFF或x = 80000000
  2. (x&7) != 7 || (x << 30 < 0) 真
  3. (x*x) >= 0 x = 0xB505
  4. x < 0 || -x <= 0 真
  5. x > 0 || -x >=0 假， 当 x = 0x80000000 时 -x也为负数。（负数的最大值要比正数大）
  6. x*y == ux*uy 真，无符号数的乘法和补码的乘法享有相同的运算规则
  7. ~x*y + ux*uy == -y 真，~x等价与-x-1然后将等式展开可得结果

4. 浮点数

浮点数对表示非常大的数据，非常接近0的数据，以及更加普遍的作为实数近似值的运算是十分有用的。这一节将讨论IEEE中浮点数是如何表示的。同时这里还将讨论舍入的问题，当一个数无法正确表示的时候是依照怎么样的规则进行向上或者向下的调整，最后将讨论浮点数的加法乘法等运算研究浮点数的数学属性，以及在C语言中的表示。

4.1 二进制小数

对于我们常用的十进制表示法来说表示的数字形式如下XXXX.xxxxx。其中小数点左边的数字的权为10的正幂，右边的权为10的负幂。对于二进制数如果采用上面的表示方法，同样的小数点左边的数字的权为2的正幂，右边为权为2的负幂。考虑到我们在计算机中对数值的编码长度有限性，许多数值无法将它准确的表示成为一个二进制的数值（如3/7 等）。

4.2 IEEE浮点表示

前面的那种方法无法有效的表示很大或者很小的数字。对于浮点数的设计来说我们更加希望通过给定x和y的方式来表示形如x*2^y这样的数。这里IEEE采用V = (-1)^s*M*2^E的形式来表示一个数：

  • 符号：符号位s决定了要表示的数是正数还是负数，对于数字0做特殊处理。
  • 有效数：M是一个二进制的小数
  • 指数：E是2的幂，它的作用是给有效数加权。

一个浮点数被划分为三个域，以编码这些值：

  • 一个单独的符号位s直接编码符号s。
  • k位的指数域编码指数E。
  • n位的小数域来编码有效数M，但是被编码的值也依赖于指数域的值是否等于零。

在C语言中，单精度浮点（float）格式中s，k，e的域分别位1位，8位和23位组合成一个32位的表示；而双精度浮点格式（double）中s，k，e的域分别位1位，11位和52位组合成一个64位的表示。这里对于给定的位表示，被编码的值可以分成三种不同的情况。

  • 规格化值 ：这种是最普遍的情况。在这种情况下exp的位模式即不全为0，也不全为1。在这种情况下，指数位域解释表示为偏置形式的有符号，指数位的值E = e-Bias(bias 为偏置量)。小数域的定义M=1+f。
  • 非规格化值 ：指数域全为0的情况。这种情况下数的浮点表示主要是用于表示接近0的小数。
  • 特殊数值 ：指数域全为1的情况，当小数域全为0的时候，表示无穷，用于表示一些溢出的结果；当小数域为非0的情况，表示的值为NaN即运算结果不是实数。

bias 的值为 2^(k-1) - 1

这里用一个假定的8位浮点格式的数来示例，其中有有指数位为4位，小数位为3位。这里可以计算出偏置量(Bias)为7，下表描述了这种情况下对数的表示

描述 位表示 e E f M V
0 0 0000 000 0 -6 0 0 0
最小的非规格化数 0 0000 001 0 -6 1/8 1/8 1/512
0 0000 010 0 -6 2/8 2/8 2/512
…
最大的非规格化数 0 0000 111 0 -6 7/8 7/8 7/512
最小的规格化数 0 0001 000 1 -6 0 1 8/512
0 0001 001 1 -6 1 9/8 9/512
…
1 0 0111 000 7 0 0 8/8 1
…
0 0111 001 7 0 1 9/8 9/8
…
最大的规格化数 0 1110 111 14 7 7/8 15/8 240
正无穷大 0 1111 000

这里再用一个例子说明浮点数的转换，有一个int类型的数字3490593，其16进制表示为0x354321，将其转换为float型数据3490593.0其16进制表示形式为0x4a550c84，这个强制类型转换的过程可以描述如下：

  1. 将数据0x354321转为为二进制的形式 ：0000 0000 0011 0101 0100 0011 0010 0001
  2. 因为float类型的位表示位1个符号位，8个指数位23个小数位。这里计算小数位 101 0101 0000 1100 1000 0100
  3. 计算指数域的值为e - Bias = 21，这里Bias = 2^(8-1) - 1 = 127 。所以可以得出指数域的值为0x95 = 1001 0100
  4. 最后符号位为0 组合起来就是(0)(100 1010 0)(101 0101 0000 1100 1000 0100)即0x4a550c84

4.3 舍入

因为表示方式限制了浮点数的范围和表示精度，所以浮点运算只能近似的表示实数运算。因此，对于值x，我们一般有一个系统的方法，期望能够找到“最接近的”匹配值。IEEE浮点格式定义了四种不同的舍入方式。默认的方法是找到最接近的匹配，而其他三种可以用于计算上界和下界：

  • 向偶数舍入 ： 也被称为最接近的值舍入，这里叫做向偶舍入主要是因为这种舍入方式相较于其他舍入方式对于1.5和2.5这样的两个数舍入的结果都是2.0 。向偶舍入采用的方式是将一个数向上或者向下舍入，找到一个最接近的匹配值。这种方式也是IEEE浮点运算默认的舍入方式，而其他三种浮点运算方式用于计算数据的上界和下界。
  • 向零舍入 ： 将正数向下舍入，将负数向上舍入。
  • 向下舍入 ：
  • 向上舍入 ：

向偶舍入，相较于向下舍入或者向上舍入避免了一些统计上的偏差。

4.4 浮点运算

IEEE标准为诸如加法和乘法这样的算数运算的结果定义了简单的规则。将浮点值x和y看成实数，并对实际运算结果进行舍入。这里因为存在舍入的原因，所以浮点运算不具有交换律。另一方面，浮点运算满足下面的单调属性，即当a >= b时一定满足a+x >= b+x，这个是无符号或者有符号数的加法运算所不满足的。

4.5 C语言中的浮点

C语言中提供了两种不同的浮点数据类型：float和double ，在支持IEEE浮点格式的机器上，这些数据类型分别对应单精度和双精度浮点。

C语言没有要求机器使用IEEE浮点。所以没有标准来改变舍入的方式或者描述特殊的数值。

当在int,float,double格式之间进行强制类型转换的时候，程序按照如下原则来进行数值和位模式的转换：

  • 从int转换成float，数字不会溢出，但是有可能会舍入。
  • 从int或者float转换成double能够保留精确的数字。
  • 从double转化为float因为float表示的范围要小一些所以可能会出现转换结果为无穷大的可能。
  • 从float或double转换成int值将会向0截断。

对于采用IA32指令集的机器，由于机器在运算过程中采用一个80位的寄存器来存储浮点数，所以会出现计算和存储下的值不一致的情况，导致一些奇怪的结果。