owned this note
owned this note
Published
Linked with GitHub
[深入理解計算機系統](https://hackmd.io/s/SJ7V-qikG)作業練習
===
### 2.58: 撰寫函式 is_little_endian，在 Little endian 機器上返回 1，反之返回 0，應能在任意機器、無論幾位元的架構都適用 (Page 88)
如果你在文件上看到一個雙字組的data，Ex: long MyData=0x12345678，要寫到從0x0000開始的記憶體位址時。
* 如果是Big Endian的系統：
最高位數的位元組在記憶體位址最低位元，最低位數的位元組在位址最高位元，依次排列。(記憶體儲存順序為從低到高)
例如 123 以 Big Endian 解釋的話會是 100 + 20 + 3。
* 如果是Little Endian的系統：
最低位數的位元組在最低位元，最高位數位元組在最高位元，反序排列。
123 = 1 + 20 + 300
```clike=
#include <stdio.h>
typedef union { long l; unsigned char c[4];}EndianTest;
int is_little_endian(int argc, char* argv[]){
EndianTest a;
a.l = 0x12345678;
int i = 0;
if(a.c[0]==0x78 /*&& a.c[1]==0x56 && a.c[2]==0x34 && a.c[3]==0x12*/){
return 1;
}
else{
return 0;
}
}
```
在[網路](https://stackoverflow.com/questions/12791864/c-program-to-check-little-vs-big-endian)上找到另一種精簡的回答：
```clike=
int main()
{
int x = 1;
char *y = (char*)&x;
printf("%c\n",*y+48);
}
```
* *y + 48 內的 48 為 ASCII 碼中 " 0 " 的編碼，而 49 則為 " 1 " 的編碼，因此當 y 指向的 x 位址為 1 時，最後 print 出來的字元就會是 1 ，反之則為 0 。
* 假設電腦為 32 bits，在 Little Endian 情況下，記憶體的儲存狀況與 &x 的位址如下：
```
higher memory
----->
+----+----+----+----+
|0x01|0x00|0x00|0x00|
+----+----+----+----+
A
|
&x
```
* 這時候 &x 的值就會是 1 ，在 printf 執行後 可以變成 ASCII 碼中的 " 1 "。
* 若是 Big Endian：
```
higher memory
----->
+----+----+----+----+
|0x00|0x00|0x00|0x01|
+----+----+----+----+
A
|
&x
```
* &x 值為 0 ， 會 print 出 ASCII 的 " 0 "。
* 整個程式做的事情如下：
* 把 x 的值設為 1 (數字)。
* 設一個 y 的 char 指標，指向轉型成 char 指標的 x 的位址，此時指到的 &x 會有兩種情況，0 或 1。
* 最後再根據 %c ，把 *y 的值加上 48 ，利用 %c 把數字(ASCII CODE)轉換成字元 0 或 1。
### 2.66: 撰寫函式 leftmost_one，產生得以找出數值 x 最高位 1 的位元遮罩 (Page 90)
```clike=
int leftmost_one(unsigned int x)
{
unsigned int mask = x;
mask |= mask >> 1; //mask = mask | (mask >>1)
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
mask = (~mask) >> 1;
return x & mask;
}
```
### 2.92: 撰寫函式 float_negate，給定浮點數 f，回傳 -f，倘若 f 是 NaN，直接回傳 f。輸入數值範圍為有效的 $2^{32}$ 個數值 (Page 96)
```clike=
float_bits float_negate(float_bits f){
unsigned sign = f >> 31;
unsigned exp = f >> 32 & 0xFF;
unsigned frac = f & 0x7FFFFF;
int is_NaN = (exp == 0xFF)&&(frac != 0);
if(is_NaN){
return f;
}
return ((~sign & 1) << 31) | (exp << 23) | frac;
}
```
https://dreamanddead.gitbooks.io/csapp-3e-solutions/chapter6/6.37.html
6.41想
### 4.47: 以 C 語言指標改寫原本使用陣列表示法的氣泡排序程式碼 (Page 327) / 延伸題目: 最佳化 / Analysis on Bubble Sort Algorithm Optimization
* [參考資料](http://epaper.gotop.com.tw/pdf/acl028800.pdf)
* 不使用陣列，改用指標改寫時，一開始遭遇到的困難是不知道該如何指定特定的陣列，然後想到，或許陣列跟指標有更深入的關係。
* 陣列為其中一種指標常數。
* C 語言中指標 (或稱指標常數) 就是是記憶體位址， 指標變數就是存放記憶體位址的變數。
* 陣列的寫法可以改寫成指標：
```clike=
array[1] = *(array + 1) = 1[array]
```
```clike=
/* pointerArr1-5.c */
#include <stdio.h>
#include <conio.h>
int main()
{
int arr[]= {100, 101, 102};
int *ptr = arr;
int i, size = 0;
size = (sizeof arr/ sizeof (arr[0]) );
/* ------------Using arr--------------*/
printf("使用 arr 指標常數來表示:\n");
for(i = 0; i < size; i++)
printf("&arr[%d] = %x\n", i, &arr[i]);
printf("\n");
for(i = 0; i < size; i++)
printf("arr+%d = %x\n", i, arr+i);
printf("\n");
for(i = 0; i < size; i++)
printf("arr[%d] = %x\n", i, arr[i]);
printf("\n");
for(i = 0; i < size; i++)
printf("*(arr+%d) = %x\n", i, *(arr+i));
/*--------------Using ptr-------------*/
printf("\n 使用 ptr 指標變數來表示:\n");
for(i = 0; i < size; i++)
printf("ptr+%d = %x\n", i, ptr+i);
printf("\n");
for(i = 0; i < size; i++)
printf("ptr[%d] = %d\n", i, ptr[i]);
printf("\n");
for(i = 0; i < size; i++)
printf("*(ptr+%d) = %d\n", i, *(ptr+i));
getch();
return 0;
}
```
* 以此改寫作業的程式：
```clike=
/*Bubble_sort:Array version*/
#include <stdio.h>
void swap(long *a, long *b)
{
if(*a != *b) {
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
void bubble_p(long* data, long count) {
long *i, *last;
for (last = data+count-1; last > data; last--) {
for (i = data; i < last; i++) {
if (*(i+1) < *i) {
/* swap adjacent elements */
swap((i+1),(i));
}
}
}
}
void main(){//測試用
long a[5] = {-1,-5,5,12,55};
bubble_p(a,5);
for(int i = 0; i < 5; i++)
printf("%ld\n",a[i]);
}
```
* 為何要用指標改寫陣列？
* 原因為，使用指標變數改寫，將使程式變得更具彈性。
* 根據測試，陣列作為指標常數，在決定好儲存位址後將不可手動改變，強行搬動會造成錯誤；
* 而指標變數則可以自由地更改記憶體位址，當然要小心別移到會造成區段錯誤的位址之類的。
* 測試程式碼如下：
```clike=
void main(){
int x[5], iArray[5];//x為指標常數，但是x[0]等等的不是，為指標變數。
printf("%d %d %d %d \n",x,&x+1,iArray,&iArray+1);//測試
//iArray = &x; // ERROR
//iArray = x; // ERROR
//x 代表 1個整數資料的起始記憶體位址 (x+1 為 &x[0] 記憶體位址加上 sizeof(int))
*(iArray + 4) = 10; // OK: 存取變數 iArray[4]
int *a,*b;
//a = b; //OK： a , b 位址互換
//a = b+1; //OK： a , b+1 (可視為 b[1])位址互換
a = &x[2]; //OK： 將陣列 x[2]的位址給 a
a = x; //OK： 將 &x[0] 的位址給 a
printf("%d %d %d %d",a,a+1,b,b+1);//測試
}
```
* ~~&x 代表 5個整數資料的起始記憶體位址 (&x+1 為 &x[0] 記憶體位址加上 5*sizeof(int))~~：這一行我存有疑問，因為&後面不該接指標常數，而且照我查找資料的定義使用&x 在指標變數上，依然錯誤，因此我認為這資料的這部分可以保留疑問。而詢問資工系同學後，發現他編譯出的成果會是&x+1 跟 x的位址一樣，猜測跟編譯器的版本相關。
### 6.37: 計算 N=64 和 N=60 的 cache miss rate (Page 455)
#### N = 64時：
* sizeof(array_t) == 64 64 == 4096 == 4C;
* sum += a[i][j];的情形：
* 讀到的記憶體位址：0, 4, 8, 12, ....., 4096*4-4
* 讀到的快取：0, 0, 0, 0, 1, 1, 1, 1,.....255, 255, 255, 255, 0, 0, 0, 0,.....255, 255, 255, 255
* 讀到一次會 miss 3 次，cache miss rate = 1/4 = 25%。
#### N = 60時：
* sum += a[i][j];的情形：
*
### 6.45: 撰寫更快的轉置矩陣實作 (Page 458)
### 6.46: 有向圖轉換為無向圖 (Page 458) / 參考: Graph, 相鄰矩陣 (Adjacency Matrix))
Sign in with Wallet
