Try   HackMD

2018q1 Homework3
D06:c-review

contributed by<blake11235>

第 4 週測驗題

測驗1


這提主要是在考 link list 的觀念，直接來看程式碼

  • 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;
}

若一開始的 *start 是空的，便會 malloc 一個新的 node 並把 value 輸入，next 和 prev 都指向自己，最後把自己的位置丟給 *start
若一開始已經有存在的 node，會創一個新的new_node並把他聯結在start的前一個位置，把 new_node 的 next 指向 start，prev 指向 last
所以答案是建立新節點，內容是 value，並安插在結尾

  • 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;
}

也是一樣建立一個 new_node，將其按插在目前 start 的前一個位置，但最後將 start 指向這個 new_node
所以答案是建立新節點，內容是 value，並安插在開頭

  • FucnC
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

  • 程式輸出

    • 首先是建立資料
    ​​​​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

    • 再來是印出數字
    ​​​​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

image

  • 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 的下一個開始，然後一直往 next 移動，直到 node 為 NULL 或者 node 回到 head
最後 return node - head 使用來判斷是否為 circle link list，如果是的話回傳值會為 0
所以答案是判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值

  • K1
    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
    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
    head->next->next->next->next->next = head->next;
    printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");

此處的 link list 沒有變，還是一樣
所以 print 出 "No"

  • K4
    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
    printf("K5 >> %d\n", head->next->data);

第 1 個結點的值是 0

  • Count
    根據 FuncX() 裏面有一個 data++ 照理來說應該每走訪一個點就要加一，但仔細觀察 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;
}

可以發現宣告的 int *data 是位址，使用的是 pass by address，但後面卻對位置做 ++ ，所以功用沒有達到。若直接去 compile 會得到 count = 0 跟一開始宣告的一樣
若要更改應該改成

- data++;
+ *data++;

第 5 週測驗題(上)

測驗1

  • 原程式
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

  • 等價程式
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
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

TODO: inline http://gnitnaw.github.io/程式語言/2016/06/14/C_inline.html

  • 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;
}

可以判斷出這項函式是在處理 32 位元的除法
這除法的概念：

Created with Raphaël 2.2.0確認 divisor <= dividend將 divisor & dividend 對齊將 mask 設成跟 divisor 的最高位一樣是否可減？dividend - divisormask 輸入商數 qdivisor & mask 右移 1被除數除完了或除數為零了剩餘的 dividend 輸入 res 內的餘數yesnoyesno

可以知道 P1 是 mask>>=1

  • 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;
}

這斷程式只是把 udiv32() 改成 64 位元版本，所以概念一樣
差別在於多了處理 divisor 為 0、divisor = dividend、divisor > dividend 情況
並且將位元數小於 32 的情況給 Func32() 處理
答案的 bits– 跟上述的 mask 有著一樣的概念，只不過這裡分開來表示而已

  • 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;
}

complex

第 5 週測驗題(中)

#include <stdio.h>
int main() {
    puts((char *) &(double []){ 3823806048287157.0, 96 });
}

x86_64 架構之下，可以印出 jserv++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

#include <stdio.h>
int main(){
    printf("%s%s", 
    (char *) (double []){6.37722099392140580485191278765E-67},
    (char *) (double []) {6.72868003071193668514069039007E-320}
    );
    return 0;
}

但是…卻產生了一坨奇怪的符號

blake112�@35

可是個別表示都沒有問題

#include <stdio.h>                                     
int main(){
    printf("%s",
    (char *) (double []) {6.37722099392140580485191278765E-67}
    //, (char *) (double []) {6.72868003071193668514069039007E-320}
    );
    return 0;
}

blake112

#include <stdio.h>
int main(){
    printf("%s",
    /*(char *) (double []) {6.37722099392140580485191278765E-67}, */
    (char *) (double []) {6.72868003071193668514069039007E-320}
    );
    return 0;
}

35

正當我在懷疑人生的時候，突然！！

#include <stdio.h>
int main(){
    printf("%s%s",
    (char *) (double []) {6.37722099392140580485191278765E-67, 0},
    (char *) (double []) {6.72868003071193668514069039007E-320, 0}
    );
    return 0;
}

大家來找碴

- {......}
+ {......, 0}

簡單來說，如果就是陣列宣告的問題
我將程式改成依序印出 1 byte 與其位置的型式，從兩個陣列的開頭印出20個

#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

看來不只是第一個宣告的陣列後面會出現怪東西，第二個也會，大概可以推測連續宣告陣列與陣列之間存在某些未知數值…

但…

#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

#include <stdio.h>                                                              
double m[] = {3823806048287157.0, 96 };
void gen() {
    m[0] -= 23671745806347;
    puts((char *) m);
}
int main() { gen(); return 0; }

可以成功輸出 Tseng

第 5 週測驗題(下)

QQ

Last changed by 
 
曾丞平
0
481
Published on HackMD