欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

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

    • 资源ID:11329372       资源大小:326.90KB        全文页数:95页
    • 资源格式: DOCX        下载积分:20金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要20金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

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

    精选优质文档-倾情为你奉上2.55-2.57 略2.58int is_little_endian()    int a = 1;    return *(char*)&a);2.59(x&0xFF) | (y&0xFF)2.60unsigned replace_byte(unsigned x, unsigned char b, int i)    return (x & (0xFF<<(i<<3) | (b << (i<<3);2.61A. !xB. !xC. !(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;    unsigned z = 1 << (w-k-1);    unsigned mask = z - 1;    unsigned right = mask & xsrl;    unsigned left = mask & (z&xsrl) + z);    return left | right;int srl(unsigned x, int k)    int xsra = (int) x >> k;    int w = sizeof(int)*8;    unsigned z = 2 << (w-k-1);    return (z - 1) & xsra;2.64int any_even_one(unsigned x)    return !(x & (0x);2.65int even_ones(unsigned x)    x = (x >> 16);    x = (x >> 8);    x = (x >> 4);    x = (x >> 2);    x = (x >> 1);    return !(x&1); x的每个位进行异或,如果为0就说明是偶数个1,如果为1就是奇数个1。那么可以想到折半缩小规模。最后一句也可以是 return (x1)&12.66根据提示想到利用或运算,将最高位的1或到比它低的每一位上,忽然想如果x就是.该如何让每一位都为1。于是便想到了二进扩展。先是x右移1位再和原x进行或,变成.,再让结果右移2位和原结果或,变成.,最后到16位,变成.。int leftmost_one(unsigned x)    x |= (x >> 1);    x |= (x >> 2);    x |= (x >> 4);    x |= (x >> 8);    x |= (x >> 16);    return x(x>>1);2.67A.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.69unsigned rotate_right(unsigned x, 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.71A.得到的结果是unsigned,而并非扩展为signed的结果。B.使用int,将待抽取字节左移到最高字节,再右移到最低字节即可。int xbyte(unsigned word, int bytenum)    int ret = word << (3 - bytenum)<<3);    return ret >> 24;2.72A.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)=(2w - 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: (unsigned t) < (unsigned a) 进位标志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(unsigned x, unsigned y)    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。注:不使用long long来实现signed_high_prod(int x, int y)是一件比较复杂的工作,而且我不会只使用整数位级编码规则来实现,因为需要使用循环和条件判断。下面的代码是计算两个整数相乘得到的高位和低位。int uadd_ok(unsigned x, unsigned y)    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<w; i+)        if( (y>>i)&1 )             h += (unsigned)x>>(w-i);            if(!uadd_ok(l, x<<i) h+;            l += (x<<i);                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: (x<<2) + xB. K=9: (x<<3) + xC. 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<<k)-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.80A. 1w-n0n:  (1<<n) - 1)B. 0w-n-m1n0m: (1<<n) - 1) << m2.81A. 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.82A. 令x为无穷序列表示的值,可以得到x*2k = Y + x。所以 x = Y/(2k - 1)。B. (a)1/7, (b)9/15 = 3/5, (c)7/63 = 1/92.83浮点数的一个特点就是,如果大于0,则可以按unsigned位表示的大小排序。如果小于0则相反。注意都为0的情况即可。所以条件是:(ux<<1)=0 && (uy<<1)=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。指数部分应该为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 = 2k - 3,即为11.101。位表示为0-11.101-00.0。2.85描述扩展精度值十进制最小的正非规格化数2(-63)*2(-214+2)3.6452e-4951最小的正规格化数2(-214+2)3.3621e-4932最大的规格化数(264-1)*2(214-1-63)1.1897e+49322.86描述HexMEV-00x80000-62-最小的值>10x3F01257/2560257*2(-8)2560x470018-最大的非规格化数0x00FF255/256-62255*2(-70)-inf0xFF00-Hex为0x3AA00x3AA0416/256-5416*2(-13)=13*2(-8)2.87格式A格式B位值位值1 01110 001-9/161 0110 0010-9/160 10110 1012080 1110 10102081 00111 110-7/10241 0000 0111-7/10240 00000 1016/2170 0000 000001 11011 000-40961 1111 0000-inf0 11000 1007680 1111 0000inf没有特别明白转换成最接近的,然后又说向+inf舍入的含义。按理说,舍入到+inf就是向上舍入,而并不是找到最接近的。表格中是按最接近的进行舍入,并且如果超出范围则认为是inf。如果都按+inf进行舍入,那么第四行格式B将是0 0000 0001。2.88A. false,float只能精确表示最高位1和最低位的1的位数之差小于24的整数。所以当x=TMAX时,用float就无法精确表示,但double是可以精确表示所有32位整数的。B. false,当x+y越界时,左边不会越界,而右边会越界。C. true,double可以精确表示所有正负253以内的所有整数。所以三个数相加可以精确表示。D. false,double无法精确表示264以内所有的数,所以该表达式很有可能不会相等。虽然举例子会比较复杂,但可以考虑比较大的值。E. false,0/0.0为NaN,(非0)/0.0为正负inf。同号inf相减为NaN,异号inf相减也为被减数的inf。2.89float的k=8, n=23。 bias = 27 - 1 = 127。最小的正非规格化数为2(1-bias-n) = 2-149。最小的规格化数为2(0-bias)*2 = 2-126。最大的规格化数(二的幂)为2(28-2 - bias) = 2127。因此按各种情况把区间分为TMin, -148 -149, -125 -126, 127 128, TMax。float fpwr2(int x)    /* Result exponent and fraction */    unsigned exp, frac;    unsigned u;    if (x < -149)         /* Too small. Return 0.0 */        exp = 0;        frac = 0;     else if (x < -126)         /* Denormalized result */        exp = 0;        frac = 1<<(x+149);     else if (x < 128)         /* Normalized result. */        exp = x + 127;        frac = 0;     else         /* Too big. Return +oo */        exp = 255;        frac = 0;        /* Pack exp and frac into 32 bits */    u = exp << 23 | frac;    /* Return as float */    return u2f(u);2.90A.pi的二进制数表示为:0 1,E=128-127=1,它表示的二进制小数值为:11.B.根据2.82,可知1/7的表示为0.001.,所以22/7为11.1001001.C.从第9位开始不同。为了方便测试2.91-2.94,我写了几个公共函数。typedef unsigned float_bits;float u2f(unsigned x)    return *(float*)&x);unsigned f2u(float f)    return *(unsigned*)&f);bool is_float_equal(float_bits f1, float f2)    return f2u(f2) = f1;bool is_nan(float_bits fb)    unsigned sign = fb>>31;    unsigned exp = (fb>>23) & 0xFF;    unsigned frac = fb&0x7FFFFF;    return exp = 0xFF && frac != 0;bool is_inf(float_bits fb)    unsigned sign = fb>>31;    unsigned exp = (fb>>23) & 0xFF;    unsigned frac = fb&0x7FFFFF;    return exp = 0xFF && frac = 0;int testFun( float_bits(*fun1)(float_bits),  float(*fun2)(float)    unsigned x = 0;    do /test for all 232 value        float_bits fb = fun1(x);        float ff = fun2(u2f(x);        if(!is_float_equal(fb, ff)            printf("%x errorn", x);            return 0;                x+;    while(x!=0);    printf("Test OKn");     return 1;最后的testFun是用来测试fun1和fun2是否对每种可能的输入都输出相同的值,fun1为题中所要求的函数,fun2为float版本。这个函数大概会运行2到3分钟,也可以写多线程,利用多核处理器求解。 2.91float_bits float_absval(float_bits f)    if(is_nan(f) return f;    else return f & 0x7FFFFFFF;float float_absval_f(float f)    if(is_nan(f2u(f) return f;    else return fabs(f);测试即调用testFun(float_absval, float_absval_f);在测试的时候发现0x7F的时候不对了。后来debug了一下,发现u2f的时候,会篡改原值。即令x = 0x7F。则f2u(u2f(x)会变成0x7FC00001。奇怪的nan,第22位一定是1。我将f2u和u2f里用memcpy也同样是不行。所以,我将testFun中的一个条件变成了:if(!is_float_equal(fb, ff) && !is_nan(fb)这个bug实在是不知道怎么回事。想了想,这和高位低位排列是无关的。这个bug还是之后再找吧。也有可能是硬件本身的原因了。注:C库中也提供了isnan()函数。2.92float_bits float_negate(float_bits f)    if(is_nan(f) return f;    else return f0x;float float_negate_f(float f)    if(isnan(f) return f;    return -f;就是将最高位反位。2.93float_bits float_half(float_bits f)    unsigned sign = f>>31;    unsigned exp = (f>>23) & 0xFF;    unsigned frac = f&0x7FFFFF;    if(exp = 0) return sign<<31 | (frac>>1) + (frac&1)&&(frac>>1)&1);    else if(exp = 1) return sign<<31 | ( (1<<22) | (frac>>1) + (frac&1)&&(frac>>1)&1)     else if(exp != 255) return sign<<31 | (exp-1) << 23 | frac;    else return f;float float_half_f(float f)    if(!isnan(f) return (float)0.5*f;    else return f;需要注意的是,舍入采用的是向偶数舍入。这也是我在测试的过程中发现的。(好吧,书上在浮点数位级编码规则中说过了,眼残没看到)最后,非规格化的平滑效果让exp=1时的程序变得比较简洁。2.94float_bits float_twice(float_bits f)    unsigned sign = f>>31;    unsigned exp = (f>>23) & 0xFF;    unsigned frac = f&0x7FFFFF;    if(exp = 0) return sign<<31 | frac<<1;    else if(exp < 254) return sign<<31 | (exp+1)<<23 | frac;    else if(exp = 254) return sign<<31 | 0xFF<<23;    else return f;float float_twice_f(float f)    if(!isnan(f) return (float)2*f;    else return f;比float_half简单一些。对于非规格化的平滑,使用移位就可以了,对于规格化,只要exp+1即可,当然,如果exp=254,就要返回inf了。2.95float_bits float_i2f(int i)    if(i = 0) return 0;    unsigned x = i>0?i:-i;    int sign = i>0?0:1;    int w = sizeof(int)<<3;    int j;    for(j=w-1; j>=0; j-) /找到最高位        if( (x>>j) & 1) break;        unsigned bias = 127;    unsigned exp, frac;    exp = bias + j;    if(j <= 23) frac = x<<(23-j);    else         frac = x>>(j-23);        unsigned mask = (1<<(j-23) - 1;        if( (x&mask) > (1<<(j-24) ) frac+; /需要舍入到大值        else if( (x&mask) = 1<<(j-24)  &&  (frac&1) frac+; /舍入到偶数        if(frac = (1<<24) exp+; /舍入到偶数超过(1<<24) - 1,指数需要再加1        return sign<<31 | exp<<23 | frac&0x7FFFFF;void test()    int x = 0;    do        float_bits fb = float_i2f(x);        float ff = (float)x;        if(!is_float_equal(fb, ff)            printf("error in %d:  %x %xn", x, fb, f2u(ff);            return;                x+;    while(x!=0);    printf("Test OKn");无耻地使用了循环。我也是一点一点测试修改,才通过的。不过好在大方向都知道,所以没有花多少时间,主要纠结点还是在舍入那块。需要特别注意。2.96int float_f2i(float_bits f)    unsigned sign = f>>31;    int exp = (f>>23) & 0xFF;    int frac = (f&0x7FFFFF) | (1<<23);    exp -= 127;    if(exp < 0) return 0;    if(exp >= 31) return 0x; /绝对值不大于231(1<<31)    if(exp > 23) frac <<= (exp - 23);    else frac >>= (23 - exp);    return sign? -frac : frac;void test2()    int x = 0;    do        int m = float_f2i(x);        int n = (int)u2f(x);        if(m != n)            printf("error in %x:  %d %dn", x, m, n);            return;                x+;    while(x!=0);    printf("Test OKn");在exp<0和>=31上犯了小错误。开始写成<=0和>=32了。其实1这个整数就是exp=0的。而int绝对值不会超过231-1,因此1.0000.小数点右移不会到超过30次(否则就越界了),所以exp<=30。而这里刚好用TMin来表示越界,因此不用关心TMin的表示。3.54int decode2(int x, int y, int z)    int ret;    z -= y; /line 2    ret = z; /line 3    ret <<= 15;/line 4    ret >>= 15;/line 5    return ret*(zx);3.55大概算法如下:x的高32位为xh,低32位为xl。y的符号位扩展成32位之后为ys(ys为0或者-1)。dest_h = (xl*ys)_l + (xh*y)_l + (xl*y)_hdest_l = (xl*y)_l注意,所有的乘法都是unsigned*unsigned。也就是说对于 1*(-1),如果存入两个寄存器中,那么高32位是0,低32位是-1。 相当于 1*(UNSIGNED_MAX)。3.56注意n在这里是一个很小的数,用8位就能表示,也可以用n=n%256表示。寄存器 变量esi    xebx    nedi    resultedx    maskint loop(int x, int n)    int result =     int mask;    for(mask = 1<<31; mask != 0; mask = (unsigned)mask)>>n)        result = (mask & x);        return result;3.57xp?*xp:0这个语句是不能被编译成条件传送语句的。因为如果是条件传送语句,那么不论xp为什么,*xp都会被计算。我们要写一个和该功能完全一样的能编译成条件传送语句的函数。于是,我们要想办法不使用*xp,而使用一个替代的指向0的非空指针。int cread_alt(int *xp)    int t = 0;    int *p = xp?xp:&t;    return *p;3.58MODE_A: result = *p1; *p1 = *p2; break;MODE_B: result = *p1 + *p2; *p2 = result; break;MODE_C: result = *p1; *p2 = 15; break;MODE_D: *p2 = *p1;MODE_E: result = 17; break;default: result = -1; break;3.59int switch_prob(int x, int n)    int result = x;    switch(n)            case 0x28:        case 0x2a:            result <<= 3; break;        case 0x2b:            result >>= 3; break;        case 0x2c:            result <<= 3;             result -= x;        case 0x2d:            result *= result;        case 0x29: /也可以不要        default:            result += 0x11;                    return result;中间有一句话没明白,汇编第12行 lea 0x0(%esi), %esi3.60对于ARST,Aijk 的位置是 A(,i*S*T+j*T+k,4)。

    注意事项

    本文(深入理解计算机系统(第二版)-家庭作业答案(共95页).docx)为本站会员(飞****2)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开