[深入理解計算機系統](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

#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)上找到另一種精簡的回答：

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)

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)

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 語言中指標 (或稱指標常數) 就是是記憶體位址， 指標變數就是存放記憶體位址的變數。
* 陣列的寫法可以改寫成指標：

array[1] = *(array + 1) = 1[array]

/* 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;
} 

* 以此改寫作業的程式：

/*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]);

}

* 為何要用指標改寫陣列？
* 原因為，使用指標變數改寫，將使程式變得更具彈性。
* 根據測試，陣列作為指標常數，在決定好儲存位址後將不可手動改變，強行搬動會造成錯誤；
* 而指標變數則可以自由地更改記憶體位址，當然要小心別移到會造成區段錯誤的位址之類的。
* 測試程式碼如下：

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))