第二章信息的表示和处理

2.1 信息存储

大多数计算机使用8 位的块，或者字节（byte）, 作为最小的可寻址的内存单位。

机器级程序将内存视为一个非常大的字节数组，称为虚拟内存 （virtual memory）。

内存的每个字节都由一个唯一的数字来标识，称为它的地址（address）。

所有可能地址的集合就称为虚拟地址空间 （virtual address space），这个虚拟地址空间只是一个展现给机器级程序的概念性映像。

2.1.1 十六进制表示法

十六进制表示、十六进制和十进制的互相转换。

2.1.2 字数据大小

每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长为位的机器而言，虚拟地址的范围为，程序最多访问个字节。

32 位字长限制虚拟地址空间为4 千兆字节（写作4GB，1G=）, 也就是说，刚刚超过字节。扩展到64 位字长使得虚拟地址空间为16EB, 大约是字节。

可移植性： 许多程序员假设一个声明为int 类型的程序对象能被用来存储一个指针。这在大多数32 位的机器上能正常工作，但是在一台64 位的机器上却会导致问题。

2.1.3 寻址和字节顺序

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

在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

某些机器选择在内存中按照从最低有效字节到最高有效字节的顺序存储对象，称为小端法 （little endian）；而另一些机器则按照从最高有效字节到最低有效字节的顺序存储，称为大端法 （big endian）。

以int类型的变量x为例，假设其位于地址0x100处，它的16进制值为0x01234567。地址范围0x100~0x103的字节顺序依赖于机器的类型：

在有些时候，字节顺序会成为问题：

是在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接收程序会发现，字里的字节成了反序的。为了避免这类问题，网络应用程序的代码编写必须遵守已建立的关千字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示。
当阅读表示整数数据的字节序列时字节顺序也很重要。这通常发生在阅读由反汇编器生成的机器级代码时。
当编写规避正常的类型系统的程序时。

打印程序对象的字节表示：

#include <stdio.h>

typedef unsigned char *byte_pointer;//用typedef将数据类型byte_pointer定义为一个指向类型为unsigned char的对象的指针

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){//&x被强制类型转换为"unsigned char *"，即把这个指针看成指向一个字节序列的对象
  show_bytes((byte_pointer) &x,sizeof(int));//使用sizeof增加可移植性
}

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);
}

2.1.4 表示字符串

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

在使用ASCII码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。

2.1.5 表示代码

对于下面的C函数

1
2
3

int sum(int x,int y){
  return x+y;
}

在不同机器上生成的字节表示的机器代码是不同的：

Linux 32    55 89 e5 8b 45 0c 03 45 08 c9 c3
Windows     55 89 e5 8b 45 0c 03 45 08 5d c3
Sum         81 c3 e0 08 90 02 00 09
Linux 64    55 48 89 e5 89 7d fc 89 75 f8 03 45 fc c9 c3

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

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

2.1.6 布尔代数简介

2.1.7 C语言中的位运算

C语言使用的符号和布尔运算中使用的符号相同：|就是或，&就是与，~就是取反，^就是异或

位级运算的一个常见用法就是实现掩码运算，这里掩码是一个位模式，表示从一个字中选出的位的集合。例如：掩码0xFF（最低的8 位为1）表示一个字的低位字节。位级运算x&0xFF生成一个由x的最低有效字节组成的值，而其他的字节就被置为0 。比如，对于x=0x89ABCDEF其表达式将得到0x000000EF

2.1.8 C语言中的逻辑运算

C语言中的逻辑运算符||、&&和!分别对应于命题逻辑中的OR、AND和NOT运算。

逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE。它们返回1或0，分别表示结果为TRUE或者FALSE。例如：

2.1.9 C语言中的移位运算

对于一个位表示为的操作数

左移运算： x<<k生成位表示为的值。即向左移动位，丢弃最高的位，并在右端补个0。

右移运算： x>>k，分为逻辑右移 和算术右移 。逻辑右移在左端补个0，得到结果是；算术右移在左端补个最高有效位的值，得到的结果是。

C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移，但是，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。

Java对于如何进行右移有明确的定义，x>>k会将x进行算术右移，而x>>>k会对x进行逻辑右移。

对于一个由位组成的数据类型，当移动位时，实际位移量是通过计算得到的。例如，假设数据类型int为

1
2
3

int      lval = 0xFEDCBA98  << 32; //0xFEDCBA98
int      aval = 0xFEDCBA98  << 36; //0xFFEDCBA9
unsigned uval = 0xFEDCBA98u >> 40; //0x00FEDCBA

2.2 整数表示

2.2.1 整数数据类型

C数据类型	32位	64位
`[signed]char`
`unsigned char`
`short`
`unsigned short`
`int`
`unsigned long`
`long`
`unsigned long`
`int32_t`
`uint_t`
`int64_t`
`uint64_t`

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

2.2.2 无符号数的编码

无符号数编码的定义： 对于向量：

位所能表示的值的范围为：最小是0，最大是

2.2.3 补码编码

补码编码的定义： 对于向量：

位所能表示的值的范围为：最小是，最大是

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

补码转换为无符号数： 对满足的有：

无符号数转换为补码： 对满足的有：

的表示可以通过把 的反码加1得到，即“ 取反加1 ”。（无论是负数转换为无符号数，还是无符号转换为负数都适用）

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

显式强制类型转换：

int tx,ty;
unsigned ux,uy;
tx = (int) ux;
uy = (unsigned) ty;

隐式类型转换：

int tx,ty;
unsigned ux,uy;
tx = ux; //转换为有符号数
uy = ty; //转换为无符号数

在32位机器上运行以下代码：

int x = -1;//1111 1111 1111 1111 1111 1111 1111 1111,0xFFFF FFFF
unsigned u = 2147483648; //2^31,1000 0000 0000 0000 0000 0000 0000 0000,0x8000 0000
printf("x = %u = %d\n",x,x); //x = 429497295 = -1
printf("u = %u = %d\n",u,u); //u = 2147483648 = -2147483648

2.2.6 拓展一个数字的位表示

无符号数的零拓展： 定义宽度为的位向量和宽度为的位向量，其中。则。

补码数的符号拓展： 定义宽度为的位向量和宽度为的位向量，其中。则。

2.2.7 截断数字

1
2
3

int x = 53191; //0000 0000 0000 0000 1100 1111 1100 0111
short sx = (short) x; //-12345
int y = sx; //-12345    12345->0011 0000 0011 1001

截断无符号数： 令等于位向量，而是将其截断为位的结果：。令,。则。

截断补码数值： 令等于位向量，而是将其截断为位的结果：。令,。则。

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

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

当参数length等于0时，运行上面的代码应该返回0.0，可实际上运行时会遇到一个内存错误。

因为参数length是无符号的，计算0-1将使用无符号运算，这等价于模数加法。结果得到。同样使用无符号数比较，而因为任何数都小于等于，所以总是为真，因此代码将试图访问数组a的非法元素。

2.3 整数运算

2.3.1 无符号加法

无符号数加法（ ）：对满足的和有：
$正常溢出$

检测无符号数加法中的溢出： 对在范围中的和，令。则对计算，当且仅当（或等价地）时，发生了溢出。

无符号数求反：对满足的任意，其位的无符号逆元由下式给出：

2.3.2 补码加法

补码加法： 对满足的整数和，有：

$正溢出正常负溢出$

检测补码加法中的溢出： 对满足的和，令。当且仅当，但时，计算发生了正溢出。当且仅当，但时，计算发生了负溢出。

2.3.3 补码的非

补码的非： 对满足的，其补码的非由下式给出

补码非的位级表示： （1）对每一位求补，再对结果加1（取反加1）

（2）设是最右边的1的位置（从右往左数的第一个1），因而的位级表示形如，这个值的非写成二进制格式就是。也就是对位左边的所有位取反。

2.3.4 无符号乘法

无符号数乘法： 对满足的和有：

2.3.5 补码乘法

补码乘法： 对满足的和有：

无符号和补码乘法的位级等价性： 给定长度为的位向量和，用补码形式的位向量表示来定义整数和：。用无符号形式的位向量表示来定义非负整数和：。则

2.3.6 乘以常数

乘以2的幂： 设为位模式表示的无符号整数。那么，对于任何，都认为给出了的位的无符号表示，这里右边增加了个

与2的幂相乘的无符号乘法： C变量x和k有无符号数值和，且，则C表达式x<<k产生数值。

与2的幂相乘的补码乘法： C变量x和k有补码值和无符号数值，且，则C表达式x<<k产生数值。

由于整数乘法比移位和加法的代价要大得多，许多C语言编译器试图以移位、加法和减法的组合来消除很多整数乘以常数的情况。例如对于表达式x*14，编译器会将其重写为(x<<3)+(x<<2)+(x<<1)或(x<<4)-(x<<1)。

2.3.7 除以2的幂

除以2的幂的无符号除法： C变量x和k有无符号数值和，且，则C表达式x>>k产生数值。

除以2的幂的补码除法，向下舍入： C变量x和k有补码值和无符号数值，且，则当执行算术移位时，C表达式x>>k产生数值。

除以2的幂的补码除法，向上舍入： C变量x和k有补码值和无符号数值，且，则当执行算术移位时，C表达式(x+(1<<k)-1)>>k产生数值。

对于使用算术右移的补码机器，C表达式(x<0 ? x+(1<<k)-1 : x) >> k将会计算数值。

写一个函数div16，对于整数参数x返回x/16的值。函数中不能使用除法、模运算、乘法、任何条件语句、任何比较运算符或任何循环。假设数据类型int是32位长，使用补码表示，右移是算术右移。

/* 利用表达式x>>31产生一个字，如果x是负数，这个字为全1，否则为全0。
   通过掩码屏蔽掉适当的位就可以得到期望的偏置值 */
int div16(int x){
  /* Compute bias to be either 0(x >=0) or 15(x < 0) */
  int bias = (x>>31) & 0xF;
  return (x+bias) >>4;
}

2.4 浮点数

浮点数对形如的有理数进行编码。

2.4.1 二进制小数

考虑一个形如

的表示法，其中每个二进制数字，或者称为位，的取值范围是0和1，如下图所示。这种表示方法表示的数定义如下：

2.4.2 IEEE浮点表示

IEEE浮点数标准用的形式来表示一个数：

符号： 决定这数是负数（）还是正数（），而对于数值0的符号位解释作为特殊情况处理
尾数： 是一个二进制小数，它的范围是，或者是
阶码： 的作用是对浮点数加权，这个权重是2的次幂（可能是负数）

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

一个单独的符号位直接编码符号
位的阶码字段exp=编码阶码
位小数字段frac=编码尾数，但是编码出来的值也依赖于阶码字段的值是否等于0

在单精度浮点格式中，s、exp和frac字段分别为位、位和位，得到一个32位的表示。在双精度浮点格式中，s、exp和frac字段分别为位、位和位，得到一个64位的表示。

给定位表示，根据exp的值，被编码的值可以分成三种不同的情况：

情况1：规格化的值

当exp的位模式既不全为0，又不全为1时，都属于这类情况。在这种情况中，阶码字段被解释为以偏置形式表示的有符号整数。也就是说，阶码的值是，其中是无符号数，其位表示为，而是一个等于（单精度是127，双精度是1023） 的偏置量。由此产生指数的取值范围，对于单精度是 ，而对于双精度是 。

小数字段frac被解释为描述小数值，其中，其二进制表示为，也就是二进制小数点在最高有效位的左边。尾数定义为。这种方式也叫隐含的以1开头 的表示，因为可以把看成一个二进制表达式为的数字。实际上是用23位来表示一个24位的数字。

情况2：非规格化的值

当阶码域全为0时，所表示的数是非规格化的形式。在这种情况下，阶码值是（单精度是 ，双精度是 ），而尾数的值是，也就是小数字段的值，没有隐含的开头的1。

情况3：特殊值

这一类数值是当阶码域全为1时出现的。当小数域全为0时，得到的值表示无穷，当时是正无穷，当时是负无穷。当小数域为非0时，表示。

2.4.3 数字示例

2.4.4 舍入

向偶数舍入也被称为向最接近的值舍入，是默认的方式，试图找到一个最接近的匹配值。它将数字向上或者向下舍入，使得结果的最低有效数字是偶数。

其他三种方式产生实际值的确界。向零舍入方式把正数向下舍入，把负数向上舍入，得到值，使得。向下舍入方式把正数和负数都向下舍入，得到值，使得。向上舍入方式把正数和负数都向上舍入，得到值，满足。

对于向偶数舍入来讲，它最大的作用是在统计时使用。向偶数舍入可以让我们在统计时，将舍入产生的误差平均，从而尽可能的抵消 。而其它三种方式在这方面都是有一定缺陷的，向上和向下舍入会造成值的偏大或偏小。而对于向零舍入来讲，如果全是正数的时候则会造成结果偏小，全是负数的时候则会造成结果偏大。

向偶数舍入规则 ：例如有效数字超出规定数位的多余数字是1001，它大于超出规定最低位的一半（即0.5），故最低位进1。如果多余数字是0111，它小于最低位的一半，则舍掉多余数字（截断尾数）即可。对于多余数字是1000（正好是最低位一半）的特殊情况，若最低位为0则舍掉多余位，最低为1则进位1，使得最低位仍为0（偶数）。

舍入前	舍入后（舍入到最接近的二分之一）

2.4.5 浮点运算

浮点加法不具有结合性。 例如，(3.14+1e10)-1e10结果为0.0，而3.14+(1e10-1e10)结果为3.14。
浮点加法满足单调性： 如果，那么对于任何及的值，除了，都有。无符号或补码加法不具有这个性质。
浮点乘法是可交换的，不具有结合性，在加法上不具有分配性，满足单调性，且只要 ，就有 。

2.4.6 C语言中的浮点数

所有的C语言版本提供了两种不同的浮点数据类型：float和double。在支持IEEE浮点格式的机器上，这些数据类型就对应于单精度和双精度浮点。
这类机器使用向偶数舍入的舍入方式。
因为C语言标准不要求机器使用IEEE浮点，所以没有标准的方法来改变舍入方式或者得到诸如、、或者之类的特殊值。
可以通过引入库函数math.h定义程序常数INFINITY和NAN。
从float或double转换成int时，值会向零舍入。进一步来说，值可能会溢出。C语言标准没有对这种情况指定固定的结果。与Intel兼容的微处理器指定位模式（字长为时的）为整数不确定值。一个从浮点数到整数的转换，如果不能为该浮点数找到一个合理的整数近似值，就会产生这样一个值。因此(int) 1e10会得到-2147483648，即从一个正值变为一个负值。

2.5 小结

计算机将信息编码为位（比特），通常组织成字节序列。有不同的编码方式用来表示整数、实数和字符串。不同的计算机模型在编码数字和多字节数据中的字节顺序时使用不同的约定。

C语言的设计可以包容多种不同字长和数字编码的实现。64位字长的机器逐渐普及，并正在取代统治市场长达30多年的32位机器。由于64位机器也可以运行为32位机器编译的程序，我们的重点就放在区分32位和64位程序，而不是机器本身。64位程序的优势是可以突破32位程序具有的4GB地址限制。

大多数机器对整数使用补码编码，而对浮点数使用IEEE标准754编码。在位级上理解这些编码，并且理解算术运算的数学特性，对于想使编写的程序能在全部数值范围上正确运算的程序员来说，是很重要的。

在相同长度的无符号和有符号整数之间进行强制类型转换时，大多数C语言实现遵循的原则是底层的位模式不变。在补码机器上，对于一个位的值，这种行为是由函数和来描述的。C语言隐式的强制类型转换会出现许多程序员无法预计的结果，常常导致程序错误。

由于编码的长度有限，与传统整数和实数运算相比，计算机运算具有非常不同的属性。当超出表示范围时，有限长度能够引起数值溢出。当浮点数非常接近于, 从而转换成零时，也会下溢。

和大多数其他程序语言一样， C语言实现的有限整数运算和真实的整数运算相比，有一些特殊的属性。例如，由于溢出，表达式x*x 能够得出负数。但是，无符号数和补码的运算都满足整数运算的许多其他属性，包括结合律、交换律和分配律。这就允许编译器做很多的优化。例如，用(x<<3)-x取代表达式7*x时，我们就利用了结合律、交换律和分配律的属性，还利用了移位和乘以2 的幂之间的关系。

我们已经看到了几种使用位级运算和算术运算组合的聪明方法。例如，使用补码运算， ~x+1等价于-x。另外一个例子，假设我们想要一个形如的位模式，由个后面紧跟着个组成。这些位模式有助于掩码运算。这种模式能够通过C表达式(1<<k)-1生成，利用的是这样一个属性，即我们想要的位模式的数值为。例如，表达式(1<<8)-1将产生位模式0xFF。

浮点表示通过将数字编码为的形式来近似地表示实数。最常见的浮点表示方式是由IEEE标准754定义的。它提供了几种不同的精度，最常见的是单精度（32位）和双精度（64位）。IEEE浮点也能够表示特殊值、和。

必须非常小心地使用浮点运算，因为浮点运算只有有限的范围和精度，而且并不遵守普遍的算术属性，比如结合性。

第二章 信息的表示和处理