深入理解计算机系统第二、三章家庭作业
题目2.64
题目要求
判断二进制数偶数位是否有任意一位位为1，有的话返回1，否则返回0
解题过程
int any_even_one(unsigned x)
{
return !!(x & (0x55555555));
}
题目2.65
题目要求
写出代码实现如下函数：
int even_ones(unsigned x);
解题过程
分析：因为本题受12次操作的限制，故不能按位计算是否该位为1。考虑到本题只需要判断1的个数的奇偶性，而并不需要计算一共有多少个1。那么我们考虑到如果能去掉偶数个1对结果并不会产生影响，这需要快速的去掉偶数个1。因为异或运算恰好可以把同为1时变成0。然后在利用分治的方法，整体异或来减少操作次数。
操作：
1.前16和后16位对齐后异或，那么这时候原来32位的奇偶性和目前异或出来的16位的结果一致。
2.同理前8位和后8位对齐异或。
3.同理前4位和后4位对齐异或。
4.同理前2位和后2位对齐异或。
5.同理前1位和后1位对齐异或。
最后只需要判断最后那一位上是1还是 0即可。
int even_ones(unsigned x)
{
unsigned y = x >> 16; x ^= y;
y = x >> 8; x ^= y;
y = x >> 4; x ^= y;
y = x >> 2; x ^= y;
y = x >> 1; x ^= y;
return !(x & 1);
}
题目3.66
题目要求
你负责维护一个大型的C 程序时，遇到如下代码：
1 typedef struct {
2 int left;
3 a_struct a[CNT];
4 int right;
5 } b_struct;
6
7 void test(int i, b_struct *bp)
8 {
9 int n = bp->left + bp->right;
10 a_struct *ap = &bp->a[i];
11 ap->x[ap->idx] = n;
12 }
通过反汇编代码得出CNT的值和a_struct的完整声明：
1 000000 <test>:
2 0:55push %ebp
3 1:89 e5 mov%esp,%ebp
4 3:53 push %ebx
5 4:8b 45 08 mov0x8(%ebp),%eax ;%eax=i
6 7:8b 4d 0c mov0xc(%ebp),%ecx ;%ecx=bp
7 a:8b d8 1c imul $0x1c,%eax,%ebx ;%ebx=i*28
8 d:8d 14 c5 00 00 00 00 lea0x0(,%eax,8),%edx ;%edx=8i;
9 14:29 c2 sub%eax,%edx ;%edx=7i;
10 16:03 54 19 04 add0x4(%ecx,%ebx,1),%edx ;%edx=7i+[bp+28i+4]
11 1a:8b 81 c8 00 00 00 mov%0xc8(%ecx),%eax ;%eax=right
12 20:03 01 add(%ecx),%eax ;%eax=right+left
13 22:89 44 91 08 mov%eax,0x8(%ecx,%edx,4) ;[bp+4*7i+4*[bp+28i+4]+0x8]=%eax
14 26:5b pop%ebx
15 27:5d pop%ebp
16 28:c3 ret
解题过程
A CNT=7
B
struct a_struct
{
int idx;
int x[6];
}
下面是简单的分析
5 i -->eax
6 bp -->ecx
7 28i-->ebx
8 8i-->edx
9 7i-->edx
10(28i+bp+4)+7i-->edx 对于C中第10行,我觉得这一行有点难理解，(28i+bp+4)是直接计算出了ap->idx的值，因为a_struct只包含7个int值，所以加7i，就计算出了ap->x[ap->idx]距离a[CNT]的起始地址有多少个int
11 *(bp+0xc8)-->eax
12 bp+(bp+0xc8) -->eax 对应C第9行
13 eax-->(edx4+bp+8) 对应C第11行。
3.68
解题过程
void good_echo()
{
char c;
int x = 0;
while( x=getchar(), x!='
' && x!=EOF)
{
putchar(x);
}
}
参考资料
1.esp和ebp的区别：http://blog.csdn.net/running_noodle/article/details/2838679
2.寄存器详解：http://wenku.baidu.com/link?url=m0isHkEhemZjFVVi46QzXgfkBdBUaF3FBMTpblEV1bSuWNjgjVHiDjXHXK330-4JuysvJFZE0tSybe6UgP7sQFtjfWDSMAAlrF4gj833uOW
3.http://wenku.baidu.com/link?url=ZwLOIG3ha7OK1EYU1n3jLKR9zD158bEgXEBu5RteaqhyFa_rntWK5pJ5CjIQoR-bhKNZRjBsHtrEq8JlZeSoSfeXD8bwMJBa4MLGd1Qbiam
4.http://blog.csdn.net/yang_f_k/article/details/9007303