2018q1 Homework3
D06:c-review
===
contributed by<`blake11235`>
---
## 第 4 週測驗題
### 測驗`1`
這提主要是在考 link list 的觀念，直接來看程式碼
* FuncA
```=c
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;
}
```
若一開始的 `*start` 是空的，便會 malloc 一個新的 node 並把 value 輸入，next 和 prev 都指向自己，最後把自己的位置丟給 `*start`
若一開始已經有存在的 node，會創一個新的`new_node`並把他聯結在`start`的前一個位置，把 new_node 的 next 指向 start，prev 指向 last
所以答案`是建立新節點，內容是 value，並安插在結尾`
* FuncB
```=c
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;
}
```
也是一樣建立一個 new_node，將其按插在目前 start 的前一個位置，但最後將 start 指向這個 new_node
所以答案是`建立新節點，內容是 value，並安插在開頭`
* FucnC
```=c
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，其值為 value1，然後依序從 start 開始搜尋值為 value2 的 node，找到了之後將他按插在 temp 的後面
所以答案是`找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1`
* 程式輸出
* 首先是建立資料
```=c
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;
}
```
48 -> 51 -> 63 -> 72 -> 86 ->
start 指向 48
* 再來是印出數字
```=c
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");
}
```
`Traversal in forward direction`
從 start 開始直到最後一個的下一個又是 start，所以答案是 **48、51、63、72、86**
`Traversal in reverse direction`
倒著輸入，起始是 start 的 prev，所以答案是 **86、72、63、51、48**
---
### 測驗`2`
* FuncX()
```=c
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 的下一個開始，然後一直往 next 移動，直到 node 為 NULL 或者 node 回到 head
最後 `return node - head` 使用來判斷是否為 circle link list，如果是的話回傳值會為 0
所以答案是`判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值`
* K1
```=c
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");
```
node_new() 這個函會建立一個結點，並且將其 next 指向 NULL
上述程式會得到 0 > 1 > 2 > 3 > 4 > NULL
所以 FuncX() 會回傳**非零值**，因為此 link list 並非 circle ~我就是死在這裡~
因此會 print 出 "Yes"
* K2
```=c
head->next->next->next->next = head;
printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
```
這個段程式將原本第 4 個 node->next 所指向的 第 5 個 node 改成指向 head
0 > 1 > 2 > 3 > 0
第 5 個 node 4 也就被 leak
此為 circle link list，所以 print 出 "No"
* K3
```=c
head->next->next->next->next->next = head->next;
printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
```
此處的 link list 沒有變，還是一樣
所以 print 出 "No"
* K4
```=c
head->next = head->next->next->next->next->next->next->next->next;
printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
```
第一個 node 的 next 指到第一個 node，所以變成 0 > 0 ，還是 circle
所以 print 出 "No"
* K5
```=c
printf("K5 >> %d\n", head->next->data);
```
第 1 個結點的值是 0
* Count
根據 FuncX() 裏面有一個 `data++` 照理來說應該每走訪一個點就要加一，但仔細觀察 FuncX()
```=c
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
```
可以發現宣告的 `int *data` 是位址，使用的是 pass by address，但後面卻對位置做 ++ ，所以功用沒有達到。若直接去 compile 會得到 count = 0 跟一開始宣告的一樣
若要更改應該改成
```=c
- data++;
+ *data++;
```
---
## 第 5 週測驗題(上)
### 測驗`1`
* 原程式
```=c
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
首先是一個輸入的 32 位元 x，先看極端例子，若 x = 0，可接得到答案 32 ，從這個角度去設想題目應該是要判斷 x 總共有幾個 0，結果是錯的哈哈
程式會一直進行向右移 1 bite 直到全部為 0 ，得到 32 之後一直返回 -1 ，可以得到從右邊數來的最後一個 1 是第幾個
所以答案是
`計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32`
* 等價程式
```=c
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 行，若 x = 0，直接回傳 32
若 x 向右移動 16 ，也就是 x 的左半部份，全是 0 的話，n 加 16，x 左移 16 繼續判斷右半部份
接下來要 x 向右移動 16+8 ，判斷最高的前 8 位是否為 0 ，若是的話左移 8 使傷胃判斷的部份移動到最高位元
再來也是一樣右移 16+8+4，最後是位移 16+8+4+2
可以得出 M1 = 24 ， M2 = 28 ， M3 = 30
---
### 測驗`2`
* Func64
```=c
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);
}
```
先將 uint64_t 拆成各 32 bits 的 lo, hi ，然後個別做 Func32() 完成其開頭有幾個 0 ，若 hi 不為 0 ，直接輸出 Func(hi) ，為 0 的話，需要對 Func(lo) 多加上前 32 個 0，所以答案是
`計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64`
:::info
TODO: inline http://gnitnaw.github.io/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/2016/06/14/C_inline.html
:::
* do_udiv32
```=c
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;
}
```
可以判斷出這項函式是在處理 32 位元的除法
這除法的概念：
```flow
st=>start: 確認 divisor <= dividend
e=>end: 剩餘的 dividend 輸入 res 內的餘數
op1=>operation: 將 divisor & dividend 對齊
op2=>operation: 將 mask 設成跟 divisor 的最高位一樣
op3=>operation: dividend - divisor
op4=>operation: mask 輸入商數 q
op5=>operation: divisor & mask 右移 1
cond=>condition: 是否可減？
cond2=>condition: 被除數除完了或除數為零了
st->op1->op2->cond->op5->cond2
cond(yes)->op3->op4
cond(no)->op5
cond2(yes)->e
cond2(no)->cond
```
可以知道 P1 是 mask>>=1
* udiv64
```=c
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;
}
```
這斷程式只是把 udiv32() 改成 64 位元版本，所以概念一樣
差別在於多了處理 `divisor 為 0`、`divisor = dividend`、`divisor > dividend` 情況
並且將位元數小於 32 的情況給 Func32() 處理
答案的 bits-- 跟上述的 mask 有著一樣的概念，只不過這裡分開來表示而已
* main
```=c
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;
}
```
:::warning
complex
:::
---
## 第 5 週測驗題(中)
```=c
#include <stdio.h>
int main() {
puts((char *) &(double []){ 3823806048287157.0, 96 });
}
```
x86_64 架構之下，可以印出 `jserv++C`
分析以下程式
```=c
#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; }
```
首先， double 的數值 3823806048287157.0 用二進位表示的話是
`01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010`
程式是將 double 的型式強迫轉換成 char 分別以 4 位元一個個輸出，又加上電腦是以 little-endian 輸出，所以看起來是 `C++vresj` 輸出會是 `jservC++`
透過 IEEE-754 的表示法
| s | exp | frac |
|:--:|:--:|:--:|
|0| 1000011 0010 | 1011 00101011 01110110 01110010 01100101 01110011 01101010 |
|0| 1001001 0010 | 1011 00101011 01110110 01110010 01100101 01110011 01101010 |
gen() 會使 m[0] 一直乘 2 乘 96 次，也就是在階碼的部份 + 96
1001001 0010 + 96 = 1001111 001
01001001 001 透過 ASCII 可得到 `I`
### 好玩的延伸 輸出你的 GitHub 帳號名稱
|字元|ASCII 2進位|16 進位|
|:--:|:--:|:--:|
|b|0110 0010|62|
|l|0110 1100|6C|
|a|0110 0001|61|
|k|0110 1011|6B|
|e|0110 0101|65|
|1|0011 0001|31|
|1|0011 0001|31|
|2|0011 0010|32|
|3|0011 0011|33|
|5|0011 0101|35|
我的 ID 超過了 8 個字元，所以一個 double 不夠用，那剩下的就在叫一個 double
所以就變成 `211ekalb` 和 `53`
```=c
#include <stdio.h>
int main(){
printf("%s%s",
(char *) (double []){6.37722099392140580485191278765E-67},
(char *) (double []) {6.72868003071193668514069039007E-320}
);
return 0;
}
```
但是...卻產生了一坨奇怪的符號
```
blake112�@35
```
可是個別表示都沒有問題
```=c
#include <stdio.h>
int main(){
printf("%s",
(char *) (double []) {6.37722099392140580485191278765E-67}
//, (char *) (double []) {6.72868003071193668514069039007E-320}
);
return 0;
}
blake112
```
```=c
#include <stdio.h>
int main(){
printf("%s",
/*(char *) (double []) {6.37722099392140580485191278765E-67}, */
(char *) (double []) {6.72868003071193668514069039007E-320}
);
return 0;
}
35
```
正當我在懷疑人生的時候，突然！！
```=c
#include <stdio.h>
int main(){
printf("%s%s",
(char *) (double []) {6.37722099392140580485191278765E-67, 0},
(char *) (double []) {6.72868003071193668514069039007E-320, 0}
);
return 0;
}
```
大家來找碴
```=c
- {......}
+ {......, 0}
```
**簡單來說，如果就是陣列宣告的問題**
我將程式改成依序印出 1 byte 與其位置的型式，從兩個陣列的開頭印出20個
```=c
#include <stdio.h>
int main(){
double x[] = {6.37722099392140580485191278765E-67};
double y[] = {6.72868003071193668514069039007E-320};
char* a = x;
char* b = y;
for(int i=0; i<20; i++){
printf("%p %c\n", a+i, *(a+i));
}
printf("\n");
for(int i=0; i<20; i++){
printf("%p %c\n", b+i, *(b+i));
}
printf("%s", a);
printf("%s", b);
return 0;
}
```
```
0x7ffdb6cc4620 b
0x7ffdb6cc4621 l
0x7ffdb6cc4622 a
0x7ffdb6cc4623 k
0x7ffdb6cc4624 e
0x7ffdb6cc4625 1
0x7ffdb6cc4626 1
0x7ffdb6cc4627 2
0x7ffdb6cc4628 �
0x7ffdb6cc4629
0x7ffdb6cc462a @
0x7ffdb6cc462b
0x7ffdb6cc462c
0x7ffdb6cc462d
0x7ffdb6cc462e
0x7ffdb6cc462f
0x7ffdb6cc4630 3
0x7ffdb6cc4631 5
0x7ffdb6cc4632
0x7ffdb6cc4633
0x7ffdb6cc4630 3
0x7ffdb6cc4631 5
0x7ffdb6cc4632
0x7ffdb6cc4633
0x7ffdb6cc4634
0x7ffdb6cc4635
0x7ffdb6cc4636
0x7ffdb6cc4637
0x7ffdb6cc4638
0x7ffdb6cc4639 �
0x7ffdb6cc463a �
0x7ffdb6cc463b
0x7ffdb6cc463c �
0x7ffdb6cc463d _
0x7ffdb6cc463e �
0x7ffdb6cc463f �
0x7ffdb6cc4640
0x7ffdb6cc4641
0x7ffdb6cc4642 @
0x7ffdb6cc4643
blake112�@35
```
可以發現那個奇怪的符號出現在 `blake112` 後面，由於 printf("%s") 讀取字串的時候必須要有 `\0` 也就是 `0000 0000` 當作字串終止，因此會直接當作字元印出來。
而`35` 後面，我在賦值的時候就給定 0 了，所以不會出現其他字元。
有數種解決方式，但有著奇怪的現象：
* 將陣列都給定第二個值，`double x[2]`，x[0] 為數值，x[1] 會自動為 0 用來當作 NULL 字串的終止。
但照理來說，需要在 `blake112` 後面放 `x[1] = 0 `，`35` 後面的 y[1] 可以不用放，但是...
```
double [] x = {}
double [2] y = {}
0x7ffc45647700 b
0x7ffc45647701 l
0x7ffc45647702 a
0x7ffc45647703 k
0x7ffc45647704 e
0x7ffc45647705 1
0x7ffc45647706 1
0x7ffc45647707 2
0x7ffc45647708
0x7ffc45647709
0x7ffc4564770a
0x7ffc4564770b
0x7ffc4564770c
0x7ffc4564770d
0x7ffc4564770e
0x7ffc4564770f
0x7ffc45647710 3
0x7ffc45647711 5
0x7ffc45647712
0x7ffc45647713
0x7ffc45647710 3
0x7ffc45647711 5
0x7ffc45647712
0x7ffc45647713
0x7ffc45647714
0x7ffc45647715
0x7ffc45647716
0x7ffc45647717
0x7ffc45647718
0x7ffc45647719
0x7ffc4564771a
0x7ffc4564771b
0x7ffc4564771c
0x7ffc4564771d
0x7ffc4564771e
0x7ffc4564771f
0x7ffc45647720
0x7ffc45647721 x
0x7ffc45647722 d
0x7ffc45647723 E
```
代表在 y 陣列的後面放入 0 也可以使 x[0] 後面變成 0 ？？
* 先宣告 y 陣列在宣告 x 陣列
由於**先宣告的陣列後面會出現奇怪符號**，所以讓有 NULL 的 y 陣列先宣告
```
double y[] = {};
double x[] = {};
0x7ffd9ff1ea80 b
0x7ffd9ff1ea81 l
0x7ffd9ff1ea82 a
0x7ffd9ff1ea83 k
0x7ffd9ff1ea84 e
0x7ffd9ff1ea85 1
0x7ffd9ff1ea86 1
0x7ffd9ff1ea87 2
0x7ffd9ff1ea88
0x7ffd9ff1ea89 �
0x7ffd9ff1ea8a
0x7ffd9ff1ea8b
0x7ffd9ff1ea8c
0x7ffd9ff1ea8d �
0x7ffd9ff1ea8e y
0x7ffd9ff1ea8f �
0x7ffd9ff1ea90
0x7ffd9ff1ea91
0x7ffd9ff1ea92 @
0x7ffd9ff1ea93
0x7ffd9ff1ea70 3
0x7ffd9ff1ea71 5
0x7ffd9ff1ea72
0x7ffd9ff1ea73
0x7ffd9ff1ea74
0x7ffd9ff1ea75
0x7ffd9ff1ea76
0x7ffd9ff1ea77
0x7ffd9ff1ea78 �
0x7ffd9ff1ea79
0x7ffd9ff1ea7a @
0x7ffd9ff1ea7b
0x7ffd9ff1ea7c
0x7ffd9ff1ea7d
0x7ffd9ff1ea7e
0x7ffd9ff1ea7f
0x7ffd9ff1ea80 b
0x7ffd9ff1ea81 l
0x7ffd9ff1ea82 a
0x7ffd9ff1ea83 k
```
果真先宣告的 y 陣列後面出現奇怪符號，但不會對整個字串輸出造成影響，但是...
```
double test[] = {0};
double x[] = {};
double y[] = {};
0x7ffed9457250 b
0x7ffed9457251 l
0x7ffed9457252 a
0x7ffed9457253 k
0x7ffed9457254 e
0x7ffed9457255 1
0x7ffed9457256 1
0x7ffed9457257 2
0x7ffed9457258 �
0x7ffed9457259
0x7ffed945725a @
0x7ffed945725b
0x7ffed945725c
0x7ffed945725d
0x7ffed945725e
0x7ffed945725f
0x7ffed9457260 3
0x7ffed9457261 5
0x7ffed9457262
0x7ffed9457263
0x7ffed9457260 3
0x7ffed9457261 5
0x7ffed9457262
0x7ffed9457263
0x7ffed9457264
0x7ffed9457265
0x7ffed9457266
0x7ffed9457267
0x7ffed9457268
0x7ffed9457269 `
0x7ffed945726a A
0x7ffed945726b
0x7ffed945726c e
0x7ffed945726d �
0x7ffed945726e �
0x7ffed945726f �
0x7ffed9457270
0x7ffed9457271
0x7ffed9457272 @
0x7ffed9457273
```
看來不只是第一個宣告的陣列後面會出現怪東西，第二個也會，大概可以推測連續宣告陣列與陣列之間存在某些未知數值...
但...
```=c
#include <stdio.h>
int main(){
double z[] = {5.25663347308138420229098632996E83 };//QQQQQQQQ
double x[] = {6.37722099392140580485191278765E-67};
double y[] = {6.72868003071193668514069039007E-320};
char* c = z;
char* a = x;
char* b = y;
for(int i=0; i<20; i++){
printf("%p %c\n", c+i, *(c+i));
}
printf("\n");
for(int i=0; i<20; i++){
printf("%p %c\n", a+i, *(a+i));
}
printf("\n");
for(int i=0; i<20; i++){
printf("%p %c\n", b+i, *(b+i));
}
printf("%s", a);
printf("%s", b);
return 0;
}
```
我測出來，第一個陣列後面卻沒有出現任何奇怪符號，怎麼第一個又沒奇怪符號了
目前我給自己的解釋，在一區域內連續宣告不同名稱的陣列，之間可能間隔某些記憶體，其值可能有某種特殊規律。
### gen() 修改
我要將`jservC++` 改成 `Tseng`
|C|+|+|v|r|e|s|j|
|--|--|--|--|--|--|--|--|
|||\0|g|n|e|s|T|
在 IEEE-754 當中
|值| s | exp | frac |
|:--:|:--:|:--:|:--:|
|C++vresj|0| 1000011 0010 | 1011 00101011 01110110 01110010 01100101 01110011 01101010 |
|gnesT|0| 1000011 0010 | 1011 00000000 01100111 01101110 01100101 01110011 01010100 |
有更動的只有 frac 部份
0100001100101011001010110111011001110010011001010111001101101010
3.823806048287157E15
0100001100101011000000000110011101101110011001010111001101010100
3.80013430248081E15
3.823806048287157E15 - 3.80013430248081E15 = 2.3671745806347
```=c
#include <stdio.h>
double m[] = {3823806048287157.0, 96 };
void gen() {
m[0] -= 23671745806347;
puts((char *) m);
}
int main() { gen(); return 0; }
```
可以成功輸出 `Tseng`
---
## 第 5 週測驗題(下)
:::info
QQ
:::
Sign in with Wallet
Connect another wallet