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

# 測驗 1 - Hamming Distance

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

## 程式原理
Hamming Distance 是要計算兩串二進位字串不同的地方有幾個，也就是計算 XOR 之後 有幾個 1
## 不使用 gcc extension 的 C99 實作程式碼

int hammingDistance(int x, int y) {
    x=x^y;
    unsigned count=0;
    while(x){
        count++;
        x=x&(x-1);
    }
    return count;
}

[參考資訊](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html)

# 測驗二-Kth Ancestor of a Tree Node

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

## 程式碼解析

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

可以從這一行看出 `parent` 為 pointer to pointer 的 type

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

`max_level`是紀錄現在這個tree當中最大的level數為多少

將 `obj->parent` 做成二維陣列，`obj->parent[n][max_level]` 並將所有值初始化成 `-1`

( -1 表示 no ancestor 的意思)

for (int i = 0; i < parentSize; i++)
    obj->parent[i][0] = parent[i];

`parent[i]` 存放的是 node~i~ 父親的位置

並把`obj->parent[i][0]` 用來存放 node~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]];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
}

目的: **設置 obj->parent 的 element**

# 測驗3-FizzBuzz

**從 1 數到 n**
* 如果是 3的倍數，印出 “Fizz”
* 如果是 5 的倍數，印出 “Buzz”
* 如果是 15 的倍數，印出 “FizzBuzz”
* 如果都不是，就印出數字本身

**可以觀察到:**

* 整數格式字串 "%d" : 長度為 2
* "Fizz" 或 "Buzz" : 長度為 4
* "FizzBuzz" : 長度為 8

#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 >> div5) >> (div3 << 2)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

**程式解說**

`div3`、`div5` 分別可知道 `i` 是否為 3 或 5 的倍數
* 是，為 1
* 否，則為 0

這個概念在quiz2有碰過

**`length`則是根據我們觀察，判斷是不是3或5的倍數進行 operator 的平移**

| `div3` | `div5` | `length` | ( 8 >> div5) >> (div3 << 2) |
|:------:|:------:|:--------:|:-----------------------------------:|
| 1 | 0 | 4 | 0 |
| 0 | 1 | 4 | 4 |
| 1 | 1 | 8 | 0 |
| 0 | 0 | 2 | 8 |