CSAPP读书笔记与习题作业练习-第2章

CSAPP读书笔记与习题作业练习-第2章

• 疑问

• • 疑问一 练习题2.41解答中m=0的问题（已解决）

• 习题

• • 练习题2.1
  • 练习题2.2
  • 练习题2.3
  • *练习题2.4
  • 练习题2.5
  • 练习题2.6
  • *练习题2.7
  • 练习题2.8
  • *练习题2.9
  • 练习题2.10
  • 练习题2.11
  • 练习题2.12
  • 练习题2.13
  • 练习题2.14
  • 练习题2.15
  • 练习题2.16
  • 练习题2.17
  • 练习题2.18
  • 练习题2.19
  • 练习题2.20
  • 练习题2.21
  • 练习题2.22
  • 练习题2.23
  • 练习题2.24
  • 练习题2.25
  • 练习题2.26
  • 练习题2.27
  • 练习题2.28
  • 练习题2.29
  • 练习题2.30
  • 练习题2.31
  • 练习题2.32
  • 练习题2.33
  • 练习题2.34
  • *练习题2.35
  • 练习题2.36
  • 练习题2.37
  • 练习题2.38
  • ?练习题2.39
  • 练习题2.40
  • 练习题2.41
  • 练习题2.42
  • 练习题2.43
  • 练习题2.44
  • 练习题2.45
  • 练习题2.46
  • 练习题2.47
  • 练习题2.48
  • 练习题2.49
  • 练习题2.50
  • 练习题2.51
  • 练习题2.52
  • 练习题2.53
  • 练习题2.54

• 整理

• • 定义与公式
  • • 2.1 无符号数编码的定义
    • 2.2 补码编码的定义
    • 2.3 补码转换为无符号数
    • 2.4 无符号数转换为补码
    • 2.5 无符号数的零扩展
    • 2.6 补码的符号扩展
    • 2.7 截断无符号数
    • 2.8 截断补码
    • 2.9 无符号数加法
    • 2.10 检测无符号数加法中的溢出
    • 2.11 无符号数求反
    • 2.12 补码加法
    • 2.13 检测补码加法中的溢出
    • 2.14 补码的非
    • 2.15 无符号乘法
    • 2.16 补码乘法
    • 2.17 无符号和补码乘法的位级等价性
    • 2.18 乘以2的幂
    • 2.19 与2的幂相乘的无符号乘法
    • 2.20 与2的幂相乘的补码乘法
    • 2.21 除以2的幂的无符号除法
    • 2.22 除以2的幂的补码除法，向下舍入
    • 2.23 除以2的幂的补码除法，向上舍入
    • 2.24 IEEE754标准表示浮点数

疑问

疑问一 练习题2.41解答中m=0的问题（已解决）

问题：练习题2.41解答将情况分为m>0和m=0两种情况，在证明m>0的情况后指出m=0时形式A和B都会少一次移位。为什么需要考虑m=0的情况？

回答：当m=0时x<<m即x本身，不需要计算左移0位的结果。

习题

练习题2.1

A. 0011 1001 1010 0111 1111 1000
B. 0XC97B
C. 1101 0101 1110 0100 1100
D. 0X26E7B5

练习题2.2

练习题2.3

*练习题2.4

A. 0x503c+0x0008=0x5044
B. 0x503c-0x0040=0x4f5c
C. 0x503c+0x0004=0x5040
D. 0X50ea-0x503c=0x00ae

更正：
对于B来说：0x503c-0x0040=0x4ffc，第3位应该是3+16-4，这里错误计算成了3+10-4
对于C来说： 0x503c+64=0x503c+0x0040=0x507c ，64的16进制计算错误

练习题2.5

A. 小端法：21 大端法：87
B. 小端法：21 43 大端法：87 65
C. 小端法：21 43 65 大端法：87 65 43

练习题2.6

A.整数：0000 0000 0011 0101 1001 0001 0100 0001 浮点数： 0100 1010 0101 0110 0100 0101 0000 0100
B.21
C.整数前面一部分不匹配，浮点数只在中间的部分匹配。

*练习题2.7

61 62 63 64 65 66
strlen函数不计算null字符

练习题2.8

*练习题2.9

A.
黑色RGB位向量[0 0 0]，位向量的补是[1 1 1]，对应白色，所以黑色的补是白色
蓝色RGB位向量[0 0 1]，位向量的补是[1 1 0]，对应黄色，所以蓝色的补是黄色
绿色RGB位向量[0 1 0]，位向量的补是[1 0 1]，对应红紫色，所以绿色的补是红紫色
蓝绿色RGB位向量[0 1 1]，位向量的补是[1 0 0]，对应红色，所以蓝绿色的补是红色
因为位向量\sim(\sim a)=a，所以可得：
白色的补是黑色
黄色的补是蓝色
红紫色的补是绿色
红色的补是蓝绿色

B.
蓝色|绿色 =[0 0 1] | [0 1 0]=[0 1 1] =蓝绿色
黄色&蓝绿色=[1 1 0] & [0 1 1]=[1 1 1]=白色
红色^红紫色=[1 0 0] ^ [1 0 1]=[0 0 1]=蓝色

更正：
B中 黄色&蓝绿色=[1 1 0] & [0 1 1]=[0 1 0]=绿色 这里位运算结果错了。

练习题2.10

练习题2.11

A.first=last=k
B.当inplace_swap(k,k)时会导致

    *k = *k ^ *k //*k此时为0
    *k = *k ^ *k 
    *k = *k ^ *k //*k执行第一行后一直为0
    
    
    c
    
    

C.把for循环的结束条件中的等号去掉

练习题2.12

A.x=x&0xFF
B.x=(~x&0x00)&(x&0xFF)
C.x=x|0xFF
更正：
B 可以为 x=x^~0xFF

练习题2.13

    int bool_or(int x, int y) {
    	int result = bis(x,y);
    	return result;
    }
    
    int bool_xor(int x, int y) {
    	int result =  bis(bic(x,y),bic(y,x));
    	return result;
    }
    
    
    c
    
    

练习题2.14

x=0110 0110
y=0011 1001

练习题2.15

!(x^y)

练习题2.16

练习题2.17

练习题2.18

A.736
B.-88
C.40
D.-48
E.120
F.136
G.504
H.192
I.-72

练习题2.19

练习题2.20

练习题2.21

练习题2.22

A.B2T_4([1011])=-x_{4-1}2^{4-1}+\displaystyle\sum_{n=0}^{4-2}x_i2^i=-2^3+2^1+2^0=-5
B.B2T_5([11011])=-x_{5-1}2^{5-1}+\displaystyle\sum_{n=0}^{5-2}x_i2^i=-2^4+2^3+2^1+2^0=-5
C.B2T_6([111011])=-x_{6-1}2^{6-1}+\displaystyle\sum_{n=0}^{6-2}x_i2^i=-2^5+2^4+2^3+2^1+2^0=-5

练习题2.23

A.

B.fun1从无符号数的最低有效位取1字节，高位皆置为0，然后转化为补码
fun2从无符号数的最低有效位取1字节，高位用根据第8位置为1或0，然后转化为补码

练习题2.24

练习题2.25

因为无符号数length=0时length-1的结果为UMax_{32}，第一次循环的比较条件变为了无符号数0<=UMax_{32}，所以程序会访问一个长度为0数组的0号元素，导致出错。

练习题2.26

A.当字符串s比字符串t短时还结果会不正确
B.因为strlen函数返回无符号整数，当字符串s短于字符串t时，无符号整数相减仍大于0，导致函数会返回1。
C.将return strlen(s) - strlen(t) > 0;改为return (int)(strlen(s) - strlen(t)) > 0;
更正：
C可以为return strlen(s)>strlen(t)

练习题2.27

    int uadd_ok(unsigned x,unsigned y){
    	return x+y>=x;
    }
    
    
    c
    
    

练习题2.28

练习题2.29

练习题2.30

    /* Determine whether arguments can be added without overflow */
    int tadd_ok(int x,int y){
    	int sum = x+y;
    	int neg_over = x <  0 && y <  0 && sum >= 0;
    	int pos_over = x >= 0 && y >= 0 && sum <  0;
    	return !neg_over && !pos_over;
    }
    
    
    c
    
    

练习题2.31

当发生正溢出时，sum=x+y-2^{32} 。而sum-x=y-2^{32}。因为y<2^{31}，所以y-2^{32}<-2^{31}，即sum-x<-2^{31}。所以sum-x=sum-x+2^{32}=y-2^{32}+2^{32}=y，同理sum-y=x。所以即使发生正溢出，该段代码也会返回真值。发生负溢出时也同理，所以本题代码无法生效。

练习题2.32

当y=-2^{31}时，-y=2^{31}，发生正溢出-y=2^{31}-2^{32}=-2^{31}，tadd_ok(x,-y)会在x<0判断为溢出，从而导致tsub_ok(x,y)判断为溢出，而事实上当x<0，y=-2^{31}，x-y并不会产生溢出。

练习题2.33

更正：-5=-8+2+1=1011_{(2)}=B

练习题2.34

| 无符号
补码| 4 [100]
-4 [100]| 5 [101]
-3 [101]| 20 [10100]
12 [01100]| 4 [100]
-4 [100] |
| 无符号
补码| 2 [010]
2 [010]| 7 [111]
-1 [111]| 14 [01110]
-2 [11110]| 6 [110]
-2 [110] |
| 无符号
补码| 6 [110]
-2 [110]| 6 [110]
-2 [110]| 36 [100100]
4 [000100]| 4 [100]
-4 [100] |

*练习题2.35

当x\neq0时，有以下证明

1. 

x\cdot y的结果可以表示为2\omega的位向量，根据补码的定义x\cdot y=a\cdot 2^\omega+b，a是高\omega位的补码，b是低\omega位的无符号数。
根据补码和无符号数乘法的位级等价性，有b=T2U_\omega(p)。令p_{\omega-1}为p的最高位，则有b=T2U_\omega(p)=p+p_{\omega-1}2^{\omega}。令t=a+p_{\omega-1}，所以有x\cdot y=p+t\cdot 2^\omega 所以当t=0时，x\cdot y=p，乘法不溢出。当t\neq 0时，x\cdot y=p+t\cdot 2^\omega\neq p，乘法不溢出。

2. 

整数除法的定义，p除以非零整数x商为q，余数为r，其中|r|<|x|

3. 

当q=y时，x\cdot y=p+t\cdot 2^\omega=x\cdot q+r+t\cdot 2^\omega=x\cdot y+r+t\cdot2^\omega。因为|r|<|x|<2^\omega，所以r+t\cdot2^\omega只有在r=t=0时才为0。
当r=t=0时，x\cdot y=p+t\cdot 2^\omega=x\cdot q+r+t\cdot 2^\omega=x\cdot q，即q=y。

当x=0时，乘法不溢出。

所以该函数可靠。

练习题2.36

    int tmult_ok(int x,int y){
    	int64_t mult = (int64_t)x * y;
    	return mult == (int)mult;
    }
    
    
    c
    
    

练习题2.37

A.
并没有改进，虽然asize计算了不会溢出的值，但是malloc函数还是会强制转换成32位整数，结果还是溢出了。
B.将第9行替换以下代码

    uint64_t totalSize = (uint64_t)ele_cnt * ele_size;
    void* result = totalSize==(size_t)totalSize ? malloc(totalSize) : NULL;
    
    
    c
    
    

练习题2.38

b=0时a<<k+b可以表示a2^k。
b=a时a<<k+b可以表示a(2^k+1)。

?练习题2.39

可以写成x<<n-x<<k+x<<n
似乎没有必要，因为除非x等于1才可以左移n位，只要x>1就会在左移时溢出，这样处理产生的溢出问题和x左移n+1位等于0的问题没有太大区别

练习题2.40

练习题2.41

假设加法减法的效率一样。
对于形式A来说，当n=m时，只需要一次移位；当n>m时需要n-m+1次移位和n-m次加法。
对于形式B来说，当n=m时，需要两次移位和一次减法；当n>m时需要2次移位和1次减法。
所以令n-m+1=2即n=m+1时，两种形式的操作次数相同。
当n>m+1时，形式B操作次数少。
当n=m时，形式A操作次数少。

练习题2.42

    int div16(int num){
    	return (num+((num>>31)&0xF))>>4;
    }
    
    
    c
    
    

练习题2.43

x左移5位减去x等于x乘2^5-1=31
y右移3位等于y除以2^3=8
所以M是31，N是8.

练习题2.44

A.假 x=TMin_{32}时x<0，x-1=TMax_{32}>0
B.真 (x & 7) != 7等价于[x_2x_1x_0]\neq111，而(x<<29)<0等价于x_2=1
C.假 根据补码乘法，令x^2 \bmod 2^{32}>2^{31}则xx<0。取x=0xFFFF，xx=FFFE0001<0
D.真 令0\leqslant x\leqslant TMax_{32}，则-TMax_{32}\leqslant-x\leqslant0
E.假 当x=TMin_{32}时，-x=TMin_{32}<0
F.真 无符号数和补码加法位级表示相同
G.真 ~y+uy等价于全1的乘数，等价于2^{32}-1，2^{32}做乘数会溢出，所以剩-x

练习题2.45

练习题2.46

A.0.\underbrace{0,\cdots,0}_{23个0}1100[1100]\cdots
B.与\frac{1}{10}的二进制相比较，0.1-x的值为\frac{1}{10}\cdot 2^{-20}，十进制约为9.54\cdot 10^{-8}
C.100小时为360000秒，误差为360000/0.1\cdot(0.1-x)\approx 3.6\cdot 10^{6}\cdot9.54\cdot 10^{-8}=0.34344秒
D.0.34344\cdot 2000\approx687米

练习题2.47

练习题2.48

3510593=11 0101 1001 0001 0100 0001_{(2)}=1.1 0101 1001 0001 0100 0001\times 2^{21}
则小数字段为[101 0110 0100 0101 0000 0100]（右补2个0）
阶数偏置值为Bias=2^7-1=127，阶数无符号值为e=E+Bias=21+127=148
阶数字段为[1001 0100]，符号位为0
所以浮点数3510593.0的位模式为[0100 1010 0101 0110 0100 0101 0000 0100]
转化为十六进制为0x4A564504。
可见整数与浮点数的位之间有如下对应关系：从整数高位第一个1的右侧位开始数23个位（到整数最低位就停止）和浮点数从高位第10位开始相对应。

练习题2.49

A.2^{n+1}+1
B.带入上式得整数为16 777 217

练习题2.50

A.舍入前：2.25 舍入后：10.0_{(2)}=2.0
B.舍入前：2.375 舍入后：10.1_{(2)}=2.5
C.舍入前：2.75 舍入后：11.0_{(2)}=3.0
D.舍入前：3.125 舍入后：11.0_{(2)}=3.0

练习题2.51

A.x'=0.000 1100 1100 1100 1100 1101_{(2)}
B.x'-0.1=0.000 0000 0000 0000 0000 0000[0011]\cdots_{(2)}=0.1\cdot2^{-22}\approx2.38\cdot10^{-8}
C.100小时为360000秒，误差为360000/0.1\cdot(x'-0.1)\approx 3.6\cdot 10^{6}\cdot2.38\cdot 10^{-8}=0.086秒
D.0.086\cdot 2000\approx172米

练习题2.52

练习题2.53

    #define POS_INFINITY 1e400
    #define NEG_INFINITY (-POS_INFINITY)
    #define NEG_ZERO (1.0/NEG_INFINITY) 
    
    
    c
    
    

练习题2.54

A.真 double比int的精度和范围更高
B.假 0x1FFFFFF会变成0x2000000
C.假 1e40会变成正无穷
D.真 double比float的精度和范围更高
E.真 浮点数加负号等价于符号位取反
F.真 执行除法前分子分母都会转化为浮点数
G.真 不过可能会溢出到正无穷
H.假 当f和d的二进制表示差了23位以上就会舍入，例如f=1.0e20 d=1.0，(f+d)-f=0

整理

定义与公式

2.1 无符号数编码的定义

对向量\vec{x}=[x_{\omega-1},x_{\omega-2},\cdots,x_0 ]：B2U_\omega(\vec{x})\doteq\displaystyle\sum_{n=0}^{\omega-1}x_i2^i

2.2 补码编码的定义

对向量\vec{x}=[x_{\omega-1},x_{\omega-2},\cdots,x_0 ]：B2T_\omega(\vec{x})\doteq-x_{\omega-1}2^{\omega-1}+\displaystyle\sum_{n=0}^{\omega-2}x_i2^i

2.3 补码转换为无符号数

对满足TMin_\omega\leqslant x\leqslant TMax_\omega的x有：
T2U_\omega (x)= \left\{ \begin{aligned} &x+2^\omega, &x \right.

2.4 无符号数转换为补码

对满足0\leqslant x\leqslant UMax_\omega的x有：
U2T_\omega (u)= \left\{ \begin{aligned} &u, &u\leqslant TMax_\omega \\ &u-2^\omega, &u\gt TMax_\omega \end{aligned} \right.

2.5 无符号数的零扩展

定义宽度为\omega的位向量\vec{u}=[u_{\omega-1},u_{\omega-2},\cdots,u_0]和宽度为{\omega'}的位向量\vec{u'}=[0, \cdots ,0,u_{\omega-1},u_{\omega-2},\cdots,u_0]，其中{\omega'}>\omega。则B2U_\omega(\vec{u})=B2U_{\omega'}(\vec{u'})

2.6 补码的符号扩展

定义宽度为\omega的位向量\vec{x}=[x_{\omega-1},x_{\omega-2},\cdots,x_0]和宽度为{\omega'}的位向量\vec{x'}=[x_{\omega-1}, \cdots ,x_{\omega-1},x_{\omega-1},x_{\omega-2},\cdots,x_0]，其中{\omega'}>\omega。则B2T_\omega(\vec{x})=B2T_{\omega'}(\vec{x'})

2.7 截断无符号数

令对向量\vec{x}=[x_{\omega-1},x_{\omega-2},\cdots,x_0 ],而\vec{x'}是将其截断为k位的结果：\vec{x'}=[x_{k-1},x_{k-2},\cdots,x_0 ]。令x=B2U_\omega(\vec{x}),x'=B2T_k(\vec{x'})，则x'=x\bmod 2^k。

2.8 截断补码

令对向量\vec{x}=[x_{\omega-1},x_{\omega-2},\cdots,x_0 ],而\vec{x'}是将其截断为k位的结果：\vec{x'}=[x_{k-1},x_{k-2},\cdots,x_0 ]。令x=B2U_\omega(\vec{x}),x'=B2T_k(\vec{x'})，则x'=U2T_k(x\bmod 2^k)。

2.9 无符号数加法

对满足0\leqslant x,y<2^\omega的x和y有：
x+_\omega^uy= \left\{ \begin{aligned} &x+y,&&x+y \right.

2.10 检测无符号数加法中的溢出

对在范围0\leqslant x,y\leqslant UMax_\omega中的x和y，令s\doteq x+_\omega^uy。则对计算s，当且仅当s（或等价地s）时，发生了溢出。

2.11 无符号数求反

对满足0\leqslant x<2^\omega的任意x，其\omega位的无符号逆元-_\omega^ux将由下式给出：
-_\omega^ux= \left\{ \begin{aligned} &x,&&x=0 \\ &2^\omega-x,&&x>0 \end{aligned} \right.

2.12 补码加法

对满足-2^{\omega -1}\leqslant x,y\leqslant2^{\omega-1}-1的整数x和y有：
x+_\omega^ty= \left\{ \begin{aligned} &x+y-2^\omega,&&2^{\omega-1}\leqslant x+y &&正溢出\\ &x+y,&&-2^{\omega-1}\leqslant x+y \right.

2.13 检测补码加法中的溢出

对在范围TMin_\omega\leqslant x,y\leqslant TMax_\omega中的x和y，令s\doteq x+_\omega^ty。当且仅当x>0,y>0,但s\leqslant0时，计算s发生了正溢出。当且仅当x<0,y<0,但s\geqslant0时，计算s发生了负溢出。

2.14 补码的非

对满足TMin_\omega\leqslant x\leqslant TMax_\omega的任意x，其补码的非-_\omega^tx由下式给出：
-_\omega^tx= \left\{ \begin{aligned} &TMin_\omega,&&x=TMin_\omega \\ &-x,&&x>TMin_\omega \end{aligned} \right.

2.15 无符号乘法

对满足0\leqslant x,y\leqslant UMax_\omega的x和y有：
x*_\omega^uy=(x\cdot y)\bmod 2^\omega

2.16 补码乘法

对满足-2^{\omega -1}\leqslant x,y\leqslant2^{\omega-1}-1的整数x和y有：
x*_\omega^ty=U2T_{\omega}((x \cdot y)\bmod2^\omega)

2.17 无符号和补码乘法的位级等价性

给定长度为\omega的位向量\vec{x}和\vec{y}，用补码形式的位向量表示来定义整数x和y：x=B2T_\omega(\vec{x}),y=B2T_\omega(\vec{y})。用无符号形式的位向量表示来定义非负整数x'和y'：x'=B2U_\omega(\vec{x}),y'=B2U_\omega(\vec{y})。则
T2B_\omega(x*_\omega^ty)=U2B(x'*_\omega^uy')

2.18 乘以2的幂

设x为位模式[x_{\omega-1},x_{\omega-2},\cdots,x_0]表示的无符号整数。那么，对于任何k\geqslant0，我们都认为[x_{\omega-1},x_{\omega-2},\cdots,x_0,\underbrace{0,\cdots,0}_{k个0}]给出了x2^k的\omega+k位的无符号表示。

2.19 与2的幂相乘的无符号乘法

C变量x和k有无符号数值x和k，且0\leqslant k<\omega，则C表达式x<<k产生数值x*_\omega^u 2^k

2.20 与2的幂相乘的补码乘法

C变量x和k有补码值x和无符号数值k，且0\leqslant k<\omega，则C表达式x<<k产生数值x*_\omega^t 2^k

2.21 除以2的幂的无符号除法

C变量x和k有无符号数值x和k，且0\leqslant k<\omega，则C表达式x>>k产生数值\lfloor x/2^k\rfloor

2.22 除以2的幂的补码除法，向下舍入

C变量x和k有补码值x和无符号数值k，且0\leqslant k<\omega，当执行算术移位时，C表达式x>>k产生数值\lfloor x/2^k\rfloor

2.23 除以2的幂的补码除法，向上舍入

C变量x和k有补码值x和无符号数值k，且0\leqslant k<\omega，当执行算术移位时，C表达式(x+(1<<k)-1)>>k产生数值\lfloor x/2^k\rfloor

2.24 IEEE754标准表示浮点数

IEEE标准采用V=(-1)^s\times M\times 2^E的形式来表示一个数：

• 符号 s决定一个数是负数(s=1)还是正数(s=0)，数值0作为特殊情况处理。
• 尾数 M是一个二进制小数，规格化的取值范围为1\sim 2-\varepsilon，非规格化的取值范围为0\sim 1-\varepsilon
• 阶码 E的作用是对浮点数加权，权重为2^E（E可能为负数）

将浮点数的位表示划分为三个字段，分别对上述值编码:

• 符号 一个单独的符号位s来编码符号s
• 尾数 n位小数字段frac=f_{n-1}\cdots f_{1}f_{0}编码尾数M，编码出来的值依赖于阶码E是否为0
• 阶码 k位的阶码字段exp=e_{k-1}\cdots e_{1}e_{0}编码阶码E。

浮点数的表示和偏置值Bias=2^{k-1}-1密切相关。令e=B2U_k(exp)，f={0.f_{n-1}\cdots f_{1}f_{0}}_{(2)}=B2U_n(frac)\cdot 2^{-n}

• 规格化的值
  当e\neq 0且e\neq 1时，阶码E=e-Bias，尾数M=1+f

• 非规格化的值
  当e=0时，阶码E=1-Bias，尾数M=f

• 特殊值
  当e=1时浮点数的值为特殊值。

  • 当f=0时该浮点数表示无穷，根据符号位s确定是正无穷还是负无穷。
  • 当f\neq 0时该浮点数的值为NaN，意为Not a Number的缩写。