HackMD
D06: c-review
contributed by < e94046165 >
第 4 週測驗題
測驗 1
首先分別解出 FuncA、B、C 的功能：
1. FuncA 功能
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;
}
If 處理的是當串列為空的時候的動作，因此直接跳到第九行進行觀察，可以看到使用了 *last 指向 *start 的前一個，也就是最後一個節點。而 new_node 插入的位置可由 new_node->next = *start 判斷出是串列末端。13~15行就是處理因應在串列末端插入節點改變的指標。
Ans: (e) 建立新節點，內容是 value，並安插在結尾
2. FuncB 功能
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;
}
FuncB 乍看之下跟 FuncA 的功能很像，但是它沒有處理 *start 為空的情況，因此很直覺的認為它包含了決定開頭的功能。第八行正好驗證了這個直覺。
Ans: (d) 建立新節點，內容是 value，並安插在開頭
3. FuncC 功能
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;
}
這個函式除了指派給 new_node->data 的 value1 外還多了一個參數 value2，5、6 行用來在串列中找出 data == value2 的 Node。找到之後第八行 temp->next = new_node 也就是將新的節點插入到 data == value2 的節點之後。
Ans: (e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1
但這個 Function 沒有防呆機制，也就是沒有考慮串列中沒有 data == value2 的情況，當此情況發生時，while 迴圈將沒辦法達到終止條件
4. Traversal in forward direction 輸出結果
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;
}
main() 中執行了五次插入，最後形成的串列為
48->51->63->72->86
Traversal in forward direction 做的事情是：
for (; temp->next != start; temp = temp->next)
printf("%d ", temp->data);
從 start 往後走訪串列並輸出，直到走訪到最後一個節點為止（temp->next == start）
因此依序輸出 48 51 63 72 86
5. Traversal in reverse direction 輸出結果
for (temp = last; temp->prev != last; temp = temp->prev)
printf("%d ", temp->data);
從 last 往前走訪串列並輸出，直到走訪到第一個節點為止（temp->prev == last）
輸出結果： 86 72 63 51 48
測驗 2
1. FuncX 的功能
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
for 迴圈的的初始值令 node = head 的下一個，終止條件則為 node = head 或 node = node->next 為 NULL，每一次都會執行 data++ 的敘述，但由於 data 只有 call by value 所以不論在此 Funcx 裡對 data 做什麼操作，從 FuncX 看到的都還是原本的 data 的初始值 0。(第一次作答的時候被騙了…直到看到最後那題答案的選項沒有足夠大的值才發現)
最後是 FuncX 的回傳值 return node - head 在 for 遇到的終止條件是 node = NULL 的時候回傳值是 非0 而當遇到的終止條件是 node = head 時，回傳值則是 0因此 FuncX 可以用來判斷串列是否為環狀串列。
Ans: (e) 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值
p.s. 沒有計算走訪的節點數的功能。
接著進入 main() 裡頭觀察串列建立與判斷是否為環狀：
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;
}
上列 3~7 行建立一個如下的串列
3 0
4 0->1
5 0->1->2
6 0->1->2->3
7 0->1->2->3->4
上面的數字是每個結點的 data 值，0 是 head 的 data 值，此時的串列並非環狀，因此第 8 行 FuncX(head, &count) 的回傳值是非 0 所以結果是 K1 = Yes
head->next->next->next->next = head;
第九行將本來第四個 node (head為第一個)的 next 指標指向 head 至此串列變成
->0->1->2->3-
|___________|
現在再跑一次 FuncX ，由於輸入的串列是環狀串列，所以回傳值 = 0 ，K1 = No
下兩行敘述：
head->next->next->next->next->next = head->next;
printf("K3 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");
延續剛剛的結果 head->next->next->next->next = head 因此
（head->next->next->next->next)->next = head->next 等同於
head->next = head->next 也就是說串列沒有做任何改變，K3 = 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);
因為 head = (head->next->next->next->next)->next->next->next->next
所以上面第1行敘述等同於 head->next = head
至此串列剩下一個指向自己的 head ，仍舊是 circular list 而 data 值 = 0，也就是 K4 = No , K5 =0
最後是 count，因為在 FuncX 裡是 call by value 不是 call by reference 所以 count 仍等於初始值 0。
第 5 週測驗題 (上)
測驗 1
考慮以下程式碼，推敲其作用 (選出最符合行為的描述)
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
將 Func32 改寫為以下功能等價的程式碼:
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;
}
1. Func32 的功能
Func32 會不斷的 recursive call 自己，並且每一次都將參數 x 向右 shift 一位，直到 x = 0 則會回傳 32。最後傳回的值為 32 - 遞迴呼叫的次數 -1，遞迴呼叫的次數又取決於 x 向右 shift 幾次會等於 0，也就是最高位的 1 所在的 bit 數+1，
可以決定出這個 function 的功能是計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
2. M1、M2、M3=?
在解此題的時候參考了 rex662624 的共筆，
他提到只要加上 if(x>>31==1)retrun 0 就可以刪除
第九行的 n = n - (x >> 31);
一開始我也以為這行只是處理開頭沒有 0 的情況，但是發現只是這樣的話這個函式根本無法回傳偶數的 n。
這題第一次在作答的時候是代入邊界值來取得 M1、M2、M3 的值，但這其實是偷吃步，要是這串 code 實際上跑不出正確的結果或是有什麼陷阱應該很容易 GG 所以這次試著從頭理解這串程式碼的觀念：
首先確定所有情況(開頭有0~32)個 0 的情況都被妥善考慮，
當 x = 0 時由第3行的 if 判斷式成立回傳 32
開頭有
1 個 0 所有 if 判斷式均不成立 n = 1 ==>M1,M2,M3<31
2 個 0 第八行的 if 判斷式必須成立(才可能使 n = 2) ==>M3 = 30
…
如此推下去可以得出 M1 = 24, M2 = 28, M3 = 30;
測驗 2
Func64 的作用為？
union u_qword {
struct {
uint32_t low;
uint32_t high;
} dwords;
uint64_t qword;
};
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);
}
這題相對來說挺簡單的，先將一個 64 bits 的數拆成 hi = 左邊的 32 bits，與 lo = 右邊 32 bits，若 hi 不為零就不用考慮 lo 為何，只要 return Func32(hi) 就好，當 hi == 0 表示開頭的 32 個位元全為 0，return 32 + Func32(lo) 如此一來便能計算開頭有幾個 0
Ans: © 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64
do_udiv32 的作用為？
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;
}
首先，由函式名稱 do_udiv32 與 argument dividend, divisor 等等可猜出這是一個除法的 function。那麼它是採取什麼樣的方式呢？
稍微瀏覽了一下，發現這與我之前作除法的想法有些相似第2周作業==>不斷將被除數與除數對齊並相減，細看程式碼可以發現
一開始 mask = 除數與被除數 Leading 1 相差的位數，
在利用 mask 將 divisor 與 dividend 對齊後(第 8 行)
mask = 1U << mask 之後用來控制商數的位數。
之後的 while 迴圈內的動作是：
11 若 dividend > divisor :
12 dividend 減去 divisor
13 將原來的商數加上對應位元的`1`
15 divisor right shift 一位
直到 商數夠長 or dividend==0(被整除)為止
最後將餘數儲存
所以 P1 應為 mask>>=1
理解了 do_udiv32 後繼續往下到 udiv64
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;
}
這個 function 與 do_udiv32 的概念基本上一樣，只是拓展成 64 位元版本並加上一些 do_udiv32 沒有的偵錯敘述，如第 7 行 防止除以 0 的判斷式、第 22 行 若除數被除數皆小於等於 32 位元 就丟給 do_udiv32 做。
還有，udiv64 除了 mask 以外還宣告了新的變數 bits 來紀錄商數的位數，並以它作為終止 while 迴圈的條件，也就是P2 = bits-- 。這部份與 32 位元版本的想法其實一樣，但是可讀性變高了(一個變數如果擔任太多角色會令可讀性變低，我第一次作答是看得霧煞煞啦…)
最後來到 main()
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;
}
首先是 P3 和 P5，看了其他人的共筆，發現這兩個數是為了讓後來的 putchar 可以輸出正確的數字。當 P3 = P5 = 48 (ASCII 0)可以使數字輸出正確，但是答案給的是 0x31 也就是 49。本來以為是自己哪裡想錯了，但是實際上跑過發現似乎是答案給錯了？
//P3 = P5 = 48
root@acnes-X550JX:~#./div
3405691582
//P3 = P5 = 49
root@acnes-X550JX:~#gcc -o div div.c
root@acnes-X550JX:~#./div
45167:2693
可以看到當 P3 = P5 = 49 時，輸出的字元超出了數字的範圍，而出現了 ":"，所以可以斷定P3 = P5 = 0x30 才對
第 5 週測驗題 (中)
測驗 1
已知在 x86_64 架構，以下程式碼的執行輸出是 jserv++C:
#include <stdio.h>
int main() {
puts((char *) &(double []){ 3823806048287157.0, 96 });
}
一開始先試著理解這段又短又奇妙的東西，從這一段程式碼不難猜出這是將一個設計好的 double 強制轉型成字串 char* 這串 double 用二進位表示是：
01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010
又 sizeof(char) = 1 bytes 所以會將這 64 個 bits 拆成 8 個 8 bits 的字元來讀取，查了 ASCII 表後可以發現上列了數字依序代表了 C++vresj，但這是 big-endian 的規則下的輸出，在 little-endian 下則會是 jserv++C。
有了上面的概念之後再來考慮以下程式碼，假設 puts 函式總是可正確運作，那麼程式輸出為何？
#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; }
可以看到 gen 是個遞迴呼叫的 function，最終將本來的 double *296，那麼這串新的 double 再用 (char*)強制轉型會輸出什麼呢？
這牽涉到 IEEE 754 所規範的浮點數表示法，當一個浮點數乘上 2n 實際上只有表示 exponent 的 bits 會更動而已，以下是經過計算之後的數
01001001 00101011 00101011 01110110 01110010 01100101 01110011 01101010
粗體的部份為改變的位元，查 ASCII 表可得到新的字串為：
jserv++I
延伸題目
修改程式，允許輸出你的 GitHub 帳號名稱
我的 id 為 e94046165 ，因為超過 8 個字元，由上述的論述可以知道，一個 double 因為只有 64 bits 所以強迫轉型成 char* 時最多只能表示 8 個字元。因此必須把 id 拆成兩個 double 來表示。但在與 blake11235 討論的時候發現了一些問題：
若用 double 表示 8 個字元的字串，在 printf 輸出的時候可能因未讀到 "\0" 而使輸出結果出錯，下面為例子：
int main(){
double x[] = {1.17767461839090865360653786975E-47 };
double y[] = {2.6185479229586066841358146022E-322 };
printf("%s", (char *) x);
printf("%s", (char *) y);
printf("\n");
return 0;
}
其中 double x 以二進位表示為
00110110 00110001 00110110 00110100
00110000 00110100 00111001 01100101
由高位往低位元每 8 bits 輸出為 6164049e
其中 double y 則是
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00110101
由高位往低位元每 8 bits 輸出為 NULL…NULL 5
接著 Printf 以 little endian 規則讀取並輸出的話應該會得到 e94046165
但以下為輸出結果：
e9404616�@5
在兩個輸出之間出現了不屬於兩個 double 裡的資料，這代表了兩件事：
1.x 與 y 的記憶體位置不連續
2.printf 因為沒有讀到 NULL 所以輸出超過 x 所涵蓋的記憶體範圍
以下驗證這兩個想法：
首先是先分別 printf 出 x 與 y 的記憶體位置
int main(){
double x[] = {1.17767461839090865360653786975E-47 };
double y[] = {2.6185479229586066841358146022E-322 };
printf("&x =%p\n", &x);
printf("&y =%p\n", &y);
printf("%s", (char *) x);
printf("%s", (char *) y);
printf("\n");
return 0;
}
輸出結果：
root@acnes-X550JX:~/tests#./aaaa
&x =0x7ffc54823830
&y =0x7ffc54823840
e9404616�@5
果然，可以看到兩者差了 8 bytes(x 的結尾到 y 的開頭之間)
然後試著加入以下程式碼，一個一個 bytes 印出字元：
p = &x;
for(i=0; i<24; i++){
printf("%p ", p);
putchar(*p++);
printf("\n");
}
結果
&x =0x7ffe6a4dd5d0
&y =0x7ffe6a4dd5e0
e9404616�@5
0x7ffe6a4dd5d0 e
0x7ffe6a4dd5d1 9
0x7ffe6a4dd5d2 4
0x7ffe6a4dd5d3 0
0x7ffe6a4dd5d4 4
0x7ffe6a4dd5d5 6
0x7ffe6a4dd5d6 1
0x7ffe6a4dd5d7 6
0x7ffe6a4dd5d8 �
0x7ffe6a4dd5d9
0x7ffe6a4dd5da @
0x7ffe6a4dd5db
0x7ffe6a4dd5dc
0x7ffe6a4dd5dd
0x7ffe6a4dd5de
0x7ffe6a4dd5df
0x7ffe6a4dd5e0 5
0x7ffe6a4dd5e1
0x7ffe6a4dd5e2
0x7ffe6a4dd5e3
0x7ffe6a4dd5e4
0x7ffe6a4dd5e5
0x7ffe6a4dd5e6
0x7ffe6a4dd5e7
在印出 x 的時候居然印了不在 x 記憶體空間裡的東西
(註：0x7ffe6a4dd5d9 裡有一個亂碼，無法複製貼上但該記憶體位置不為空)
那麼該如何解決呢？
只要使 x 與 y 記憶體位置相連就行了：
int main(){
double x[] = {1.17767461839090865360653786975E-47,2.6185479229586066841358146022E-322 };
printf("%s", (char *) x);
printf("\n");
return 0;
}
root@acnes-X550JX:~/tests#./aaaa
e94046165
那為什麼範例沒有遇到這個問題呢？
char *p;
int main(){
double x[]= { 3823806048287157.0, 96 };
puts((char *) &x);
printf("\n");
p = &x;
for(i=0; i<15; i++){
printf("%p ", p);
putchar(*p++);
printf("\n");
}
return 0;
}
稍微修改 code 讓它 printf 出整個 array 裡的 data:
輸出
jserv++C
0x7ffceeeb2380 j
0x7ffceeeb2381 s
0x7ffceeeb2382 e
0x7ffceeeb2383 r
0x7ffceeeb2384 v
0x7ffceeeb2385 +
0x7ffceeeb2386 +
0x7ffceeeb2387 C
0x7ffceeeb2388
0x7ffceeeb2389
0x7ffceeeb238a
0x7ffceeeb238b
0x7ffceeeb238c
0x7ffceeeb238d
0x7ffceeeb238e X
可以看到因為 array 中第二個值為 96 所以前 7 個 bytes 皆為零(ASCII 96 = X)，而在puts 的時候 puts 出最後一個字元©就遇到了 NULL 因此不會繼續 puts 出其他不該出現的結果。不知道這部份是不是在撰寫程式碼的時候就考慮到的，不過就此看來如果對不同的 datatype 做強制轉型，而不考慮其他 function 的運作機制的話，可能會有不堪設想的後果。
第 5 週測驗題 (下)
計組太爛。。。。。先緩緩
