# 2020q3 Homework4 (quiz4)
contributed by < ``yceugene`` >

###### tags: `linux2020` `sysprog2020` `quiz`
[題目連結](https://hackmd.io/@sysprog/2020-quiz4)

## :memo: 目錄
[TOC]
## 測驗 1: 計算 Hamming Distance
* 題意: 計算兩整數 x 與 y 的 Hamming distance (其二進位的每個位元的差)。 例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。

* 利用 __builtin_popcount() 實作 Hamming Distance 程式碼如下:

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

根據 Hamming distance 的定義，就是在計算兩數二進位表示中相同位置但不同數值的位元有多少，因此要對兩數做 `XOR`，再利用 __builtin_popcount 算出 `x XOR y` 有多少個 1 即可，故 `OP = ^`。

## 測驗 2: Kth Ancestor of a Tree Node
* 題意: 回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。 (樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點)
* 條件: 樹上有 n 個節點，編號自 0 到 $n-1$。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。

    typedef struct {
        AAA;
        int max_level;
    } TreeAncestor;

``AAA = int **parent``
* 參考 C 程式實作:

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

* 程式原理:

``TreeAncestor *treeAncestorCreate()``

``int treeAncestorGetKthAncestor()``

``void treeAncestorFree(TreeAncestor *obj)``

* __builtin_clz: 返回左起第一個1之前0的個數

## 3. FizzBuzz
* 題意: FizzBuzz 題目
1. 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
2. 如果是 5 的倍數，印出 “Buzz”
3. 如果是 15 的倍數，印出 “FizzBuzz”
4. 如果都不是，就印出數字本身
* 直覺的實作程式碼:

    #include <stdio.h>
    int main() {
        for (unsigned int i = 1; i < 100; i++) {
            if (i % 3 == 0) printf("Fizz");
            if (i % 5 == 0) printf("Buzz");
            if (i % 15 == 0) printf("FizzBuzz");
            if ((i % 3) && (i % 5)) printf("%u", i);
            printf("\n");
        }
        return 0;
    }

* 利用 bitwise 和上述技巧實作的 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;
    }

## 4. F

整數 PAGE_QUEUES 的數值分佈:
* (1 or 2 or 3 or 4)
* $(5 or 6 or 7 or 8) × (2n)$, n from 1 to 14

原本的除法:

#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;

預先進行計算，從而避免整數除法指令的使用:

#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) {
    case 2: blockidx /= 2;
        break;
}

* 動作說明 :
* __builtin_ffs(x)-1 是二進位數字中, 右方有幾個 '0'. 如:
__builtin_ffs(0x80)-1 = 7
__builtin_ffs(0x08)-1 = 3
__builtin_ffs(0x04)-1 = 2
__buildin_ffs(0x01)-1 = 0
* x >> ffs32(n) 即 x / $2^n$ 因此只需考慮質數 3, 5, 7