【深入理解计算机系统-第二版】第二章部分家庭作业(Homework)参考答案

原文链接:http://www.cnblogs.com/XjChenny/archive/2013/03/18/2966414.html

这几天一直在写《深入理解计算机系统》第二版中第二章的家庭作业,费了几天的时间,终于完成了。当初碰到若干题不会,在网上也没有搜索到答案。现在,我把这份自己完成的答案分享上来,与大家交流思想。其中错误一定会存在,如果有错误,希望指出来,共同进步。

2.67

A:左移位数大于等于int长度。

B:可以考虑用两次左移来实现<<32:

int set_msb=1<<31;

int beyond_msb=set_msb<<1;

C:可以考虑用三次左移来实现<<31与<<32:

int temp=1<<15;

temp<<=15;

int set_msb=temp<<1;

int beyond_msb=temp<<2;

 

2.68

Q:Clear all but least significant n bits of x,即保留x的低n位,1<=n<=w

A:可以参考2.66的提示。生成低n位全为1,其余位全为0的掩码,通常想到的是

(1<<n)-1

但是n==w的时候就会出错,左移的位数等于int长度(见2.67A),这时我们可以采用两次左移来实现:先生成低n-1位全为1,其余位全为0的掩码m,然后让m左移1位,然后加1即可,手工检验n==1时此情形仍满足,故最后的掩码为{[1<<(n-1)-1]<<1+1},此掩码与x相与即可:

int lower_bits(int x, int n)

{

       return ((1<<(n-1)-1)<<1+1)&x;

}

2.69

Q::Do rotating right shift. Assume 0<=n<w

A:实际上相当于将x循环右移n位。我们先取x的低n位,要特别注意n==0的情形,参照2.68,使用((1<<n)-1)&x来取得x的低n位,之所以不采用2.68最终答案所示的方法的原因是n可以取到0,但是取不到w,而2.68中,n取不到0,而能取到w。

然后我们将x的高(w-n)位右移n位,在题目假设(P154页)中,右移操作是算数右移,高n位扩展了x的符号位,而我们需要的是逻辑右移。逻辑右移的解法如2.63中所示:

unsigned srl(unsigned x, int k)

{

       unsigned xsra = (int) x>>k;

       return ((1<<(w-k-1)-1)<<1+1)^xsra;

}

同时需要注意n为0的情形,处理该情形的方法如2.68所述。将x的低n位左移w-n位,异或上slr(x,n)即可:

((((1<<n)-1)&x)<<(w-n-1)<<1)^slr(x,n)

在上式中,同样要注意k=0的情形。

 

2.70

Q:Return 1 when x can be represented as an n-bit, 2’s complement number; 0 otherwise. 1<=n<=w.

A:对于w位的二进制补码数x,它能不能表示成n位的二进制补码数需要看它的最高w-n+1位是不是全0(正数)或者全1(负数)。这是由于:

我们考虑一个n-bit的二进制补码数a,最高位(第n-1位)是符号位。对于正数,有a[n-1]=0,将其扩展为w-bit时,第n-1位及其左边的w-n位都为0。这个条件是充分必要的,我们可以反证出,如果前面最高的w-n+1位中(除了最高位),某一位有1,则一定不能用n-bit的二进制补码数表示出。

而对于负数,有a[n-1]=1,将其扩展为w-bit时,第n-1位及其左边的w-n位都为1。这个条件同样是充分必要的,在此不再进行说明。

由此我们可以得到解法:(1)用掩码屏蔽掉x的高w-n位,即取得00…x[n-1]x[n-2]…x[0]。(2)然后将x[n-1]扩展到最高的w-n位中,得到x’=x[n-1]x[n-1]…x[n-1]x[n-2]…x[0]。(3)最后return x’==x即可。

步骤:

(1)y= (~((~0)<<n-1<<1))&x(分两次左移,为了处理n==w的情形)

(2)z=y>>n-1,z[0]是符号位,z==1为负,z==0为正就是符号位。

x’=((0-z)&(~0<<n-1<<1))|y

(3)return x’==x

 

2.71

A:packed_t是无符号数,而它包装的4个字节都是有符号数,1byte的包装在无符号数中的有符号数扩展后符号位并没有扩展。例如,1byte的0xFF表示-1,而扩展成32位后应该为0xFFFFFFFF。而按照原函数中所示,扩展后结果是0x000000FF。

B:其实这个题可以将unsigned转换成signed,然后利用算数右移来取得高位符号位的扩展。但是我们有另外一个解法:

unsigned x=word>>(bytenum<<3);

x<<=24;

x>>=24;

unsigned y=x>>7;

y<<=8;

return x-y;

这个解法不理解的话,自己动手找个示例画一画就理解其中的原理了。

2.72

A:sizeof返回size_t,实际上是无符号整型,而maxbytes-sizeof(val)则会隐式装换为无符号数减法,所的结果始终是正数。测试条件>=0始终成立。

B:maxbytes>=0&&maxbytes>=sizeof(val)

 

2.73

编写一个函数,当正溢出时,将结果设为Tmax,当负溢出时,将结果设置为Tmin。

首先,我们需要判断是否发生了溢出:x、y同号,而与x+y异号时则发生了溢出:即(1)=((x^(x+y))&(y^(x+y))>>(w-1)。经过这个式子处理,发生溢出时,(1)式结果为1111….111,未发生溢出时,(1)式结果为0000….000。

然后,我们判断发生的溢出是正溢出还是负溢出:即

(2)=(1)&(x>>(w-1)),正溢出时,(2)为0000…000;负溢出时,(2)为11111…111。

未发生溢出时,结果为x+y,而发生溢出时,(x+y)这部分结果需要屏蔽掉,代之以相应的Tmax或者Tmin。故最终的结果包含了(x+y)|(1)。当x+y没有发生溢出时,这部分结果为x+y,而发生溢出时,这部分结果为1111…111。而当正溢出时,我们需要的结果是0111…111,负溢出时,我们需要的结果是1000…000,即我们需要在(x+y)|(1)的基础上减去相应的值:

当未发生溢出时,减去0

当正溢出时,减去1000…000

当负溢出时,减去0111…111

综上所述,我们可以得到需要减去的那部分的值的表达式:

(1)&((1<<(w-1))^(2))。故最终的结果为:

(x+y)|(1)- (1)&((1<<(w-1))^(2)),其中(1)、(2)的表达式如上述分析中所示。

2.74

这道题是测试减法是否发生了溢出。如果我们一下子不好考虑的话,先分析在减法中哪些情况会发生溢出。设x-y=z,

当x>0,y<0,z<=0时会发生溢出;

当x<0,y>0,z>=0时会发生溢出。

即x、y异号,并且x与z异号时会发生溢出。特别注意z=0的情形。

最后的答案可以写为:

return (x^y!=0)&&(z==0||x^z!=0)

 

2.75

设两个bit串的signed表示为x’、y’,unsigned表示为x,y。根据本章所学,有x’=x+x[w-1]*2w,y’=y+y[w-1]*2w

x’*y’ = (( x+x[w-1]*2w) * (y+y[w-1]*2w) mod 2w

       =(x*y+(y*x[w-1]+x*y[w-1])*2w+x[w-1]*y[w-1]*2w) mod 2w

注意上式,(x*y)的高w位在(x*y)中计算出,x’*y’相对于x*y高w位所多出的数是y*x[w-1]+x*y[w-1]。故经过unsigned_high_prod计算出的结果,需要加上x(当y为负时),与y(当x为负时),就是signed_high_prod的结果。

 

2.76

A:a<<2+a

B:a<<3+a

C:a<<5-a<<1

D:a<<3-a<<6

 

2.77

书中P130页有原理叙述。对于本题,我们首先需要判断x是正数还是负数:

int a=x>>w-1;

a==111….111则为负数,a==000….000则为正数。正数时不用额外考虑,而负数时需要加上一个bias偏差来向0舍入:

int result=((y-1)&a+x)/y,y=1<<k,带入之后即可得到最终答案。

2.78

5*x/8:

x<<2+x得到5*x,而除以8的操作需要利用2.77题的结果,最终结果是: return divide_power(x<<2+x,3)。

 

2.79

这道题与2.78的唯一区别是计算5x/8时不能发生溢出。因为5x/8=x/2+x/8。当x为负数时,我们需要求得5x/8向上舍入的结果,在博客上我们使用celling(x)来表示x向上舍入的正数。我们可以通过对几个x的取值进行验证,得到如下关系:

celling(5x/8)=celling(x/2)+celling(x/8)+1,当x=-5-8k或-7-8k,k=0,1,2…

celling(5x/8)=celling(x/2)+celling(x/8),其他情况。

       由2.77可以得到:

celling(x/2)=divide_power2(x,1)

celling(x/8)=divide_power2(x,3)

下面判断x=-5-8k或者x=-7-8k。负值不好判断,而正值比较好判断,即:-x=5+8k,后3位为101。而-x=-7+8k,后三位为111。

故我们可以得到,

celling(5x/8)= celling(x/2)+celling(x/8)+(-x&0x5||-x&0x7)&0x1。

而当x为正数时,我们也需要经过相似的判断,经过计算,可以知道当x=5+8k或x=7+8k时,同样需要多加一个1。

故而,最后总的式子为:

celling(5x/8)= celling(x/2)+celling(x/8)+(-x&0x5||-x&0x7||x&0x5||x&0x7)&0x1

2.80

A:~((1<<n)-1),注意此时0<n<w。

B:(1<<(n+m)-1)-(1<<m-1)=1<<(n+m)-1<<m。

 

2.81

A:错误,考虑x=0,y=1<<31,x>y,而-x>-y。

B:正确。数学中常用的分配律、结合律即可证明,<<5即乘以32。

C:错误。~x+~y=(-x-1)+(-y-1)=-(x+y)-2,不等于-(x+y)-1

D:正确的。signed与unsigned的加法计算在本质上是一致的。

E:正确。右移会向小值舍入。

 

2.82

A:我们要求出那个无穷循环的串的数学公式表示。令其为V,则有

V<<k=V+Y(高等数学知识)

       则V=Y/(2k-1)

B:(a) 1/7 (b) 0.6 (c) 1/9

 

2.83

浮点数最高位为符号位。先处理-0、+0比较的情况:

ux<<1==0&&uy<<1==0

x为正,y为正:

sx==0&&sy==0&&ux>=uy

x为负,y为负:

sx==1&&sy==1&&ux<=uy

x为正,y为负:

!sx&&sy

以上式子使用||连接起来就是最终答案。

 

2.84

A:f=0.01,M=1.01,E=2。注意到E=2而原始的exp-bias=E,exp=1+2k-1

B:f=0.11…1,M=1.11…1。而注意要精确表示最大的奇数。f的最后一个1一定要保留,所以E最大为n。此时,原始的exp=n+2k-1-1。

C:最小的正normalized值的表示为

2^(2-2k-1)。要求它的倒数,则指数部分应该是2^(2k-1-2),以使得乘积为1。而数值部分,则为0。

 

2.91

unsigned sign=f>>31;

unsigned exp=f>>23&0xFF;

unsigned frac=f&0x7FFFFF;

if(!(exp^0xFF==0&&frac!=0)) f|=1<<31;

return f;

 

2.92

unsigned sign=f>>31;

unsigned exp=f>>23&0xFF;

unsigned frac=f&0x7FFFFF;

if(!(exp^0xFF==0&&frac!=0)) f+=1<<31;

return f;

 

2.93

unsigned sign=f>>31;

unsigned exp=f>>23&0xFF;

unsigned frac=f&0x7FFFFF;

 

if(exp^0xFF==0&&frac!=0) return f;

else if(exp>0) exp=exp-1;

else {

       //round to even

       if(frac&0x1!=0&&(frac>>1)&0x1==1)

              frac=frac>>1+1;

       else frac=frac>>1;

}

return (sign<<31)|(exp<<23)|frac;

 

2.94

unsigned sign=f>>31;

unsigned exp=f>>23&0xFF;

unsigned frac=f&0x7FFFFF;

 

if(exp^0xFF==0&&frac!=0) return f;

else if(exp&0xFE!=0&&exp!=0) exp=exp+1;

else if(exp==0)

{

       if(frac>>23&0x1==0) frac<<1;

       else

{    

       exp=1;

       frac<<1;

}

}

return (sign<<31)|(exp<<23)|frac;

 

2.95

i是整数,故而E部分的指数最小也为0+127=127。不包括E为0的情况。我们首先判断最高位的1在哪个位置。

//符号位

int sign=i>>31;

 

//求i的绝对值

if(!sign) i=~i+1;

 

//求数值位最高位的1所在位置

int pos=0;

if(i>>16) {pos+=16; i>>=16;}

if(i>>8) {pos+=8; i>>=8;}

if(i>>4) {pos+=4; i>>=4;}

if(i>>2) {pos+=2; i>>=2;}

if(i>>1) {pos+=1; i>>=1;}

 

exp=pos+127;

//屏蔽掉数值部分为1的最高位(第pos位),这一位在浮点数中是隐式显示表示的。

i=~(1<<pos)&i;

//第pos位要左移或者右移到第23位,使得低23位是frac部分。

if(i>>23)

{

       frac=i>>(pos-23);

       //最低(pos-23)位要看是否需要round to even,并且pos!=23

if(!(pos^0x17)&&(((1<<(pos-23)-1)&&i)^(1<<(pos-23-1)))==0))

{

       //round to even

       if(frac&0x1) frac+=1;

       //发生溢出时,需要进位

       if(frac==0) exp+=1;

}

}

else

{

       frac=i<<(23-pos);

}

return (sign<<31)|(exp<<23)|frac;

2.96

这道题还是比较繁琐,解法可类比2.95,但不再具体写代码了。在求解的时候,首先不考虑符号位,先求绝对值的表示,设这个绝对值为ret。

由于采用了round to zero的策略,故而不需要考虑“入”,只需要考虑“舍”即可。

(1)exp<0+127,ret=0

(1)exp=0+127,ret=1;

(2)exp=255,frac!=0时,ret=0x80000000

(3)exp等于其他值时,我们先把frac部分提出来,在第23位变为1,这是因为在float表示中,这个整数部分的1被隐藏了,我们求解int的时候,需要将其加上。此时,小数点在第23位的右侧。

当exp=127时,frac>>=23;

当exp=128时,frac>>=22;

……

当exp=150时,frac>>=0;

当exp=151时,frac<<=1;

当exp=152时,frac<<=2;

……

当exp=157时,frac<<=7;

之后,再左移的话,就会溢出。也即exp>157时,ret=0x80000000。

最后,如果是正数的话,直接拼装一下。而如果是负数的话,先按正数拼接,然后变反即可。不需要考虑Tmin的原因是float没有足够的精度来表示Tmin,故参数给出的f不可能被表示成Tmin。

转载于:https://www.cnblogs.com/XjChenny/archive/2013/03/18/2966414.html

上一篇:Spring框架学习(八):@Qualifier实现高级装配


下一篇:Python标准模块--argparse