# 2018q1 Homework3 (c-review)
contributed by < `BroLeaf `>
###### tags `BroLeaf`
## [第四週測驗題](https://hackmd.io/s/SynmEVIqG)
### 測驗 `1`
#### 解題
```clike=
void FuncA(struct node **start, int value) {
if (!*start) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
```
1. 可以看出 `FuncA` 一開始有 `if (!*start)` 推斷出這是給第一次 call 用的，直接 malloc 一塊記憶體、設完 node 就 return 了。
後面自然就是第二次以上 call function 用到的部份。
`new_node->next = *start(*start)->prev = new_node;`
新結點的 next 是 start ， start 的 prev 是 新結點，知道這是把新加入的結點塞在最後一個結點後面當作新的最後一個。
`FuncA` 就是 建立新節點，內容是 `value`，並安插在結尾
```clike=
void FuncB(struct node **start, int value) {
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev = new_node;
*start = new_node;
}
```
2. 這段程式碼跟上段程式碼後半不一樣的地方就是 `*start = new_node;` 他把新結點設為 start ，跟第1題相反。
`FuncB` 是 建立新節點，內容是 `value`，並安插在開頭
```clike=
void FuncC(struct node **start, int value1, int value2) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value1;
struct node *temp = *start;
while (temp->data != value2)
temp = temp->next;
struct node *next = temp->next;
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
```
3. value1 是要插入的新結點的值， value2 是用來比對的值。 while loop 是找到與 value1 相同值的結點把他叫作 temp，
`temp->next = new_node;`、`next->prev = new_node;` 修改前後結點的 link ，
`new_node->prev = temp;`、`new_node->next = next;` 設定新結點的 link ，
所以可以看出新結點是在 temp 後、 next 前
`FuncC` 是 找到節點內容為 `value1` 的節點，並在之後插入新節點，內容為 `value2`
```clike=
void display(struct node *start) {
struct node *temp = start;
printf("Traversal in forward direction \n");
for (; temp->next != start; temp = temp->next)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\nTraversal in reverse direction \n");
struct node *last = start->prev;
for (temp = last; temp->prev != last; temp = temp->prev)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\n");
}
int main() {
struct node *start = NULL;
FuncA(&start, 51); FuncB(&start, 48);
FuncA(&start, 72); FuncA(&start, 86);
FuncC(&start, 63, 51);
display(start);
return 0;
}
```
4. 按照main call function 的順序
FuncA(&start, 51)：51
FuncB(&start, 48)：48->51
FuncA(&start, 72)：48->51->72
FuncA(&start, 86)：48->51->72->86
FuncC(&start, 63, 51)：48->51->63->72->86
再來看 diaplay ，第 4 行 for loop 的終止條件是`temp->next != start`也就是當跑到最後一個結點時就會跳出不會進去，所以在 for 的外面多 printf 一次就是印出最後一個值，當前結點在最後一個，
現在印出的：
`48 51 63 72 86`
第 8 行把結點改成最後一個，若這是一個環狀的 link-list 實際上註解掉好像也不會改變結果？
第 9 行邏輯和前面的一樣，把 for loop 終止在第一個結點，然後多 printf 一次，
所以最後會印出的順序是：
`48 51 63 72 86 86 72 63 51 48`
### 測驗 `2`
```clike=
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
```
1. 終止條件是 `node && node != head` 當 node 跑到沒有宣告的區域，或是變成 head 時就會終止，可以想成跑一整個 link-list 在多一次 next 就跳出迴圈。
所以如果這不是環狀的 return node - head 就不會是 0 ，相反若是環狀的就會返回 0 。
而 `data++` 是 " 指向 data 的 address ++ " 而不是 data 裡面的值去++
所以這裡的答案不是 `(f)` 而是
`(e)` 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值
```clike=
int main() {
int count = 0;
struct node *head = node_new(0);
head->next = node_new(1);
head->next->next = node_new(2);
head->next->next->next = node_new(3);
head->next->next->next->next = node_new(4);
printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next = head;
printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next->next = head->next;
printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next = head->next->next->next->next->next->next->next->next;
printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
printf("K5 >> %d\n", head->next->data);
printf("count >> %d\n", count);
return 0;
}
```
2. 根據程式碼一個個排下來，現在的 link-list 是：
`0 -> 1 -> 2 -> 3 -> 4`
不是一個環狀的 link-list 所以第一個 `FuncX` 回傳非0值，所以
K1 是 YES
3. `head->next->next->next->next = head` 把最後一個 next 遮住不要看，就會發現其實是指 value 是 3 的結點，把 next 放進去一起看，就是把那個結點的 next 變成 head ，就變成了環狀 link-list
`0 -> 1 -> 2 -> 3 -> 0 ->........`
`FuncX` 回傳 0
所以 K2 是 NO
4. `head->next = head->next->next->next->next->next->next->next->next` 同樣用上一的看法，連到最後會發現連到 head 變成：
`0 -> 0 -> ......`
還是環狀的 所以 K3 是 NO
5. `head->next` 永遠是 head 所以整個結構沒有變
所以 K4 是 NO
6. head->data = 0
所以 K5 是 0
7. 這題第一題就提到過了，改變的只是在 function 的 local value 的 address 沒有真的改到 data
所以 是 0
## [第五週測驗題(上)](https://hackmd.io/s/SynmEVIqG)
### 測驗 `1`
```clike=
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
1. 代數字進去是最快的解題方式，
把 0 帶入，會直接 return 32
把 1 帶入，進入一次遞迴， return 32 - 1
把 2 帶入，進入兩次遞迴， return ( 32 -1 ) -1
把 3 帶入，進入兩次遞迴， return ( 32 -1 ) -1
算到這裡就知道， `Func32` 會把傳進去的數字作邏輯右移，再 return ( 32 - 進入遞迴的次數 )，得到的結果就是
`(c)` 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
將 Func32 改寫為以下功能等價的程式碼:
```clike=
uint8_t FuncI(uint32_t x)
{
if (!x) return 32;
int n = 1;
if (!(x >> 16)) { n += 16; x <<= 16; }
if (!(x >> M1)) { n += 8; x <<= 8; }
if (!(x >> M2)) { n += 4; x <<= 4; }
if (!(x >> M3)) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
2. 知道這個 function 也是在算 clz 後理解就比較快了，5678行就是關鍵，分別用來確認 x 前 16 8 4 2 bits 是不是 0 如果是就加上去，並改變 x 的值，把要檢查的剩下部份位移到前面的幾個 bits。如果不是，就縮小範圍繼續檢查。
再來是 `n = n - (x >> 31)` 就是檢查剩下最後沒有被檢查到的那個 bit 。
在第六行時，要檢查的部份只剩下 x 的前 8 bits，所以 M1 = 24
以此類推，
第七行檢查前 4 bits ，所以M2 = 28
第八行檢查前 2 bits ，所以M3 = 30
知道這是 [afcidk](https://hackmd.io/s/SkS7PeXsf) 說的 二分搜尋法 就可以更快理解這個概念。
### 測驗 2
延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。
Func64 的作用為？
```clike=
#include <stdint.h>
#include <stdio.h>
union u_qword {
struct {
uint32_t low;
uint32_t high;
} dwords;
uint64_t qword;
};
struct udiv_result {
union u_qword q;
union u_qword r;
};
static inline int Func64(uint64_t val)
{
uint32_t lo = (uint32_t) val;
uint32_t hi = (uint32_t) (val >> 32);
return hi ? Func32(hi) : 32 + Func32(lo);
}
static int do_udiv32(uint32_t dividend,
uint32_t divisor,
struct udiv_result *res)
{
/* Ensure dividend is always greater than or equal to the divisor. */
uint32_t mask = Func32(divisor) - Func32(dividend);
divisor <<= mask; /* align divisor */
mask = 1U << mask; /* align dividend */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.dwords.low |= mask;
}
divisor >>= 1;
} while ((P1) && dividend);
res->r.dwords.low = dividend;
return 0;
}
int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
uint64_t mask;
uint64_t bits;
res->q.qword = res->r.qword = 0;
if (divisor == 0) { /* division by 0 ? */
res->q.qword = 0xffffffffffffffffull;
return -1;
}
if (divisor == dividend) {
res->q.qword = 1;
return 0;
}
if (divisor > dividend) {
res->r.qword = dividend;
return 0;
}
/* only 32 bit operands that the preconditions are fulfilled. */
if (!(divisor >> 32) && !(dividend >> 32))
return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);
bits = Func64(divisor) - Func64(dividend);
divisor <<= bits; /* align divisor and dividend */
mask = 1ULL << bits;
/* division loop */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.qword |= mask;
}
divisor >>= 1;
mask >>= 1;
} while ((P2) && dividend);
res->r.qword = dividend;
return 0;
}
int main()
{
char digitbuff[20];
char *pos = digitbuff + sizeof(digitbuff);
union u_qword v; /* current value */
union u_qword nv; /* next value */
struct udiv_result d;
int64_t value = 0xCAFEBABE; /* Java classfile magic number */
v.qword = (unsigned long long) value;
while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
/* determine digits from right to left */
udiv64(v.qword, 10, &d);
*--pos = d.r.dwords.low + P3;
v.qword = d.q.qword;
}
do { /* process 32 bit (or reduced 64 bit) value */
nv.dwords.low = v.dwords.low / P4;
*--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
} while ((v.dwords.low = nv.dwords.low) != 0);
int len = digitbuff + sizeof(digitbuff) - pos;
char *p = pos;
while (len--)
putchar(*p++);
printf("\n");
return 0;
}
```
## [第五週測驗題(中)](https://hackmd.io/s/HkQjgqI5G)
### 測驗 `1`
已知在 x86_64 架構，以下程式碼的執行輸出是 `jserv++C`:
```clike=
#include <stdio.h>
int main() {
puts((char *) &(double []){ 3823806048287157.0, 96 });
}
```
根據題目的意思，宣告一個 double 變數，然後在"不改變其記憶體內容下"強制轉成 char 並輸出，關鍵點就在於 double 變數裏面儲存的到底是什麼東西。
根據 [double converter](http://www.binaryconvert.com/convert_double.html#) 將
`3823806048287157.0` 轉換後會變成 `0x432B2B767265736A`
再把得到的十六進位數字丟到 [hex to string converter](https://codebeautify.org/hex-string-converter)
`0x432B2B767265736A` 轉換後會得到 `C++vresj`
發現跟實際得到的結果是完全相反的，這是因為 x86-64 架構是 little-endian 就是說當我們要存一個 double 數
`0x432B2B767265736A`
它實際上在記憶體的內容會是
`0x6A736572762B2B43`
所以用 char 一個 byte 一個 byte 去讀，結果就會是相反的
參考：[Big and Little Endian Byte Order](http://www.yolinux.com/TUTORIALS/Endian-Byte-Order.html)
考慮以下程式碼，假設 puts 函式總是可正確運作，那麼程式輸出為何？
```clike=
#include <stdio.h>
double m[] = { 3823806048287157.0, 96 };
void gen() {
if (m[1]--) {
m[0] *= 2;
gen();
} else
puts((char *) m);
}
int main() { gen(); return 0; }
```
從這個遞迴式子可以看出，把 m[0] 乘上 $2^{96}$ 後再把它印出來，對 double 的作用剛好就是直接在 Exponent 加上 96，所以
把 `0x432B2B767265736A` 轉換成 binary 後會得到
```
s Exponent Mantissa
0 10000110010 1011001010110111011001110010011001010111001101101010
```
在 Exponent 加上 96，也就是 00001100000 ：
```
0 10000110010 1011001010110111011001110010011001010111001101101010
+ 00001100000
------------------------------------------------------------------
0 10010010010 1011001010110111011001110010011001010111001101101010
```
再把他轉換成十六進位
`0x492B2B767265736A (big-endain)`
`0x6A736572762B2B49 (little-endain)`
最後再轉成 String 就會是
`jserv++I`
:::success
延伸題目:
1. 修改程式，允許輸出你的 GitHub 帳號名稱
2. 承上，修改 gen() 函式，透過特定的轉換，讓 `m[]` 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼
3. 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
:::
1. 我的 github 帳號是 BroLeaf 共7個 char ，轉換成 ascii code ，用 little-endian 表示的話就是如下，第一個 byte 是 NULL
`006661654C6F7242`
再轉成 double 然後把它印出來
```clike=
puts((char *) &(double []){9.95963171225462228399162147146E-307, 96});
//output:BroLeaf
```
2. 我姓葉，要輸出Yeh，為了要輸出更短的字串，我必須把Exponent 的 bit 清掉，也就是除 $2^6$ 。
但是在清掉的那一刻，就會從 denormalized 變成 normalized 會有計算偏移量的問題， Mantissa 就會跟著改變，所以只好除 $2^5$ ，雖然會導至多印出 'DEL' 這個 char 不過不影響實際上的結果。
為了使 Mantissa 符合需求，我在 puts 前面扣掉兩者的差 (diff)
```
BroLeaf :0 00000000110 0110011000010110010101001100011011110111001001000010
masked :0 00000000000 0110011000010110010101001100011011110111001001000010
Yeh :0 00000000000 0000000000000000000000000000011010000110010101011001
diff :0 00000000000 0110011000010110010101001100000001110000110011101001
```
```clike=
} else {
m[0] -= ( 8.87311048192124586227196764917E-309 ) ;
puts((char *) m);
return ;
}
//output:Yeh
```
3. 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
* 每 8 個 bytes 為一個單位，然後把bytes 按相反順序存入，例如要印出`BroLeaf`
little-endian 要存入 `faeLorB`
big-endian 則是要存入 `BroLeaf`
Sign in with Wallet
Connect another wallet