【CSAPP】笔记-Cp2-2-数的表示与运算

少女dtysky

世界Skill

时刻2016.06.22

路标

CSAPP

计算机系统

信息存储

数据类型

整形

浮点数

CSAPP（深入理解计算机系统）第二章“信息的表示和处理”第二部分“数的表示与运算”的笔记和课后习题。
Github的同步工程在这

整形

整形数据顾名思义，是指整数，整数在计算机中的表示是精确的，也是有限的。一般而言，如果一个整数的位宽为w，则其表示的无符号整数所能表示数的范围为$0 \sim 2^w-1$，而有符号整数则能表示$-2^{w/2} \sim 2^{w/2}-1$。比如，对于一个32位的系统，其int型有符号整数的位宽是32，所以其范围是-2147483648 ~ 2147483647。

C中的整形数据类型一般有char、short、int、long、long long，位宽逐级递增，具体位宽取决于系统，在这些类型前加上unsigned便可以定义一个无符号数。

再次声明注意，在依赖于通信的应用中，字节序和位宽的匹配是特别重要的，如果可以，尽量使用c++中的stdint中的类型，或者自己定义一些uint_8t之类的类型。

编码

整数的编码可以区分为有符号和无符号两种，无符号编码整数对应的值即为其二进制对应的值，无需多言。有符号编码整数对应的值，一般是其二进制对应的补码。
补码是一种表示有符号数的编码形式，对于一个n位的有符号数A，其最高位为符号位，为1表示负数，为0表示正数，其他位为数值位。当A为正数时，数值位对应的二进制数即为A所代表的值，比如0111所代表的有符号数为7；A为负数时，数值位对应的二进制数的补码加上负号为A的值，比如1111表示-1。其计算规则为：

A的补码 = A的取反加1。比如当A = 111时，其补码为000 + 1 = 001。

当然，这并非最简单和最原始的算法，书中给出的方法是，对于有符号数A = abcd，其中abcd均为0或者1：

A=−a∗23+b∗22+c∗2+dA = -a*2^3 + b*2^2 + c*2 + d

除了补码之外，有符号数的表示方式还有反码和原码，反码即为补码减1，而原码即为将数值位直接作为其绝对值的负数。在整数的表示形式中，这二者除了在某些底层硬件应用外并不常用，不再过多讨论。需要注意的是这二者的0都有+0和-0两种形式。

补码的英文为Two's complement，反码为Ones' complement。我们可以用$2^w - x$来计算一个位宽w并且原码为x的数的补码，可以用$2^w\{1\} - x$来计算其反码。

转换

C中有符号数和无符号的转换在不同基础的计算机上不同，但都遵循同样的原则——不改变其最底层的字节本身，而只是改变解释的方式。这样会导致这种转换出现反直觉的结果，比如下面代码： 

int x = -111;
unsigned int y = (unsigned int)x;
printf("%u", y);

输出为4294967185。

通过以上定义，不难推出一系列的所谓补码和无符号数转换公式，但目测作用不大。

在C中

转换

C中的基础数据类型转换可以显示进行，也可以隐式进行。前者表现为float y = (float) x;这样的语句，其中x是int型变量；后者的表现则丰富的多，有float y = x;这种，也有在格式化输出时的printf("%u", x);这种，他会把int型变量x转换为无符号数输出。

在运算中，如果一个数是有符号而另一个为无符号的，则有符号数会被隐式转换为无符号数，这体现在加减乘除个各种比较运算中，比如： 

int x = -1;
unsigned int y = 0;
printf("%d", x < y);

得到的结果是0，即false，因为此时x被当做无符号数处理了，是一个很大的正数。

在标准库文件limits.h中定义了int的最大和最小值，其中： 

#define INT_MIN (-INT_MAX - 1)

这是由于一些比较隐晦的原因。

扩展和截断

数的位扩展一般发生在不同字长的整数的转换时，例如当一个整数从char型转换为int型时，就需要将8bits的数转换为32bits（在32bits的系统下）。对于无符号数，直接将低八位保留，高八位补零即可，但对于有符号数，则需要根据符号位的情况选择补零还是补一。

数的截断类似于扩展，不过与后者相反。截断在位级对于有符号数和无符号数都是相同的，都是高位裁剪，但结果还保留着原先的性质，无需多说。

一个利用符号数的漏洞

C中，memcpy函数将一块内存从一个地址拷贝到另一个地址，这个函数有一个参数n，表示要拷贝内存的长度，n的类型是size_t，是一个无符号数。如果给n赋予一个有符号的负数，将会导致被复制的内存大小改变，这显然会导致一些意外的结果。

这个现象导致了曾经FreeBSD中getpeername函数的漏洞。

一般而言，高级语言都尽量避免无符号数直接被程序员操作。这也是为了防止错误。

整数运算

计算机中的整数运算本质上和数学上的整数运算等价，但由于计算机中数值的有限性，所以可能会出现一些反直觉的现象。

无符号加法

无符号加法最大的一个问题就是溢出，虽然在Lisp系等语言中无限精度的运算是可能的，但像是C系的语言，运算还是有限精度的，这就会出现溢出问题。比如两个32bits的数进行运算，运算结果超过了32bits，这就造成了一次溢出。

对于有限精度的等宽w位无符号整数，其加法本质上等于两个数的算术和对$2^w$取模，这表现为对溢出位w+1的舍弃。比如两个四位整数9和16，其算术和为25，二进制表示为11001，将最高为舍弃后为1001，即9 = 25 % 16。

补码加法

有符号加法在此处指补码的加法，其最大的问题同样是溢出。对于一个两个w位的补码有符号数相加，当其和sum正向超出w位可表示的补码有符号数范围时，会发生正溢出，最终结果为$sum - 2^w$；反之，当逆向超过时发生负溢出，最终结果为$sum + 2^w$。

补码的非

补码的非由于INT_MIN的存在变得有点奇怪，对于不等于INT_MIN的数，其取反就是自己的相反数，反之就是其自身。

无符号乘法

无符号乘法就是加法的叠加，对于两个w位的补码有符号数x和y，其乘法本质为：

x * y = (x * y) % $2^w$

补码乘法

补码乘法在位级上与无符号乘法完全一致，截断也一样，只是在最后的解释上有所不同。

乘以常数

一种常用的优化，可以将乘法拆为左移和加减法的组合来提高性能。比如：

y = x * 3 = x * 1 + x * 2 = x + x << 2

2的幂的除法

和常数乘法类似，常数除法也可以拆分，不过拆分到的是右移运算。在正整数除法的前提下，无论是算术还是逻辑右移1位和除以2是等价的，虽然在除不尽的情况下，结果应该是一个小数，但在整数除法中定义将商+余数这种结果中的商，也就是小数结果的向下舍入后的舍入值作为最终结果。
而对于负数，则应当是向上舍入 ，并不和算术右移等价。修正的方法是：

$$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$$

本质上，无论对于正数还是负数，原则都是向零舍入。它们在计算时唯一的区别是如何构造那个偏置值是y-1还是0。详见习题42的解答。

浮点数

浮点数是计算机内部采用的用于表示实数的系统，他可以表示整形无法表示的小数部分，当然，在某些特殊领域中也常用定点数，但浮点数还是最一般的。但理解定点数仍然对理解浮点数有着不小的好处。

定点数

首先考虑十进制实数的表达，一个拥有m位整数位和n为小数位的实数，其本质上是：

$$x = \sum_{i=0}^ma_i10^i + \sum_{i=n}^0a_i10^i$$

二进制也类似，为：

$$x = \sum_{i=0}^ma_i2^i + \sum_{i=n}^0a_i2^i$$

在实数的表示中，我们用.这个符号来分隔整数和小数部分，成为点。 在计算机中，一个数的位宽确定的情况下，当点的位置固定时，我们就称这个数为定点数，以下便是一个4位整数4位小数的二进制定点数：

整数 点 小数
0101 . 1000

它代表的数为5.5。

需要注意的是，计算机中除了整形和部分小数之外，很多数都是不精确的，这其实相当于十进制中有理数和无理数。

IEEE浮点表示

IEEE浮点表示规则是一种当前几乎所有计算机遵循的通用标准，它规定一个浮点数的构造如下：

$$(-1)^s * M * 2^e$$

其中，s为符号，M为尾数，是一个二进制小数，E为阶码，其作用为对浮点数加权，可以为负数。我们可以很清晰看到，这实际上是一种科学计数法。下表表示了一个32位浮点数：

31 30~23 22~0
s exp frac

其中s为符号位，exp为为模式或者阶码，frac为尾数，通过设置exp可以将浮点数设为几种不同的模式：

规格化的值

exp各位不全为0或1时，为规格化的值。此时，阶码被解释为一个以偏置形式表示的有符号整数，为阶码E=exp-Bias，exp被作为无符号整数，而Bias为exp位数减1所能代表的最大有符号数减1。同时，此时frac被作为一个整数位为0的小数的小数位，尾数为frac+1，即将整数位替换为1，这种方式被称作隐含的以1开头的表示。于是，此时的数为：

x=(−1)s∗(1+frac)∗2exp−Biasx = (-1)^s * (1 + frac) * 2^{exp - Bias}

非规格化的值

这种格式的一个作用是表示0，exp和frac全为0时，当s为0时，表示数+0.0，s为1时，表示数-0.0。

另一个作用是表示非常接近于0的数，此时exp仍然为0，但是frac却不一定，这提供了一种叫做逐渐溢出的属性。此时的E=1 - Bias，M=frac，使得从最小规格数到最大非规格数的平滑过渡。

特殊值

当exp各位全为1时，表示特殊值。若frac全为0，得到的值表示无穷，s为0为正无穷，否则为负无穷。若frac不为0，则值为NaN，这表示运算结果不是一个实数或者无穷值。

为何如此设计

一切设计都是为了平滑、方便。比如如果将浮点数解释为无符号整数，会发现在浮点数自身升序排列时，此整数也是升序的，它们有着一致性，这意味着可以用一套排序解决两个问题。

舍入

由于浮点数无法准确表示很多数字，所以舍入就显得有些重要，IEEE浮点格式规定了四种不同的摄入方式，分别为向偶数舍入、向上舍入、向下舍入、向零舍入四种。

后三种已经在前面的有符号乘法探讨过，看似最符合直觉，但实际上浮点数中默认使用的却是向偶数舍入。对于一个二进制数，最低位为1则为奇数，否则为偶数。
当XXX...YYY...Y100这种形式时，向偶数舍入才有效，我们总是倾向于让最低位为0。

运算

浮点数运算基本上可以看做是两个浮点数精确运算后的舍入解，但考虑到浮点数种有规格外和特殊的值（Nan、inf等），所以运算并非总是可以这么去做。
由于舍入的存在，浮点数运算也不具备结合性。例如，对于0.000001 + 1000000 - 1000000和0.000001 + (1000000 - 1000000)，其结果就完全不同，前一个式子在第一运算中由于舍入会将0.000001丢失。

C中的浮点数

在C中，浮点数有float个double两种类型，前者单精度，32bits，后者双精度，64bits。但由于C中不要求机器使用IEEE标准，所以对于特殊值，并没有标准要求，不同编译器定义不同。

需要注意的是强制类型转换的时候，会发生许多期望之外的状况：

int转为float或者double时不会溢出但可能舍入，double转为float时可能发生溢出为正负无穷的状况，double和float到int时发生向零舍入。

习题

所有有代码的练习都以以题号为名字的单个文件内。

代码位于CSAPP-Chapter2内。

17

基础计算，略过。

18

A: 0b0000000110111000 = 440
B: 0b0000000000010100 = 20
C: 0b1111111001011000 = - (0b0000000110100111 + 1) = -424
......

19

将十进制的二进制补码表示按照二进制无符号数解释即可。

20

比如对于-8，其补码为1000，位宽w = 4，所以，补码转换为无符号数的结果为$-8 + 2^4 = 8$，结果和直接将二进制解释为无符号数时一致。

21

只需要注意有符号数和无符号是在计算式会被隐式转换为无符号数即可。

22

对于A：

$$x = -1 * 2^3 + 1 * 2 + 1 * 1 = -5$$

对于其他也一样。

23

fun1先对word左移24位，再逻辑右移24位，之后转换为有符号数。
fun2先将word转换为有符号数，之后左移24位，再算术右移24位。

w fun1(2) fun2(w)
0x00000076 0x00000076 0x00000076
0x87654321 0x00000021 0x00000021
0x000000c9 0x000000c9 0xffffffc9
0xedcba987 0x00000087 0xffffff87

24

位级去掉最高位，将剩余解释为有符号或者无符号数即可。

25

详见代码。

当数组长度为0时，由于length为无符号数，所以length - 1语句将得到一个无符号数的结果，在32bits的机器上，此结果为0xffffffff对应的无符号数，是一个很大的正数。所以在循环时，会有数组越界发生，即访问未初始化的存储区域，发生错误。

将i <= length - 1改为i < length可破。

26

详见代码。

size_t为无符号数，s与t的长度的相减也会的到一个无符号结果，这使得改结果与0相比较大或相等，无法得到正确结果。
将相减后与0比较直接改为两个长度相比较即可。

27

比较x + y 和 x（或y）的大小即可。

28

套公式，略过。

29

基础计算，略过。

30

详见代码。

溢出只有可能在x和y同号时出现，都为正时可能发生正溢出，即最终和为负，都为负时则可能发生负溢出，即和最终为正。

31

溢出是可逆的，即便sum溢出了，但sum - x = y却还是成立的。

32

因为补码的值域不是关于y轴对称的，所以当y为INT_MIN时，-y会直接发生溢出，变为y，此时如果x为0，题目所示的函数将不会认为溢出，但实际上已经溢出了。

在原先的代码加一个分支即可。

33

0xF的补码是其自身，其他都是相反数。

34

基础运算，略过。

35

1

$$B2T_{2w}(x) = -x_{2w-1} 2^{2w-1} + x_{2w-2} 2^{2w-2} + ... + x_w * 2^2 + \sum_{i=0}^{w-1}x_i2^i$$

$$=2^w({-x_{2w-1} 2^{w-1} + x_{2w-2} 2^{w-2} + ... + x_w}) + \sum_{i=0}^{w-1}x_i2^i$$

$$=2^w({-x_{2w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i2^i}) + \sum_{i=0}^{w-1}x_i2^i$$

$$=2^wv + u$$

已知有符号和无符号乘法在位形式上一致，令上述公式的x=x*y，其中p是乘积x*y在w位时的补码形式，则有：

$$u=p_{w-1}2^w+p$$

于是有：

$$x*y = 2^w(v+p_{w-1})+p$$

令$t = v+p_{w-1}$则：

$$x*y = t2^w+p$$

即证。

2

由于p是一个整数，所以其总是可以被分解为一个非零整数、商和余数的和，即：

$$p = xq + r$$

即证。

3

令q=y，则有：

$$p = xy + r$$

而$p=xy-t2^w$，固有：

$$r=-t2^w$$

由于r的绝对值小于x的绝对值，而x又是一个补码，所以x的最大值为$2^w$，同时t为一个大于等于1的数，所以要使此等式成立，r和t都必须为0，即证。

36

详见代码。

37

改进是这段代码的乘法计算部分不再溢出，但由于malloc的最后一个参数是size_t，所以还是存在问题的。

解决方法就是将相乘的两个数都声明为int型，这样它们都为正数时，相乘放入一个size_t中时便不会溢出。
而实际上，这两个值的确都是正数。

38

b为0时，可以计算1、2、3、8倍，为a时，可以计算2、3、5、9倍。

39

$$(2^{n+1} - 2^m)x = 2^m(2^{n+1-m}-1)x$$

即：

((x << n+1-m) - x) << m

40

  1. x << 3 - x << 1
  2. x << 5 - x
  3. x << 1 - x << 3
  4. y = x << 2 + x; y << 1 + y << 3

41

如果n有可能超过位宽，选A。
否则，选B。

42

详见代码。

可以使用31位的符号右移确定x是正数或者负数，而后使用mask得到合适的偏置，最后直接根据公式求解。

43

$$M = 2^6 - 1$$

N=23N = 2^3

44

  1. 要使该式为假则必须要找到整数x，使得x-1>=0且x<=0，这样的x在C中是存在的，即x=INT_MIN，减1运算后会发生溢出。
  2. 若x&7为7则x的低三位全为1，而x<<29大于0则x的倒数第3位为0，这样的x不存在，所以原式必然为真。
  3. 当结果会溢出的时候，原式便可能为假。
  4. 事实上，整数x如果不是负数就是0要么就是正数，并且原式没有特别的边界情况，恒成立。
  5. 与4基本一致，但当x=INT_MIN的时候，-x由于溢出仍然为x=INT_MAX,还是为负，这可以使得原式为假。
  6. 恒成立，C中，当无符号数和有符号数做运算时，会把有符号数转为无符号数，而有符号数和无符号数在位级上运算又是等价的。
  7. -y=~y+1 -> ~y=-y-1，所以这个式子本质上和6中的一致，原式成立。

45

基础运算，略过。

46

A. 为0.{23个0}1100110011001100.......

B. 为$\sum_{i=-\inf}^{-24}a_i2^i$，其中，当i % 4 == 0 or 1时，$a_i=1$，否则为0。求和如下：

$$sum = 2^{-24} + 2^{-25} + 2^{-28} + 2^{-29} + ......$$

$$=2^{-24}(1 + 1/2) + 2^{-28}(1 + 1/2) + ......$$

$$=3 * 2^{-25} * (1 + 2^{-4} + ......)$$

$$=1/(2^{20} * 10) \approx 9.53 * 10^{-8}$$

C. 约为 $9.53 * 10^{-8} * 36000 = 0.034$秒。

D. 约为0.034 * 2000 = 68米。

47

基础计算，略过。

48

整形数的二进制表示为00000000001 101011001000101000001。
浮点数的二进制表示为0 10010100 10101100100010100000100。

浮点数的s = 1，exp = 148 -> e = 148 - 127 = 21，frac = 0.6739811897277832 -> M = 1.6739811897277832。

通过上面对比可见，整形表示的最后21位和浮点数frac中的前21位是一致的。

49

A.

$$min = 2^{n + 1} + 1$$

B.

224+1=167772172^24 + 1 = 16777217

50

基本计算，略过。

51

A. 由于末尾0后两个1，原数加1舍入更为合理，即x' = 0.00011001100110011001101。

B. 为$\sum_{i=-\inf}^{-24}a_i2^i$，其中，当i % 4 == 0 or 1时，$a_i=0$，否则为1。求和如下：

$$sum = 2^{-26} + 2^{-27} + 2^{-30} + 2^{-31} + ......$$

$$=2^{-26}(1 + 1/2) + 2^{-28}(1 + 1/2) + ......$$

$$=3 * 2^{-27} * (1 + 2^{-4} + ......)$$

$$=1/(2^{22} * 10) \approx 2.38 * 10^{-8}$$

C. 约为0.0008秒。

D. 约为1.71米。

52

基础计算，略过。

53

假设1e400溢出位正无穷，则有：

POS_INFINITY = 1e400
NEG_INFINITY = -POS_INFINITY
NEG_ZERO = -1.0 / POS_INFINITY

54

A. 真，int到double的转换不会有任何精度损失，而转回时不会发生舍入。
B. x为INT_MAX时会发生溢出。
C. d超过了float的范围数会发生舍入。
D. 真，float到double的转换不会有任何精度损失，而转回时不会发生舍入。
E. 真，浮点数取反只影响符号位。
F. 真，整形和浮点数计算是会被转换为浮点数。
G. 真，即便d*d发生了溢出到正无穷，但规则保证此不等式成立。
H. 当f远大于d时，会发生舍入。

如果不是自己的创作，少女是会标识出来的，所以要告诉别人是少女写的哦。