# 2020q3 Homework4 (quiz4)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`

## 測驗`1`
下方程式碼會回傳兩個參數的 Hamming distance

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

> In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Hamming distance 的定義是在兩個相同長度的字串裡，共有幾個位置是不一樣的 (一個為 0, 一個為 1)。

從定義不難看出可能會需要用到 XOR ，可以將不同的位元變成 1 ，再算出一共有多少 1 就是所要的 Hamming distance。

---

## 測驗`2`

#include <stdlib.h>

typedef struct {
    int **parent;
    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 - 1] == -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 & (1 << i))
            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);
}

`TreeAncestor` 這個 struct 記錄所有節點的關係以及深度，又從後面的運用可以得知 parent 應為二維陣列，因此 AAA 選 `int **parent`

`parent[i][j]` 所代表的值應是**第 i 個節點的上 j 代祖先**，例如 : parent[5][0] 代表第 5 個節點的上 0 代祖先，也就是第 5 個節點本身；parent[6][2] 代表第 6 個節點的上 2 代祖先，也就是第 0 個節點。

因此得出 `parent[i][j] = parent[parent[i][j-1]][j-1]` 也就是該節點第 j 個祖先應為 "前個祖先的 j-1 個祖先"，若前個祖先為 -1 ，也就是 root ，則第 j 個祖先為 -1

在 `treeAncestorGetKthAncestor` 中，把 `k` 分解成 $2^n+i$，也就是第 $2^n$ 個節點的上 $i$ 個祖先來搜尋，因此 `CCC` 應為 1 << i

---

## 測驗`3`
下方程式碼會在輸入的數字能被 3 整除時印出 "Fizz"；在能被 5 整除時印出 "Buzz"；在能被 3 和 5 整除時印出 "FizzBuzz"；此外，印出該數字。

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

這裡用到了之前的 `is_divisible` 來判斷是否可以整除，並且利用 lenth 來取得字串長度，一共會有三種情況 :
- 2 : 皆不能被整除
- 4 : 能被 3 或 5 其中一個整除
- 8 : 能被 3 和 5 整除

在 `strncpy` 中，利用了 `[(MSG_LEN >> KK1) >> (KK2 << KK3)]` 來取得字串的位置，搭配 lenth 會有四種情況 :
- 8 : 皆不能被整除，會印出 "%u"
- 可以判斷 `KK1` 及 `KK2` 都為 0，應該是 `div3` 或 `div5`
- 4 : 能被 5 整除
- 可以判斷 `KK1` 或 `(KK2 << KK3)` 為 1
- 0 : 能被 3 或 15 整除
- `MSG_LEN` 被移動了 4 bits 以上

這裡會讓 `KK1` 是 `div5`，在 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 是 4 的情況下剛好移動 1 bit

在 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 是 0 的情況下會選擇將 `KK2` 為 2 ；`KK3` 為 `div3` ，如此才能在被 3 整除時移動 4 bits

---

## 測驗`4`
下方程式碼實作加速整數除法運算

#include <stdint.h>
#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
    CASES
}

可以把所有數字都看成是 $2^n\times k$ ，這裡利用 `int __builtin_ffs (int x)` 來計算這個 $n$ 是多少。

第 5, 6 行將除數與被除數最大的 $2^n$ 先處理掉，然後再處理剩下的數字。

因此 case 裡面就是處理除了 2 之外的質數