第1页 / 共93页
第2页 / 共93页
第3页 / 共93页
第4页 / 共93页
第5页 / 共93页
第6页 / 共93页
第7页 / 共93页
第8页 / 共93页
深入理解计算机系统（第二版）家庭作业答案.docx
深入理解计算机系统(第二版) 家庭作业 第二章
深入理解计算机系统二进制
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;
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.64
int any_even_one(unsigned x){
return !!(x & (0x55555555));
}
2.65
int 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 (x^1)&1
2.66
根据提示想到利用或运算，将最高位的 1 或到比它低的每一位上，忽然想如果 x 就是
10000000..该如何让每一位都为 1。于是便想到了二进扩展。先是 x 右移 1 位再和原 x
进行或，变成 1100000...，再让结果右移 2 位和原结果或，变成 11110000...，最后
到 16 位，变成 11111111...。
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.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(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.71
A.得到的结果是 unsigned，而并非扩展为 signed 的结果。
B.使用 int，将待抽取字节左移到最高字节，再右移到最低字节即可。
int xbyte(unsigned word, 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: (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>i)&1 ) {
h += (unsigned)x>>(w-i);
if(!uadd_ok(l, 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<> 3，当然，需要考虑 x 为负数时的舍入。
先看上述表达式，假设 x 的位模式为[b(w-1), b(w-2), ... , b(0)]，那么我们需要
计算：
[b(w-1),b(w-2),b(w-3),
...
,b(0), 0,
0]
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
