第二章 信息的表示和处理

[清晰svg格式从此提取](http://pan.baidu.com/s/1hscLNa0)

---

本章我们来研究三种重要的数字表示

• 无符号是基于传统二进制表示法，表示大于或等于0的数字
• 补码是表示有符号整数的最常见方式，有符号整数可以是正或者为负
• 浮点数是表示实数的科学计数法的以2为基数的版本

计算机的表示法是用有限的数量的位表示的数字编码，所以，结果太大的时候，某些运算就会溢出。浮点运算溢出会产生特殊的值+∞，但是一组正数的乘积总是正的，这点和整数不同。但是由于表示的精度有限，浮点运算是不可结合的。

整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确的，而浮点数可以编码一个较大的数值范围，但是这种表示只是近似的。

2.1信息存储

大多数计算机使用8位的块，或者说字节，作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字标识，称为它的地址，所有可能地址的集合称为虚拟地址空间。

十六进制表示法

一个字节由8位组成，在二进制表示法中，它的值域是00000000_{11111111，用十六进制书写，它的值域是0x00}0xFF。

以0x或者0X开头的数字常量被认为是16进制，字符“A”~“F”既可以是大写也可以是小写。

字数据大小

字长决定的最重要的系统参数就是虚拟地址空间的最大大小。对于一个字长为ω位的机器而言，虚拟地址的范围就是0 ~ 2^ω - 1，程序最多访问2^ω个字节。

大部分数据类型都编码为有符号数值，除非有前缀关键字unsigned或者对确定大小的数据类型使用了特定的无符号声明。（数据类型char是个例外）

寻址和字节顺序

多字节对象被存储为连续的字节序列，对象的地址为所用字节最小的地址。

最低有效字节在最前面的方式，称为小端法。
最高有效字节在最前面的方式，称为大端法。

许多比较新的微处理器是双端法，然而实际上，一旦选择了特定的操作系统，字节顺序也就被固定下来。Android和iOS都是运行于小端模式。

表示代码

指令编码是不同的，不同的机器类型使用不同的且不兼容的指令和编码方式。
从机器的角度来看，程序仅仅只是字节序列。

有关布尔代数

布尔运算~对应逻辑运算NOT，对应集合的补；
布尔运算&对应逻辑运算AND，对应集合的并；
布尔运算|对应逻辑运算OR，对应集合的交；
布尔运算^对应逻辑运算亦或。

布尔运算的分配率：a & (b | c) = (a & b)|(a & c),a | (b & c) = (a | b)&(a | c)
另外，对于a ^ a = 0，因此还有(a ^ b) ^ a = b

这里有一些有意思的关于位运算的东西，简单整理在一起，以后单开一个笔记，把一些位运算的算法题归类一下。

a ^= b;
b ^= a;
a ^= b;

这样可以交换a和b的值，但是这个种交换方式没有性能上的优势，它仅仅是一个智力游戏（至少书上是这么说的……）

有关逻辑运算

C语言还提供了一组逻辑运算符||、&&、和！，分别对应命题逻辑中的OR，AND和NOT运算。

逻辑运算具有短路性。即：第一个参数求值能确定表达结果，那么就不会对第二个参数求值。

有关位移运算

C语言提供了位移运算，向左或者向右移动位模式。

C表达式x << k会x向左移动k位，丢弃最高的k位，并在右端补k个0.

有一个相应的友谊运算x >> k。一般而言，机器支持两种形式的右移：逻辑右移和算术右移。逻辑右移在左端补k个0，算数右移是在左端补k个最高有效位的值。

对于无符号数，右移必须是逻辑的。

Java表达式中，x >> k是算术右移，x >>> k是逻辑右移。

加减法优先级比位移优先级要高

    一些位运算的常见技巧
    
    0 ^ a = a
    
    a ^ a = 0
    
    a & （a - 1）可以消除最右边的一个1
    
    位运算x & 0xFF生成一个由x的最低有效字节组成的值，而其他字节就被置为0。
    
    Java是用的补码，0x7fffffff是最大正整数，0x80000000是最小的负数。
    和0x7fffffff按位与就是取绝对值了，然后那个按位或就是求负数。
    
    可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a的奇偶性。
    
    修改正负号就是按位取反再加一，也就是~x + 1
    
    检验补码乘法是否溢出：
    int p = x * y;
    return !x || p / x == y;
    
    

2.2整数表示

整型数据类型表示有限范围的整数。

有一个很值得注意的特点是取值范围是不对称的，负数的范围比正数的范围大1.

无符号数的编码

无符号数编码详见思维导图。

补码编码

补码编码详见思维导图。

ω位补码所能表示的值的范围：最小是位向量[10……0]，最大的值是位向量[01……1]。

注意：-1和UMax有同样的位表示——全1的串。数值0在两种表示方式中都是全0的串。

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

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

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

补码转无符号数详见思维导图。

无符号数转为补码详见思维导图。

执行一个运算的时候，如果它的一个运算数是有符号的而另一个是无符号的，那么C语言会隐式的将有符号数强制类型转换为无符号数，并假设两个数都是非负的，来执行运算。

扩展一个数字的位表示

要将一个无符号数转换为一个更大的数据类型，只需要简单的在表示的开头添加0，这种运算被称为零扩展。

要将一个补码数字转换为一个更大的数据类型，可以执行一个符号扩展，在表示中添加最高有效位的值。

一个有意思的地方：
当把short转换成unsigned时，我们要先改变大小，之后再完成从有符号到无符号的转换。也就是说(unsigned)sx等价于(unsigned)(int)sx

截断数字

将一个ω位的数字截断为一个k位的数字，我们会丢弃最高的ω - k位。

补码截断也有相似的属性，不过要将最高位转换为符号位，也就是说，一个正数截断了以后可能就变成了负数。

2.3整数运算

无符号加法

详见思维导图

如果s没有溢出，则可以肯定s ≥ x

无符号数求反详见思维导图

补码加法

详见思维导图

对满足TMinω ≤ x， y ≤ TMaxω 的x和y，另s = x + y，当且仅当x > 0，y > 0，但s ≤ 0时，计算s发生了正溢出。当且仅当x < 0，y < 0，但s ≥ 0时，计算s发生了负溢出。

补码的非

详见思维导图

无符号乘法

详见思维导图

补码乘法

详见思维导图

乘以常数

编译器使用了一项重要优化，试着用位移和加法运算的组合来代替乘以常数因子的乘法。

考虑一组从位位置n到位位置m的连续的1（n≥m）我们可以用下面两种不同形式中的一种来计算这些位对乘积的影响：

• 形式A：(x << n) + (x << n - 1) + ... + (x << m)
• 形式B：(x << (n + 1)) - (x << m)

除以2的幂

• 除以2的幂无符号除法：C变量x和k有无符号数值x和k，且0 ≤ k ＜ ω，则x>>k产生数值，x / 2^k
• 除以2的幂补码除法，向下舍入：C变量补码x和无符号k，且0 ≤ k ＜ ω，当执行算术位移时，x>>k产生数值x / 2^k
• 除以2的幂的补码除法，向上舍入：C变量补码x和无符号k，且0 ≤ k ＜ ω，当执行算术位移时，（x + (1 << k）- 1) >> k产生数值x / 2^k。

遗憾的是，和乘法不同，我们不能用除以2的幂的出发来表示任意常数K的除法，所以除法绝大多数情况下指令会相当慢。

2.4浮点数

二进制小数

定义见思维导图

IEEE浮点表示

IEEE浮点标准用V = (-1)^s * M * 2^E

• s：sign，符号，决定正负。
• M：significand，尾数，通常是[1.0~2.0)范围的小数
• E：exponent，阶码，就是次方数。

单精度浮点格式中，s，exp和frac字段分别为1位、k = 8位和n = 23位，得到一个32位的表示。双精度浮点格式中，s、exp和frac字段分别为1位、k = 11位和n = 52位，得到一个64位的表示。

规格化的值

解码字段被解释为偏置形式表示的有符号整数。阶码的值是E = e - Bias，其中e是无符号数，而Bias是一个等于2^(k-1) - 1的偏置值。

小数子段frac被解释为描述小数值f，其中0 ≤ f < 1，二进制小数在最高有效为的左边。尾数定义为M = 1 + f。这种方式也叫做隐含的以1开头的表示.

非规格化的值

阶码值是E = 1 - Bias，而尾数的值是M = f，也就是小数字段的值，不包含隐含的开头的1.

非规格化数的另外一个功能是表示那些非常接近于0.0的数。它们提供了一种属性，称为逐渐溢出，其中，可能的数值分布均匀的接近于0.0.

特殊值

最后一类数值是当阶码全为1的时候出现的。当小数域全为0时，得到的值表示无穷，当s = 0时是+∞，当s = 1时是-∞。当我们把两个非常大的数相乘，或者除以零时，无穷能够表示溢出的结果。当小数域为非零的时候，结果值被称为“NaN”，即“不是一个数（Not a Number）”的缩写。一些运算的结果不能是实数或无穷，就会返回这样的NaN值，比如当计算根号-1或者∞-∞时。

浮点数的一些Point

• 值+0.0总有一个全为0的位表示。
• 最小的正非规格化的位表示，是有最低有效位为1而其他所有位为0构成的。它的数字值是V = 2^(-n-2(k-1)+2)。
• 最大的非规格化值的位模式是由全为0的解码字段和全为1的小叔子段组成的。数值V = (1 - 2^(-n)) * 2^((-2)(k-1)+2)。
• 最小的正规格化值的位模式的阶码字段的最低有效位为1，其他位全为0。它的尾数值M = 1，而阶码值E = -2^(k-1) + 2。因此数值V = 2^((-2)(k-1) + 2)。
• 值1.0的位表示的阶码字段除了最高有效为等于1以外，其他位都等于0。它的尾数值是M = 1，他的阶码值是E = 0.
• 最大的规格化值的位表示的符号位为0，阶码的最低有效位等于0，其他位等于1.数值V = （1 - 2^(-n-1)） * 2²(k-1)

舍入

IEEE浮点格式定义了四种不同的舍入方式。默认的方法是找到最接近的匹配，其他三种可用于计算上界和下界。

浮点运算

IEEE标准定义了一些使之更合理的规则。例如，定义1 / -0将产生-∞,而定义1 / +0会产生+∞

对于所有的x和y的值，实数的加法运算是可交换的。但是运算是不可结合的。例如（3.14 + 1e10）- 1e10

无穷（因为+∞ - ∞ = NaN）和 NaN是例外情况，因为对于任何x都有NaN + x = NaN。

浮点加法满足了单调性属性：如果a ≥ b，那么对任何a、b以及x的值，除了NaN，都有x + a ≥ x + b。

浮点乘法也遵循通常乘法所具有的许多属性。它是可交换的，不具有可结合行。例如（1e20 * 1e20） * 1e-20位+∞，而1e20 * （1e20 * 1e-20）得出1e20。

浮点乘法满足单调性：

a ≥ b 且 c ≥ 0 → a * c ≥ b * c
a ≥ b 且 c ≤ 0 → a * c ≤ b * c

我们还可以保证，只要a ≠ NaN，就有a * a ≥ 0.

C语言中的浮点数

所有C语言版本提供了两种不同的浮点数据类型：float 和 double。

一些会产生错误的点：

• 从int转成float，数字不会溢出，但是可能被舍入。
• 从int或float转成double，因为double有更大的范围，也有更高的精度，所以能够保留精确的数值。
• 从double转换成float，因为范围小，所以值可能溢出成+∞或者-∞，另外，也可能舍入。
• 从float或double转成int，值将会向零舍入。例如1.999转换为1，而-1.999转为-1.进一步来说，值可能会溢出。与Inter兼容的微处理器指定位模式[10...00]（字长为ω时的TMinω）为整数不确定值。一个从浮点数到整数的转换，如果不能为该浮点数找到一个合理的整数近似值，就会产生一个这样的值。因此，表达式（int）+le10会得到-21483648，即从一个正值变成了一个负值！！！

课后题中的一些点

1. 表达式~0xFF创建一个掩码，该掩码8个最低位为0，其余的为1.这个掩码的产生与字长无关。相比之下，0xFFFFFF00只能工作在32位机器上。
2. x ^ y = (x & ~y) | (~x & y)
3. TMin32是-2147483648，并且将它强制类型转换为无符号数后，变成了2147483648。另外，如果有任何一个运算数是无符号的，那么在比较之前，另一个运算数会被强制类型转换为无符号数。
4. 函数的任何测试过程中，TMin 都应该作为一种测试情况！！！
5. 对于无符号数的非，位的模式是相同的。
6. int64_t pll = (int64_t) x * y;这一句如果写成int64_t pll = x * y;就会用32位的值来计算乘积（这时候可能就溢出了！），然而再符号扩展到64位。
7. 表达式x>>32产生一个字，如果x是负数，这个字全为1，否则全为0.这个诀窍偶尔会有大用处。
8. 一个具有n位小数的浮点格式，不能准确描述的最小正整数是：1后面跟着n个0后面再跟一个1.即2^(n+1) + 1
9. 2.44C的谜题里的需要理解的计算机运算的属性。

32位机器，有符号值使用算术右移，无符号值使用逻辑右移
int x,y
unsigned ux,uy

A. (x > 0）||((x - 1) < 0
False 假设x = TMin32，那么x - 1 = TMax32
B.  (x & 7) != 7 || (x << 29 < 0)
True
C.  (x * x) >= 0
False 当x为0xFFFF时，x * x为-131071（0xFFFE0001）
D.  x < 0 || -x <= 0
True
E.  x > 0 || -x >= 0
False 设x = TMin32（好吧，又是它）那么x和-x都是负数！
F.  x + y == uy + ux
True
G.  x * ~y + uy * ux == -x
True ~y等于-y-1.uy * ux等于x * y，所以左边等价于x * -y - x + x * y。

勘误：43页第一段原文中写的是复数的范围比整数的范围大1，应该是正数……