2018q1 Homework3 (c-review)

contributed by < BroLeaf >

tags `BroLeaf`

第四週測驗題

測驗 `1`

解題
















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

可以看出 FuncA 一開始有 if (!*start) 推斷出這是給第一次 call 用的，直接 malloc 一塊記憶體、設完 node 就 return 了。
後面自然就是第二次以上 call function 用到的部份。
new_node->next = *start(*start)->prev = new_node;
新結點的 next 是 start ， start 的 prev 是新結點，知道這是把新加入的結點塞在最後一個結點後面當作新的最後一個。
FuncA 就是建立新節點，內容是 value，並安插在結尾









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

這段程式碼跟上段程式碼後半不一樣的地方就是 *start = new_node; 他把新結點設為 start ，跟第1題相反。
FuncB 是建立新節點，內容是 value，並安插在開頭












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

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






















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






int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next; node && node != head; node = node->next)
        data++;
    return node - head;
}

終止條件是 node && node != head 當 node 跑到沒有宣告的區域，或是變成 head 時就會終止，可以想成跑一整個 link-list 在多一次 next 就跳出迴圈。
所以如果這不是環狀的 return node - head 就不會是 0 ，相反若是環狀的就會返回 0 。
而 data++ 是 " 指向 data 的 address ++ " 而不是 data 裡面的值去++
所以這裡的答案不是 (f) 而是
(e) 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值


















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

根據程式碼一個個排下來，現在的 link-list 是：
0 -> 1 -> 2 -> 3 -> 4
不是一個環狀的 link-list 所以第一個 FuncX 回傳非0值，所以
K1 是 YES
head->next->next->next->next = head 把最後一個 next 遮住不要看，就會發現其實是指 value 是 3 的結點，把 next 放進去一起看，就是把那個結點的 next 變成 head ，就變成了環狀 link-list
0 -> 1 -> 2 -> 3 -> 0 ->........
FuncX 回傳 0
所以 K2 是 NO
head->next = head->next->next->next->next->next->next->next->next 同樣用上一的看法，連到最後會發現連到 head 變成：
0 -> 0 -> ......
還是環狀的所以 K3 是 NO
head->next 永遠是 head 所以整個結構沒有變
所以 K4 是 NO
head->data = 0
所以 K5 是 0
這題第一題就提到過了，改變的只是在 function 的 local value 的 address 沒有真的改到 data
所以是 0

第五週測驗題(上)

測驗 `1`



uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}

代數字進去是最快的解題方式，
把 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 改寫為以下功能等價的程式碼:











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

知道這個 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 說的二分搜尋法就可以更快理解這個概念。

測驗 2

延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。

Func64 的作用為？
















































































































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

第五週測驗題(中)

測驗 `1`

已知在 x86_64 架構，以下程式碼的執行輸出是 jserv++C:




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

根據題目的意思，宣告一個 double 變數，然後在"不改變其記憶體內容下"強制轉成 char 並輸出，關鍵點就在於 double 變數裏面儲存的到底是什麼東西。

根據 double converter 將
3823806048287157.0 轉換後會變成 0x432B2B767265736A
再把得到的十六進位數字丟到 hex to string converter
0x432B2B767265736A 轉換後會得到 C++vresj

發現跟實際得到的結果是完全相反的，這是因為 x86-64 架構是 little-endian 就是說當我們要存一個 double 數
0x432B2B767265736A
它實際上在記憶體的內容會是
0x6A736572762B2B43
所以用 char 一個 byte 一個 byte 去讀，結果就會是相反的
參考：Big and Little Endian Byte Order

考慮以下程式碼，假設 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; }

從這個遞迴式子可以看出，把 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

延伸題目:

修改程式，允許輸出你的 GitHub 帳號名稱
承上，修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼
如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

我的 github 帳號是 BroLeaf 共7個 char ，轉換成 ascii code ，用 little-endian 表示的話就是如下，第一個 byte 是 NULL
006661654C6F7242
再轉成 double 然後把它印出來



puts((char *) &(double []){9.95963171225462228399162147146E-307, 96});

//output:BroLeaf

我姓葉，要輸出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






    } else {
        m[0] -= ( 8.87311048192124586227196764917E-309 ) ;
        puts((char *) m);
        return ;
    }
//output:Yeh

如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

每 8 個 bytes 為一個單位，然後把bytes 按相反順序存入，例如要印出BroLeaf
little-endian 要存入 faeLorB
big-endian 則是要存入 BroLeaf

2018q1 Homework3 (c-review)

tags BroLeaf

第四週測驗題

測驗 1

解題

測驗 2

第五週測驗題(上)

測驗 1

測驗 2

第五週測驗題(中)

測驗 1

tags `BroLeaf`

測驗 `1`

測驗 `2`

測驗 `1`

測驗 `1`