深入理解计算机系统第二版家庭作业答案Word文档格式.docx
《深入理解计算机系统第二版家庭作业答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《深入理解计算机系统第二版家庭作业答案Word文档格式.docx（117页珍藏版）》请在冰点文库上搜索。
这个可以利用取反加1来实现，不过这里的加1是加1<
（w-k-1）。
如果x的第w-k-1位为0，取反加1后，前面位全为0，如果为1，取反加1后就全是1。
最后再使用相应的掩码得到结果。
对于srl，注意工作就是将前面的高位清0，即xsra&
（1<
（w-k）-1）。
额外注意k==0时，不能使用1<
（w-k），于是改用2<
sra（int
k）{
xsrl=
（unsigned）
x
k;
w=
sizeof（int）<
3;
unsignedz=
1
（w-k-1）;
unsignedmask=z
-
unsignedright=mask
xsrl;
unsignedleft=
~mask
（~（z&
xsrl）
+
z）;
left
right;
srl（unsignedx,
xsra=
（int）
sizeof（int）*8;
2
（z
xsra;
2.64
any_even_one（unsignedx）{
!
（0x55555555））;
2.65
even_ones（unsignedx）{
^=
（x>
16）;
8）;
4）;
2）;
1）;
}
x的每个位进行异或，如果为0就说明是偶数个1，如果为1就是奇数个1。
那么可以想到折半缩小规模。
最后一句也可以是return（x^1）&
1
2.66
根据提示想到利用或运算，将最高位的1或到比它低的每一位上，忽然想如果x就是10000000..该如何让每一位都为1。
于是便想到了二进扩展。
先是x右移1位再和原x进行或，变成1100000...，再让结果右移2位和原结果或，变成11110000...，最后到16位，变成11111111...。
leftmost_one（unsignedx）{
|=
x^（x>
2.67
A.32位机器上没有定义移位32次。
B.beyond_msb变为2<
31。
C.定义a=1<
15;
a<
=15;
set_msb=a<
beyond_msb=a<
2;
2.68
感觉中文版有点问题，注释和函数有点对应不上，于是用英文版的了。
个人猜想应该是让x的最低n位变1。
lower_one_mask（int
n）{
（2<
（n-1））
2.69
rotate_right（unsignedx,
sizeof（unsigned）*8;
n）
（x<
（w-n-1）<
2.70
这一题是看x的值是否在-2^（n-1）到2^（n-1）-1之间。
如果x满足这个条件，则其第n-1位就是符号位。
如果该位为0，则前面的w-n位均为0，如果该位为1，则前面的w-n位均为1。
所以本质是判断，x的高w-n+1位是否为0或者为-1。
fits_bits（int
=
（n-1）;
||
（~x）;
2.71
A.得到的结果是unsigned，而并非扩展为signed的结果。
B.使用int，将待抽取字节左移到最高字节，再右移到最低字节即可。
xbyte（unsignedword,
bytenum）{
ret=word
（（3
bytenum）<
3）;
ret
24;
2.72
A.size_t是无符号整数，因此左边都会先转换为无符号整数，它肯定是大于等于0的。
B.判断条件改为if（maxbytes>
0&
maxbytes>
=sizeof（val））
2.73
请先参考2.74题。
可知：
t=a+b时，如果a，b异号（或者存在0），则肯定不会溢出。
如果a，b均大于等于0，则t<
0就是正溢出，如果a，b均小于0，则t>
=0就是负溢出。
于是，可以利用三个变量来表示是正溢出，负溢出还是无溢出。
saturating_add（int
y）{
sizeof（int）<
3;
t=x
y;
ans=x
x>
=（w-1）;
y>
t>
pos_ovf=
~x&
~y&
t;
neg_ovf=x&
y&
~t;
novf=
~（pos_ovf|neg_ovf）;
（pos_ovf&
INT_MAX）
（novf&
ans）
（neg_ovf&
INT_MIN）;
2.74
对于有符号整数相减，溢出的规则可以总结为：
t=a-b;
如果a,b同号，则肯定不会溢出。
如果a>
=0&
b<
0，则只有当t<
=0时才算溢出。
如果a<
0&
b>
=0，则只有当t>
不过，上述t肯定不会等于0，因为当a，b不同号时：
1）a!
=b，因此a-b不会等于0。
2）a-b<
=abs（a）+abs（b）<
=abs（TMax）+abs（TMin）=（2^w-1）
所以，a，b异号，t，b同号即可判定为溢出。
tsub_ovf（int
=y）&
（y==t）;
顺便整理一下汇编中CF，OF的设定规则（个人总结，如有不对之处，欢迎指正）。
t=a+b;
CF:
（unsignedt）<
（unsigneda）进位标志
OF:
（a<
0==b<
0）&
（t<
0!
=a<
0）
t=a-b;
=0）||（（a<
t<
0）退位标志
=b<
（b<
0==t<
汇编中，无符号和有符号运算对条件码（标志位）的设定应该是相同的，但是对于无符号比较和有符号比较，其返回值是根据不同的标志位进行的。
详情可以参考第三章3.6.2节。
2.75
根据2-18，不难推导，（x'
*y'
）_h=（x*y）_h+x（w-1）*y+y（w-1）*x。
unsigned_high_prod（unsignedx,
unsignedy）{
signed_high_prod（x,
y）
（w-1））*y
x*（y>
（w-1））;
当然，这里用了乘法，不属于整数位级编码规则，聪明的办法是使用int进行移位，并使用与运算。
即（（int）x>
（w-1））&
y和（（int）y>
x。
注：
不使用longlong来实现signed_high_prod（intx,inty）是一件比较复杂的工作，而且我不会只使用整数位级编码规则来实现，因为需要使用循环和条件判断。
下面的代码是计算两个整数相乘得到的高位和低位。
uadd_ok（unsignedx,
y
=x;
void
signed_prod_result（int
y,
h,
l）{
h=
0;
l=
（y&
1）?
x:
for（int
i=1;
i<
w;
i++）{
if（
（y>
i）&
）
h
+=
（unsigned）x>
（w-i）;
if（!
uadd_ok（l,
x<
i））
h++;
l
i）;
h=h
（（x>
（w-1））*y）
（（y>
（w-1））*x）;
最后一步计算之前的h即为unsigned相乘得到的高位。
sign_h=unsign_h-（（x>
y）-（（y>
x）;
sign_h=unsign_h+（（x>
（w-1））*y）+（（y>
（w-1））*x）;
2.76
A.K=5:
（x<
2）+x
B.K=9:
3）+x
C.K=30:
5）-（x<
1）
D.K=-56:
3）-（x<
6）
2.77
先计算x>
k，再考虑舍入。
舍入的条件是x<
0&
x的最后k位不为0。
divide_power2（int
ans=x>
ans
（w-1））
（（1<
k）-1））;
ans;
2.78
这相当于计算（（x<
2）+x）>
3，当然，需要考虑x为负数时的舍入。
先看上述表达式，假设x的位模式为[b（w-1）,b（w-2）,...,b（0）]，那么我们需要计算：
[b（w-1）,b（w-2）,b（w-3）,
...
b（0）,
0,
0]
+
[b（w-1）,b（w-2）,...,b
（2）,
b
（1）,b（0）]
最后需要右移3位。
因此我们可以忽略下方的b
（1）,b（0）。
于是就计算（x>
2）+x，再右移一位即是所求答案。
不过考虑到（x>
2）+x可能也会溢出，于是就计算（x>
3）+（x>
1），这个显然是不会溢出的。
再看看b（0）+b
（2）会不会产生进位，如果产生进位，则再加一。
最后考虑负数的舍入。
负数向0舍入的条件是x<
（（x<
2）+x的后三位不全为0）。
满足舍入条件的话，结果再加1。
容易证明，加法后三位不全为0可以等价为x后三位不全为0。
mul5div8（int
x）{
b0=x&
1,
b2=
2）&
ans=
3）
（b0&
b2）;
7））;
2.79
不懂题意，感觉就是2.78。
2.80
A.1[w-n]0[n]:
~（（1<
n）-1）
B.0[w-n-m]1[n]0[m]:
（（1<
n）-1）<
m
2.81
A.false，当x=0,y=TMin时，x>
y，而-y依然是Tmin，所以-x>
-y。
B.true，补码的加减乘和顺序无关（如果是右移，则可能不同）。
C.false，当x=-1,y=1时，~x+~y=0xFFFFFFFE，而~（x+y）==0xFFFFFFFF。
D.true，无符号和有符号数的位级表示是相同的。
E.true，最后一个bit清0，对于偶数是不变的，对于奇数相当于-1，而TMin是偶数，因此该减法不存在溢出情况。
所以左边总是<
=x。
2.82
A.令x为无穷序列表示的值，可以得到x*2^k=Y+x。
所以x=Y/（2^k-1）。
B.（a）1/7,（b）9/15=3/5,（c）7/63=1/9
2.83
浮点数的一个特点就是，如果大于0，则可以按unsigned位表示的大小排序。
如果小于0则相反。
注意都为0的情况即可。
所以条件是：
（（ux<
1）==0&
（uy<
1）==0）||
（!
sx&
sy）||
!
sy&
ux>
=uy）||
（sx&
sy&
ux<
=uy）;
2.84
A.5.0，5表示为101，因此位数M就是1.01为1.25，小数f为0.01=0.25。
指数部分应该为E=2，所以其指数部分位表示为e=（2^（k-1）-1）+2=2^（k-1）+1。
位表示三个部分分别是s-e-f，为0-10..01-0100..0。
B.能被准确描述的最大奇数，那么其M=1.111..1，故f部分全为1，E应该为n。
当然，这个假设在2^（k-1）>
=n的情况下才能成立。
这时，s=0,e=n+2^（k-1）-1,f=11...1。
值为2^（n+1）-1。
C.最小的规格化数为2^（1-bias）即2^（-2^（k-1）+2），所以其倒数值V为2^（2^（k-1）-2），所以M为1.00000，f部分为全0，E=2^（k-1）-2，e部分为2^（k-1）-2+bias=2^k-3，即为11..101。
位表示为0-11..101-00..0。
2.85
描述
扩展精度
值
十进制
最小的正非规格化数
2^（-63）*2^（-2^14+2）
3.6452e-4951
最小的正规格化数
2^（-2^14+2）
3.3621e-4932
最大的规格化数
（2^64-1）*2^（2^14-1-63）
1.1897e+4932
2.86
Hex
M
E
V
-0
0x8000
-62
--
最小的值>
0x3F01
257/256
257*2^（-8）
256
0x4700
8
最大的非规格化数
0x00FF
255/256
255*2^（-70）
-inf
0xFF00
Hex为0x3AA0
0x3AA0
416/256
-5
416*2^（-13）=13*2^（-8）
2.87
格式A
格式B
位
101110001
-9/16
101100010
010110101
208
011101010
100111110
-7/1024
100000111
000000101
6/2^17
000000000
111011000
-4096
111110000
011000100
768
011110000
inf
没有特别明白转换成最接近的，然后又说向+inf舍入的含义。
按理说，舍入到+inf就是向上舍入，而并不是找到最接近的。
表格中是按最接近的进行舍入，并且如果超出范围则认为是inf。
如果都按+inf进行舍入，那么第四行格式B将是000000001。
2.88
A.false，float只能精确表示最高位1和最低位的1的位数之差小于24的整数。
所以当x==TMAX时，用float就无法精确表示，但double是可以精确表示所有32位整数的。
B.false，当x+y越界时，左边不会越界，而右边会越界。
C.true，double可以精确表示所有正负2^53以内的所有整数。
所以三个数相加可以精确表示。
D.false，double无法精确表示2^64以内所有的数，所以该表达式很有可能不会相等。
虽然举例子会比较复杂，但可以考虑比较大的值。
E.false，0/0.0为NaN，（非0）/0.0为正负inf。
同号inf相减为NaN，异号inf相减也为被减数的inf。
2.89
float的k=8,n=23。
bias=2^7-1=127。
最小的正非规格化数为2^（1-bias-n）=2^-149。
最小的规格化数为2^（0-bias）*2=2^-126。
最大的规格化数（二的幂）为2^（2^8-2-bias）=2^127。
因此按各种情况把区间分为[TMin,-148][-149,-125][-126,127][128,TMax]。
float
fpwr2（int
x）
/*Resultexponentandfraction*/
unsignedexp,
frac;
unsignedu;
if
-149）
/*Toosmall.Return0.0*/
exp=
frac=
else
-126）
/*Denormalizedresult*/
1<
（x+149）;
128）
/*Normalizedresult.*/
exp=x
127;
/*Toobig.Return+oo*/
255;
/*Packexpandfracinto32bits*/
u=exp
23
/*Returnasfloat*/
u2f（u）;
2.90
A.pi的二进制数表示为：
01000000010010010000111111101011，E=128-127=1，
它表示的二进制小数值为：
11.0010010000111111101011
B.根据2.82，可知1/7的表示为0.001001[001]...，
所以22/7为11.001001001001001[001]...
C.从第9位开始不同。
为了方便测试2.91-2.94，我写了几个公共函数。
typedefunsignedfloat_bits;
u2f（unsignedx）{
*（（float*）&
x）;
f2u（float
f）{
*（（unsigned*）&
f）;
bool
is_float_equal（float_bitsf1,
f2）{
f2u（f2）
==f1;
is_nan（float_bitsfb）{
unsignedsign=fb>
31;
unsignedexp=
（fb>
23）
0xFF;
unsignedfrac=fb&
0x7FFFFF;
exp==
0xFF
frac
is_inf（float_bitsfb）{
frac==
testFun（
float_bits（*fun1）（float_bits）,
float（*fun2）（float））{
unsignedx=
do{
//testforall2^32value
float_bitsfb=
fun1（x）;
ff=
fun2（u2f（x））;
is_float_equal（fb,
ff））{
printf（"
%xerror\n"
x++;
}while（x!
=0）;
printf（"
TestOK\n"
）;
升级会员 