深入了解計算機系統家庭作業

深入了解計算機系統第二章家庭作業

題目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

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!='\n' && x!=EOF)

putchar(x);

}

深入了解計算機系統第六章家庭作業

6.35

對于寫配置設定的高速緩存，每次寫不命中時，需要讀取資料到高速緩存中。

該高速緩存隻有2個組，對于相同的i,j，src[i][j]和dst[i][j]對應相同的組。

src[0] src[2] 對應組0；

src[1] src[3] 對于組1。

dst同src。

dst數組

　列0 列1 列2 列3

行0 m h m h

行1 m m h m

行2 m h m h

行3 m m h m

src數組

行0 m m m m

行1 m m m m

行2 m m m m

行3 m m m m

6.36

緩存能完全容得下兩個數組，是以隻會出現冷不命中。

行0 m h h h

行1 m h h h

行2 m h h h

行3 m h h h

參考資料

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

深入了解計算機系統家庭作業彙總 20135301&amp;&amp;20135328