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

## 測驗 `1`

LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。即 `1100` 和 `0111` 的 Hamming distance 為 3

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

----

Hamming distance 是計算兩個位元是不同值的數量，故這裡採用 XOR，答案為 (c\)

#### OP = ?
* (a) |
* (b) &
* (c\) ^
* (d) +
* (e) -

## 測驗 `2`

LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 大意:

>給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點

digraph G {
    nodesep=0.4; //was 0.8
    ranksep=0.5;

    {node[style=invis,label=""]; cx_0;
    }
    {node[style=invis, label="", width=.1]; ocx_2; ocx_1;
    }

    {rank=same; 1; 2; cx_0}
    {rank=same; 3; 4; ocx_1}
    {rank=same; 5; 6; ocx_2}

    0 -> 1[arrowhead=none];
    0 -> 2[arrowhead=none];
    1 -> 3[arrowhead=none];
    1 -> 4[arrowhead=none];
    2 -> 5[arrowhead=none];
    2 -> 6[arrowhead=none];

    {edge[style=invis];
                        //Distantiate nodes
                        0 -> cx_0;
                            1 -> cx_0 -> 2;

                        //Force ordering between children
                        2 -> ocx_2;
                            5 -> ocx_2 -> 6;
                        1 -> ocx_1;
                            3 -> ocx_1 -> 4;
    } 
} 

Input:

["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:

[null,1,0,-1]

#### AAA = ?

* (a) int ***parent
* (b) int **parent
* (c\) int *parent

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

由`n * sizeof(int *)`可知答案為 (b)

#### BBB = ?

* (a) (-2)
* (b) (-1)
* (c\) 0
* (d) 1
* (e) 2

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

==25~27行==判斷 `obj->parent[i][j + BBB]` 是否為`-1`
否，則執行

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

j 要變成 j-1 可能會超出邊界，所以 j + BBB 應為檢查 j-1 是否超出邊界的行為，故答案為 (b)

#### CCC = ?

* (a) 1
* (b) i
* (c\) i >> 1
* (d) i >> k
* (e) k << i
* (f) 1 << i

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

==40行==判斷 k 的第 i 個 bit 是不是1，用 1<<i 去判斷，如果 k 為3的話
那答案會是`parent[ parent[node][1 << 0] ][1 << 1]`
故選(f)

----

## 測驗 `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;
}

`is_divisible` 函式在可被 M 整除時回傳1，否則回傳0
`MSG_LEN` 預設是8，表示每個字元都不會被印出來，由於[]裡面的值會決定從 FizzBuzz 裡面第幾個字元開始，而如果是五的倍數一定會印出 Buzz 所以首先判斷的應該是有沒有被5整除，故 KK1 為(a)

剩下的部分則是判斷有沒有被3整除，並且由於8變成4只要右移一位即可，如果要把4變成0則至少要右移3位，所以 KK2 判斷是否有要位移應為 (d) ，KK3 為(c\)，因為如果 KK2 為1代表能被3整除(1<<2)為4，整個值變0，表示都能被印出來，如果只是3的倍數的話長度會是4只會印出前4個

#### KK1 = ?

* (a) div5
* (b) div3
* (c\) 2
* (d) 1

#### KK2 = ?

* (a) 0
* (b) 1
* (c\) 2
* (d) div3
* (e) div5

#### KK3 = ?

* (a) 0
* (b) 1
* (c\) 2
* (d) div3
* (e) div5

----

## 測驗 `4`
考慮以下運算

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) {
    CASES
}

其中 `ffs32(x)` 為 `x` 最後一個1的位置(最右邊為第0個)

#define ffs32(x)  ((__builtin_ffs(x)) - 1)

已知 `PAGE_QUEUES` 範圍如下
- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) × (2^n^), n from 1 to 14

經由 `ffs32` 化簡可知除數剩下的可能只有 1、3、5、7
故選 (b)、(d)、(f)

----