深入理解计算机系统第二版家庭作业答案.docx
《深入理解计算机系统第二版家庭作业答案.docx》由会员分享,可在线阅读,更多相关《深入理解计算机系统第二版家庭作业答案.docx(117页珍藏版)》请在冰点文库上搜索。
深入理解计算机系统第二版家庭作业答案
深入理解计算机系统(第二版)家庭作业第二章
深入理解计算机系统二进制
2.55-2.57
略
2.58
int is_little_endian(){
int a= 1;
return *((char*)&a);
}
2.59
(x&0xFF)|(y&~0xFF)
2.60
unsigned replace_byte(unsigned x, unsigned char b, int i)
{
return (x & ~(0xFF<<(i<<3))) | (b << (i<<3));
}
2.61
A.!
~x
B.!
x
C.!
~(x>>((sizeof(int)-1)<<3))
D.!
(x&0xFF)
注意,英文版中C是最低字节,D是最高字节。
中文版恰好反过来了。
这里是按中文版来做的。
2.62
这里我感觉应该是英文版对的,int_shifts_are_arithmetic()
int int_shifts_are_arithmetic(){
int x= -1;
return (x>>1) == -1;
}
2.63
对于sra,主要的工作是将xrsl的第w-k-1位扩展到前面的高位。
这个可以利用取反加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<<(w-k-1)。
int sra(int x, int k){
int xsrl= (unsigned) x >> k;
int w= sizeof(int)<<3;
unsignedz= 1 << (w-k-1);
unsignedmask=z - 1;
unsignedright=mask & xsrl;
unsignedleft= ~mask & (~(z&xsrl) + z);
return left | right;
}
int srl(unsignedx, int k){
int xsra= (int) x >> k;
int w= sizeof(int)*8;
unsignedz= 2 << (w-k-1);
return (z - 1) & xsra;
}
2.64
int any_even_one(unsignedx){
return !
!
(x & (0x55555555));
}
2.65
int even_ones(unsignedx){
x ^= (x>> 16);
x ^= (x>> 8);
x ^= (x>> 4);
x ^= (x>> 2);
x ^= (x>> 1);
return !
(x&1);
}
x的每个位进行异或,如果为0就说明是偶数个1,如果为1就是奇数个1。
那么可以想到折半缩小规模。
最后一句也可以是return(x^1)&1
2.66
根据提示想到利用或运算,将最高位的1或到比它低的每一位上,忽然想如果x就是10000000..该如何让每一位都为1。
于是便想到了二进扩展。
先是x右移1位再和原x进行或,变成1100000...,再让结果右移2位和原结果或,变成11110000...,最后到16位,变成11111111...。
int leftmost_one(unsignedx){
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return x^(x>>1);
}
2.67
A.32位机器上没有定义移位32次。
B.beyond_msb变为2<<31。
C.定义a=1<<15;a<<=15;set_msb=a<<1;beyond_msb=a<<2;
2.68
感觉中文版有点问题,注释和函数有点对应不上,于是用英文版的了。
个人猜想应该是让x的最低n位变1。
int lower_one_mask(int n){
return (2<<(n-1)) - 1;
}
2.69
unsigned rotate_right(unsignedx, int n){
int w= sizeof(unsigned)*8;
return (x>>n) | (x<<(w-n-1)<<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。
int fits_bits(int x, int n){
x >>= (n-1);
return !
x || !
(~x);
}
2.71
A.得到的结果是unsigned,而并非扩展为signed的结果。
B.使用int,将待抽取字节左移到最高字节,再右移到最低字节即可。
int xbyte(unsignedword, int bytenum){
int ret=word << ((3 - bytenum)<<3);
return 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就是负溢出。
于是,可以利用三个变量来表示是正溢出,负溢出还是无溢出。
int saturating_add(int x, int y){
int w= sizeof(int)<<3;
int t=x + y;
int ans=x + y;
x>>=(w-1);
y>>=(w-1);
t>>=(w-1);
int pos_ovf= ~x&~y&t;
int neg_ovf=x&y&~t;
int novf= ~(pos_ovf|neg_ovf);
return (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>=0时才算溢出。
不过,上述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同号即可判定为溢出。
int tsub_ovf(int x, int y){
int w= sizeof(int)<<3;
int t=x - y;
x>>=(w-1);
y>>=(w-1);
t>>=(w-1);
return (x !
=y)&&(y==t);
}
顺便整理一下汇编中CF,OF的设定规则(个人总结,如有不对之处,欢迎指正)。
t=a+b;
CF:
(unsignedt)<(unsigneda)进位标志
OF:
(a<0==b<0)&&(t<0!
=a<0)
t=a-b;
CF:
(a<0&&b>=0)||((a<0==b<0)&&t<0)退位标志
OF:
(a<0!
=b<0)&&(b<0==t<0)
汇编中,无符号和有符号运算对条件码(标志位)的设定应该是相同的,但是对于无符号比较和有符号比较,其返回值是根据不同的标志位进行的。
详情可以参考第三章3.6.2节。
2.75
根据2-18,不难推导,(x'*y')_h=(x*y)_h+x(w-1)*y+y(w-1)*x。
unsigned unsigned_high_prod(unsignedx, unsignedy){
int w= sizeof(int)<<3;
return signed_high_prod(x, y) + (x>>(w-1))*y + x*(y>>(w-1));
}
当然,这里用了乘法,不属于整数位级编码规则,聪明的办法是使用int进行移位,并使用与运算。
即((int)x>>(w-1))&y和((int)y>>(w-1))&x。
注:
不使用longlong来实现signed_high_prod(intx,inty)是一件比较复杂的工作,而且我不会只使用整数位级编码规则来实现,因为需要使用循环和条件判断。
下面的代码是计算两个整数相乘得到的高位和低位。
int uadd_ok(unsignedx, unsignedy){
return x + y >=x;
}
void signed_prod_result(int x, int y, int &h, int &l){
int w= sizeof(int)<<3;
h= 0;
l= (y&1)?
x:
0;
for(int i=1; i if( (y>>i)&1 ) {
h += (unsigned)x>>(w-i);
if(!
uadd_ok(l, x<
l += (x<
}
}
h=h + ((x>>(w-1))*y) + ((y>>(w-1))*x);
}
最后一步计算之前的h即为unsigned相乘得到的高位。
sign_h=unsign_h-((x>>(w-1))&y)-((y>>(w-1))&x);
sign_h=unsign_h+((x>>(w-1))*y)+((y>>(w-1))*x);
2.76
A.K=5:
(x<<2)+x
B.K=9:
(x<<3)+x
C.K=30:
(x<<5)-(x<<1)
D.K=-56:
(x<<3)-(x<<6)
2.77
先计算x>>k,再考虑舍入。
舍入的条件是x<0&&x的最后k位不为0。
int divide_power2(int x, int k){
int ans=x>>k;
int w= sizeof(int)<<3;
ans += (x>>(w-1)) && (x&((1< return 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<0&&((x<<2)+x的后三位不全为0)。
满足舍入条件的话,结果再加1。
容易证明,加法后三位不全为0可以等价为x后三位不全为0。
int mul5div8(int x){
int b0=x&1, b2= (x>>2)&1;
int ans= (x>>3) + (x>>1);
int w= sizeof(int)<<3;
ans += (b0&b2);
ans += ((x>>(w-1)) && (x&7));
return ans;
}
2.79
不懂题意,感觉就是2.78。
2.80
A.1[w-n]0[n]:
~((1<B.0[w-n-m]1[n]0[m]:
((1<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)||
(!
sx&&!
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
0
-62
--
最小的值>1
0x3F01
257/256
0
257*2^(-8)
256
0x4700
1
8
--
最大的非规格化数
0x00FF
255/256
-62
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
-9/16
010110101
208
011101010
208
100111110
-7/1024
100000111
-7/1024
000000101
6/2^17
000000000
0
111011000
-4096
111110000
-inf
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 (x <-149) {
/*Toosmall.Return0.0*/
exp= 0;
frac= 0;
} else if (x < -126) {
/*Denormalizedresult*/
exp= 0;
frac= 1<<(x+149);
} else if (x < 128) {
/*Normalizedresult.*/
exp=x + 127;
frac= 0;
} else {
/*Toobig.Return+oo*/
exp= 255;
frac= 0;
}
/*Packexpandfracinto32bits*/
u=exp << 23 | frac;
/*Returnasfloat*/
return 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;
float u2f(unsignedx){
return *((float*)&x);
}
unsigned f2u(float f){
return *((unsigned*)&f);
}
bool is_float_equal(float_bitsf1, float f2){
return f2u(f2) ==f1;
}
bool is_nan(float_bitsfb){
unsignedsign=fb>>31;
unsignedexp= (fb>>23) & 0xFF;
unsignedfrac=fb&0x7FFFFF;
return exp== 0xFF && frac !
= 0;
}
bool is_inf(float_bitsfb){
unsignedsign=fb>>31;
unsignedexp= (fb>>23) & 0xFF;
unsignedfrac=fb&0x7FFFFF;
return exp== 0xFF && frac== 0;
}
int testFun( float_bits(*fun1)(float_bits), float(*fun2)(float)){
unsignedx= 0;
do{ //testforall2^32value
float_bitsfb= fun1(x);
float ff= fun2(u2f(x));
if(!
is_float_equal(fb, ff)){
printf("%xerror\n", x);
return 0;
}
x++;
}while(x!
=0);
printf("TestOK\n");
return 1;
}