2020q3 Homework4 (quiz4)

contributed by < StevenChen8759 >

tags: linux2020

相關連結：
2020秋季進階電腦系統理論與實作 quiz4
2020秋季進階電腦系統理論與實作 quiz4 作業說明
2020秋季進階電腦系統理論與實作 quiz4 作業繳交區

測驗一

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

程式碼分析

• 參考附圖中的雙立方體，可發現二進制表示中任兩個數字之間的 Hamming Distance 與表示法中對應位元不同的數量有關。
  • 0110 與 0100 之 Hamming Distance 為 1
  • 0011 與 1100 之 Hamming Distance 為 4
• 因此，我們需透過 XOR 指出位元表示不同的位置為 1，再以 __builtin_popcount() 計算位元為 1 的數量，即為輸入兩數的 Hamming Distance。
  • 故 OP 應填入 ^

測驗二

#include <stdlib.h>

typedef struct {
    AAA;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j + BBB] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (CCC))
            node = obj->parent[node][i];
    return node;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->n; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}

程式碼分析

• 觀察 treeAncestorCreate() 函式內部對 obj 的操作，在 allocate n 個 int * 型別的空間給 obj->parent 之後，再分配 max_level 個 int 的空間，並分別將其位址儲存在先前宣告的 int * 型別的記憶體位址之中。由這樣子的操作，可以知道 parent 是一個二維陣列，故其宣告應為指標的指標。
  • 由上可知，AAA 應填入 int **parent。
• 觀察 treeAncestorCreate()，在第二個 for loop 時，程式將所有 node 的 parent 指派到配置的二維陣列之中；第三個 for loop 則是找出指定的節點是第幾代的 Ancestor。
  • 觀察 25 行針對陣列元素的操作，可知 BBB 為了防止陣列輸入項為負值而造成錯誤，因此應填入 -1

測驗三

#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char *argv[]) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

程式碼分析

• 根據 quiz2 中測驗四所提，我們透過這個函式，得以較低的成本 (不需乘、除運算) 計算出一個數字
  $n$ 是否可指定數字整除。
  • 原理請參考 quiz2 Homework 解說
• 根據上述提示，若 i 可被 3 整除，則 div3 的值為 1；若 i 可被 5 整除，則 div5 的值為 1
• 根據題意，在下列不同的狀況時，應輸出的字串對應如下:
  • 1. 若 i 是 3 的倍數，但不是 5 的倍數，則印出 Fizz
  • 2. 若 i 是 5 的倍數，但不是 3 的倍數，則印出 Buzz
  • 3. 若 i 是 3 與 5 的倍數，則印出 FizzBuzz
  • 4. 若 i 不是 3 與 5 的倍數，則印出 i 之值
• 觀察 strncpy() 陳述句，我們推敲出對應上述情況的輸出值與對應範圍
  • –––––––––––> (FizzBuzz%U\0)
  • 1. start=0, length=4 (Fizz\0–––)
  • 2. start=4, length=4 (––Buzz\0–)
  • 3. start=0, length=8 (FizzBuzz\0–)
  • 4. start=8, length=2 (––––-%u\0)
• 我們可以發現在第 4 種狀況時，字串仍然輸出並保留了可讓 printf() 可辨識的字元，這樣的設計可讓使用者輸出數字。
• length 之值已在第 14 行的程式碼計算出來，而接著需要探討的就是 start 值的問題了，我們根據 (MSG_LEN >> KK1) >> (KK2 << KK3) 之 start 值與上述狀況加以分析 (已知 MSG_LEN 為 8)
  • Case 1. 8 -> 0, Right Shift 4
  • Case 2. 8 -> 4, Right Shift 1
  • Case 3. 8 -> 0, Right Shift 4
  • Case 4. 8 -> 8, Right Shift 0
• 根據上述的觀察，僅有在整除 5 時需右移 1 位元；而當一數可整除 3 時 (包含可同時整除 5)，則須右移 4 位元；並且在 3 跟 5 都不可整除時，右移位元數須為 0。
  • 綜合以上的分析，KK1 應為 div5，KK2 應為 div3，KK3 應為 2，這樣的組合才可滿足要求。