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

###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz4)

# 測驗 1 - Hamming Distance

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

## 程式原理
Hamming Distance 是要計算兩串二進位字串不同的地方有幾個。因為 XOR 的操作在不同的地方為 1 ，相同的地方為 0。所以要算 Hamming distance 就是計算 XOR 之後 1 有幾個就對了

## 不使用 gcc extension 的 C99 實作程式碼
想要拿掉 `__builtin_popcount`，最簡單的作法就是把 popcount 實作換掉。

int hammingDistance(int a, int b){
    a ^= b;
    // population count
    a = (a & 0x55555555) + ((a & 0xAAAAAAAA) >> 1);
    a = (a & 0x33333333) + ((a & 0xCCCCCCCC) >> 2);
    a = (a & 0x0F0F0F0F) + ((a & 0xF0F0F0F0) >> 4);
    a = (a & 0x00FF00FF) + ((a & 0xFF00FF00) >> 8);
    a = (a & 0x0000FFFF) + ((a & 0xFFFF0000) >> 16);
    return a;
}

我一樣是先作 XOR ， 只是 popcount 的部份改成用 bitwise operator 實作。
+ 第 4 行相當於把 bit 兩兩配對相加，兩 bit 相加的結果剛好就是 population。
+ 所以現在 32 bit 內相當於有16個數字分別紀錄每個長度 2 的區間分別有幾個 1 。 做完第五行，則可以得到每個長度 4 的區間共有幾個 1 。
+ 依此配推最後就可以獲得 1 總數。

## LeetCode - Total Hamming Distance
這題的技巧就是不要真的兩兩去配對 array 中每個元素。藉由知道 數字總數目 $n$ 以及某個 bit 上 1 的總數 $s$，我們就可以算出這個位置的總 hamming distance $h$:
$$
h = (n-s)s
$$
因為每個 0 配上 1 才會貢獻一個 distance，所以 0 的總數乘上 1 的總數就得到 $h$ 了。

int totalHammingDistance(int* nums, int nums_size){
    int one_count[sizeof(int) * 8] = {0};
    int sum = 0;
    for (int i=0; i < nums_size; ++i) {
        int num = nums[i];
        while (num) {
            one_count[__builtin_ctz(num)]++;
            num ^= num & -num;
        }
    }
    for (int i=0; i<sizeof(int)*8; ++i) {
        sum += (nums_size - one_count[i]) * one_count[i];
    }
    return sum;
}

+ 我用 one_count 來紀錄每一個 bit 位置的 1 的數量。
+ 走訪 `nums` 一次，利用之前 bitmap 用到的技巧來數所有 1 的出現。
+ 最後再把每個位置所貢獻的 distance 加總即可。

如此可達到 100% 速度，但是必須花一個陣列來計數，所以 Memory usage 是 5 %。

# 測驗 2 - Kth Ancestor of a Tree Node

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

## 程式原理
+ 這題程式碼的原理是利用 parent 這個二維陣列紀錄每個元素的第 $2^0, 2^1, ..., 2^m$ 個 parent，其中 $m$ 為 `max_level - 1`。
+ 所以當我們想要找第 k 個 parent 時，假如 $k=7=2^0+2^1+2^2$，則我們只需要找上 1 個 parent，再找此 parent 的第 2 個 parent，最後再找此 parent 的第 4 個 parent 就好
+ 最簡單的實作可能需要走訪 $k$ 次來找到 Kth parent，用此方法只需要 $H(k)$ (hamming weight of $k$) 次走訪。

## 選項選擇
+ 從 11 行，可以看的出來 parent 為一 `int*` 的陣列，所以他的型別應該要是 `int **`
+ 在 25 行，我們正在建表
+ 因為一個節點的第 $2^i$ 個 parent，等於第 $2^{i-1}$ 個 parent 的第 $2^{i-1}$ 個 parent，故 `BBB=-1`。
+ 40 行，我們逐一檢查 k 的 2 進位組成。檢查方式就是 `k & 1 << i`，如此可知道 $k$ 的二進位分解中是否包含 $2^i$，如果有，則我們就需要做一次 `node = obj->parent[node][i];

## LeetCode

typedef struct {
    int **parent;
    int max_level;
    int n;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->n = n;
    obj->parent = malloc(n * sizeof(int *));
    int j;
    int max_level = 32 - __builtin_clz(n);
    
    for (j = 0; j < n; j++) {
        obj->parent[j] = malloc(max_level * sizeof(int));
        memset(obj->parent[j], 0xFF, max_level * sizeof(int));
    }
    for (j = 0; j < parentSize; j++){
        obj->parent[j][0] = parent[j];
    }
    
    int sign=1;
    for (j = 1;j<max_level && sign >= 0; j++) {
        sign = -1;
        for (int i = 0; i < n; i++) {
            if (obj->parent[i][j - 1] != -1) {
                obj->parent[i][j] = obj->parent[obj->parent[i][j - 1]][j - 1];
                sign &= obj->parent[i][j];
            }
        }
    }
    obj->max_level = max_level;
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    for(int i=obj->max_level-1; k && node != -1; i--){
        if (k >> i) {
            node = obj->parent[node][i];
            k ^= 1 << i;
        }
    }
    return node;
}

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

**截圖：**
LeetCode 的趴數常常會波動，所以我跑了幾次大概有一半都能過 75% 門檻。

## 對原程式碼的更動
1. ==4==: 在 `TreeAncestor` 新增 `int n` 這個 member，來正確釋放記憶體。
2. ==13==: `max_level` 改為 `32 - __builtin_clz(n)` ，去掉了 `+1`。 因為根據題目條件 $k \leq n$，所以若 $32-\text{clz(n)} = m$，則 $k$ 的最大 set bit 也只會在第 $m-1$ bit (從 0 算起)。長度 $m$ 的陣列就剛好裝得下 $2^0,2^1,...,2^{m-1}$，所以可以少使用 $n$ 個 `int` 的記憶體。
3. ==17==: 改成用 memset 來初始化全部為 -1。
4. ==quit判斷==: 原本用條件判斷 `obj->parent[i][j]` 是否為 -1 來決定是否要提早中止。我將這部份改成 bitwise AND。藉由把 `sign` 初始化為 -1，他的最高位會是 1，假如中間有一個 `obj->parent[i][j]` 不是 -1，則會把最高位變為 0。因此我可以用判斷 `sign >= 0` 來決定要不要提早中止。
5. ==24==: 這裡除了加入 `sign` 的判斷，還要加入 `j<max_level`。因為我已經把 `max_level` 降低 1 了，故他沒辦法像原本的實作一定會經由 `quit` 的判斷停止。
6. ==treeAncestorGetKthAncestor==: 舊的實作從低 bit 開始找起。我想到若從高位 bit 開始看起，應會更早遇到 `-1` 才對，所以我改成由高為 bit 找起的方式。

    for(int i=obj->max_level-1; k && node != -1; i--){
        if (k >> i) {
            node = obj->parent[node][i];
            k ^= 1 << i;
        }
    }

+ $k \leq n$ 的二進位分解最大就只有到 $2^{m-1}$，因此 `i` 從 `obj->max_level-1` 開始。我逐漸往回找 set bit，找到就消掉，直到沒 parent 或是已經找到 $k$ 個為止。

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

## 程式碼解說
+ `is_divisible` 使用之前討論過的方式來判斷是否整除。
+ 首先我們統整一下對於不同的 `div3` 與 `div5` 我們會需要的 length 與 offset
+ | div3 | div5 | length | offset |
| -- | -- | -- | -- |
| 0 | 0 | 2 | 8(MSG_LEN) |
| 0 | 1 | 4 | 4 |
| 1 | 0 | 4 | 0 |
| 1 | 1 | 8 | 0 |
+ 可以注意到當 `div3` 與 `div5` 只有一個為 1 的時候，長度皆為 4。而兩個同為 1 時，長度為 8 。這樣剛好可以用 `(2 << div3) << div5` 來實作
+ 再來當 `div5` 為 1 時 offset 被除以二，對應到 `MSG >> div5`。而 `div3` 為 1 時，一律為 0 ，所以藉由
+ `>> (div3 << 2)` 我們可以確保當 `div3=1` ，我們會把數字全部位移出去變成 0 。所以這裡 `2` 也可以是更大的數字。

## 效能測試
### 環境

gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

### 程式碼
:::spoiler

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#define MSG_LEN 8
#define TEST_RANGE 1000000

static inline bool __attribute__((always_inline)) 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() {
    clock_t start, end;
    // char buffer[9];
    start = clock();
    int a=3,b=5;
    for (unsigned int i = 1; i < TEST_RANGE; i++) {
        int div3 = i%a, div5 = i%b;
        if (!div3) printf("Fizz");
        if (!div5) printf("Buzz");
        if (div3 && div5) printf("%u", i);
        printf("\n");
    }
    end = clock();
    fprintf(stderr, "%.4e, ", (double)(end-start) / CLOCKS_PER_SEC);
    
    start = clock();
    for (size_t i = 1; i < TEST_RANGE; 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");
    }
    end = clock();
    fprintf(stderr, "%.4e\n", (double)(end-start) / CLOCKS_PER_SEC);

    return 0;
}

:::
### 測試方式

#!/bin/bash
gcc -std=c99 -o fizzbuzz fizzbuzz.c
> time.txt
for i in {1..100}
do
  ./fizzbuzz 2>>time.txt 1>out.txt
done

### 測試結果
+ naive 的部份，編譯出來的結果是使用 divl 指令。但是結果顯示 naive 似乎還比較快。

+ 另外如果我將 ==23== 行換成 `div3 = i%3, div5 = i%5`，編譯器似乎會把除法指令替換掉。兩種情況下 `bitwise` 的實作都輸了。

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

我們單純看 `divident` 也就是 `PAGE_QUEUES` 的處理：

divident >>= ffs32(divident)
switch(divident)

會發現其實就是把 PAGE_QUEUES 的所有低位 0 shift 掉，看有幾種可能。由於 $2^n$ 一定會被 shift 掉，所以只要看 1~7:
| 數字 | 移除低位0 |
| -- | -- |
| 1 | 1 |
| 2 | 1 |
| 3 | 3 |
| 4 | 1 |
| 5 | 5 |
| 6 | 3 |
| 7 | 7 |

從這裡可以發現 `divident` 變成 1 的情況都是在 `PAGE_QUEUES` 為 2 的冪次方的情況。這種情況下 shift 完就做完除法了所以不用特別再處理。
剩下的就是 3、5、7 這三種情況。