深入理解计算机系统(第二版)-家庭作业答案

深入理解计算机系统(第二版)家庭作业第二章深入理解计算机系统二进制2.55-2.57略2.58intis_little_endian(){inta=1;return*((char*)&a);}2.59(x&0xFF)|(y&~0xFF)2.60unsignedreplace_byte(unsignedx,unsignedcharb,inti){return(x&~(0xFF(i3)))|(b(i3));}2.61A.!~xB.!xC.!~(x((sizeof(int)-1)3))D.!(x&0xFF)注意，英文版中C是最低字节，D是最高字节。中文版恰好反过来了。这里是按中文版来做的。2.62这里我感觉应该是英文版对的，int_shifts_are_arithmetic()intint_shifts_are_arithmetic(){intx=-1;return(x1)==-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)。intsra(intx,intk){intxsrl=(unsigned)xk;intw=sizeof(int)3;unsignedz=1(w-k-1);unsignedmask=z-1;unsignedright=mask&xsrl;unsignedleft=~mask&(~(z&xsrl)+z);returnleft|right;}intsrl(unsignedx,intk){intxsra=(int)xk;intw=sizeof(int)*8;unsignedz=2(w-k-1);return(z-1)&xsra;}2.64intany_even_one(unsignedx){return!!(x&(0x55555555));}2.65inteven_ones(unsignedx){x^=(x16);x^=(x8);x^=(x4);x^=(x2);x^=(x1);return!(x&1);}x的每个位进行异或，如果为0就说明是偶数个1，如果为1就是奇数个1。那么可以想到折半缩小规模。最后一句也可以是return(x^1)&12.66根据提示想到利用或运算，将最高位的1或到比它低的每一位上，忽然想如果x就是10000000..该如何让每一位都为1。于是便想到了二进扩展。先是x右移1位再和原x进行或，变成1100000...，再让结果右移2位和原结果或，变成11110000...，最后到16位，变成11111111...。intleftmost_one(unsignedx){x|=(x1);x|=(x2);x|=(x4);x|=(x8);x|=(x16);returnx^(x1);}2.67A.32位机器上没有定义移位32次。B.beyond_msb变为231。C.定义a=115;a=15;set_msb=a1;beyond_msb=a2;2.68感觉中文版有点问题，注释和函数有点对应不上，于是用英文版的了。个人猜想应该是让x的最低n位变1。intlower_one_mask(intn){return(2(n-1))-1;}2.69unsignedrotate_right(unsignedx,intn){intw=sizeof(unsigned)*8;return(xn)|(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。intfits_bits(intx,intn){x=(n-1);return!x||!(~x);}2.71A.得到的结果是unsigned，而并非扩展为signed的结果。B.使用int，将待抽取字节左移到最高字节，再右移到最低字节即可。intxbyte(unsignedword,intbytenum){intret=word((3-bytenum)3);returnret24;}2.72A.size_t是无符号整数，因此左边都会先转换为无符号整数，它肯定是大于等于0的。B.判断条件改为if(maxbytes0&&maxbytes=sizeof(val))2.73请先参考2.74题。可知：t=a+b时，如果a，b异号（或者存在0），则肯定不会溢出。如果a，b均大于等于0，则t0就是正溢出，如果a，b均小于0，则t=0就是负溢出。于是，可以利用三个变量来表示是正溢出，负溢出还是无溢出。intsaturating_add(intx,inty){intw=sizeof(int)3;intt=x+y;intans=x+y;x=(w-1);y=(w-1);t=(w-1);intpos_ovf=~x&~y&t;intneg_ovf=x&y&~t;intnovf=~(pos_ovf|neg_ovf);return(pos_ovf&INT_MAX)|(novf&ans)|(neg_ovf&INT_MIN);}2.74对于有符号整数相减，溢出的规则可以总结为：t=a-b;如果a,b同号，则肯定不会溢出。如果a=0&&b0，则只有当t=0时才算溢出。如果a0&&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同号即可判定为溢出。inttsub_ovf(intx,inty){intw=sizeof(int)3;intt=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:(a0==b0)&&(t0!=a0)t=a-b;CF:(a0&&b=0)||((a0==b0)&&t0)退位标志OF:(a0!=b0)&&(b0==t0)汇编中，无符号和有符号运算对条件码（标志位）的设定应该是相同的，但是对于无符号比较和有符号比较，其返回值是根据不同的标志位进行的。详情可以参考第三章3.6.2节。2.75根据2-18，不难推导，(x'*y')_h=(x*y)_h+x(w-1)*y+y(w-1)*x。unsignedunsigned_high_prod(unsignedx,unsignedy){intw=sizeof(int)3;returnsigned_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)是一件比较复杂的工作，而且我不会只使用整数位级编码规则来实现，因为需要使用循环和条件判断。下面的代码是计算两个整数相乘得到的高位和低位。intuadd_ok(unsignedx,unsignedy){returnx+y=x;}voidsigned_prod_result(intx,inty,int&h,int&l){intw=sizeof(int)3;h=0;l=(y&1)?x:0;for(inti=1;iw;i++){if((yi)&1){h+=(unsigned)x(w-i);if(!uadd_ok(l,xi))h++;l+=(xi);}}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.76A.K=5:(x2)+xB.K=9:(x3)+xC.K=30:(x5)-(x1)D.K=-56:(x3)-(x6)2.77先计算xk，再考虑舍入。舍入的条件是x0&&x的最后k位不为0。intdivide_power2(intx,intk){intans=xk;intw=sizeof(int)3;ans+=(x(w-1))&&(x&((1k)-1));returnans;}2.78这相当于计算((x2)+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)。于是就计算(x2)+x，再右移一位即是所求答案。不过考虑到(x2)+x可能也会溢出，于是就计算(x3)+(x1)，这个显然是不会溢出的。再看看b(0)+b(2)会不会产生进位，如果产生进位，则再加一。最后考虑负数的舍入。负数向0舍入的条件是x0&&((x2)+x的后三位不全为0)。满足舍入条件的话，结果再加1。容易证明，加法后三位不全为0可以等价为x后三位不全为0。intmul5div8(intx){intb0=x&1,b2=(x2)&1;intans=(x3)+(x1);intw=sizeof(int)3;ans+=(b0&b2);ans+=((x(w-1))&&(x&7));returnans;}2.79不懂题意，感觉就是2.78。2.80A.1[w-n]0[n]:~((1n)-1)B.0[w-n-m]1[n]0[m]:((1n)-1)m2.81A.false，当x=0,y=TMin时，xy，而-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.82A.令x为无穷序列表示的值，可以得到x*2^k=Y+x。所以x=Y/(2^k-1)。B.(a)1/7,(b)9/15=3/5,(c)7/63=1/92.83浮点数的一个特点就是，如果大于0，则可以按unsigned位表示的大小排序。如果小于0则相反。注意都为0的情况即可。所以条件是：((ux1)==0&&(uy1)==0)||(!sx&&sy)||(!sx&&!sy&&ux=uy)||(sx&&sy&&ux=uy);2.84A.5.0，5表示为101，因此位数M就是1.01为1.25，小数f为0.01=0.25。指数部分应