# 2020q3 Homework4 (quiz4)
[toc]
## 測驗 1

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

將上下 exclusive or 後，不一樣的位置會得到 1，再數 1 的數量
`OP = (c) ^`
## 測驗 2

#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;//加一是為了包含 root 的 parent -1
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));

從這裡可以看出
`AAA = (b) int **parent`

        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;//全都先預設為-1
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];//設定各 node 的 parent

    for (int j = 1;; j++) {//因為 parent 已經設好了，所以從 1 開始
        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];

若第 j-1 個 parent 已經不存在，則第 j 個 parent 也不存在
`BBB = (b) (-1)`
第 27 行似乎有錯，應改為`: obj->parent[obj->parent[i][j - 1]][0];`

            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;//把 max_level 改為真正的 level
    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;
}

這邊無法理解 for 迴圈的用意何在
應該可以根據先前建立的 parent 直接回傳
`return obj->parent[node][k-1]` 才對

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

第 46 行的 obj->n 應該是指 node 數，但在 struct 中未定義
## 測驗 3

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

div3 與 div5 為用設計好的 M 快速判斷能否被 3 與 5 整除
接下來要靠 div3 與 div5 與 shift 來控制 "FizzBuzz%u" 的起始位置
div3 為 1 時，須將 8 shift 到 0 ，div3 為 0 div5 為 1 時 shift 到 4 ，否則保持 8
`KK1 = (a) div5`
`KK2 = (d) div3`
`KK3 = (c) 2`
## 測驗 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
}

第 6 行將除數特性中 $2^n$ 先去除，使 LSB 為 1
考慮 `PAGE_QUEUES` 可能的數值，在做過此操作後只剩下 1, 3, 5, 7 這些可能，而如果是 1 不需要計算
`CASES = (b) 3 (d) 5 (f) 7`