# 2020q3 Homework4 (quiz4)
contributed by < `CW-B-W` >

###### tags: `sysprog2020`

## Outline
[TOC]

## 測驗`1`
### hammingDistance
* OP = `^`
* xor 會將 x 與 y 間相同的 bits 設為 `0` ， 不同的 bits 設為 `1`
* 再利用 popcount 算出 x 與 y 間有幾個不同的 bits 即可

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

#### [Leetcode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)

## 測驗`2`
### LeetCode 1483. Kth Ancestor of a Tree Node
* 倍增法求 LCA
* 此法可用來輔助找尋 [`Second Minimum Spanning Tree`](https://sites.google.com/view/ntpuprog/%E8%AA%B2%E7%A8%8B%E8%B3%87%E6%BA%90%E8%88%87%E7%B7%B4%E7%BF%92%E6%B8%85%E5%96%AE/2019/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A8%B9/%E6%AC%A1%E5%B0%8F%E7%94%9F%E6%88%90%E6%A8%B9)
* 主要概念：我的 `第 2^k 個 parent` 的 `第 2^k 個 parent` ， 就是我的 `第 2^(k+1) 個 parent`
* 本質上為 `DP (Dynamic Programming)`
* AAA = `int **parent`
* 由 `line 17` 可知 parent 被當作 `2D-array` 使用
* BBB = `(-1)`
* 此處實作找尋 `我的第 2^j 個 parent`
* 情況一 : `我的第 2^(j-1) 個 parent` 不存在 (i.e. 超出 root) ， 則 `我的第 2^j 個 parent` 也不存在
* 特判此狀況是為了防止

                obj->parent[obj->parent[i][j - 1]][j - 1];

變成

                obj->parent[-1][j - 1];

導致出錯
* 情況二 : `我的第 2^(j-1) 個 parent` 存在， 則 `我的第 2^j 個 parent` 為 `我的第 2^(j-1) 個 parent` 的 `第 2^(j-1) 個 parent`
* CCC = `1 << i`
* `求 k 個 parent`
* 先舉例 `k = 5`
* `第 5 個(3'b101) parent` 為 `第 1 個(3'b001) parent` 的 `第 4 個(3'b100) parent`
* 由上例可知，將 k 表示為多個 `第 2^i 個 parent` 的組合，可快速利用 `parent[][]` 求出 `第 k 個 parent`

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

### 延伸問題 `2` - 減少記憶體浪費

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

    int max_level = 32 - __builtin_clz(n) + 1;

    obj->parent = malloc(max_level * sizeof(int *));

    /* obj->parent[j][i]: The (2^j)-th ancestor of i */
    obj->parent[0] = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        obj->parent[0][i] = parent[i];

    for (int j = 1;; j++) {
        obj->parent[j] = malloc(n * sizeof(int));
        /* cnt is used to count the number of nodes who have the (2^j)-th ancestor */
        int cnt = 0;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[j][i] = obj->parent[j-1][i] == -1
                                    ? -1
                                    : obj->parent[j-1][obj->parent[j-1][i]];
            if (-1 != obj->parent[j][i]) cnt++;
        }
        /* If none node has the (2^j)-th ancestor, we don't need to go deeper. */
        if (!cnt) break;
    }

    obj->max_level = max_level - 1;
    return obj;
}

## 測驗`3`
### FizzBuzz
* KK1 = `div5`
* 用湊得強行湊出來
* KK2 = `div3`
* 用湊得強行湊出來
* KK3 = `2`
* 用湊得強行湊出來

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

## 測驗`4`
### PAGE_QUEUES
* CASES = {`3`, `5`, `7`}
* `CASES` 裡的數字 `Least Significant Bit` 必為 `1`
* 因為 `divident >>= ffs32(divident)` 將 trailing zeros 都移除了

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