# 2020q3 Homework4 (quiz4)
contributed by \<joe-U16>
[測驗題](https://hackmd.io/@sysprog/2020-quiz4)
## 測驗 `1`

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

**程式碼運作原理:**
* 做 `x ^ y` 後，會比對 `x` `y` 的每個 bit 的值，如果該 bit 的值不一樣，該 bit 會 output `1`
* e.g. `0b0011 ^ 0b0001` => `0b0010`
* 而Hamming Distance 就是比對有幾個 `bit` 不一樣，所以利用 `__builtin_popcount` 把 `xor` 完後，output 為 1 的 value 加總即為所求

**不使用 gcc extension 的方法:**
實作出計算 `1` 個數的程式碼

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

**練習 LeetCode 477. Total Hamming Distance**
如果用兩個 `for` 迴圈，裡面 call 計算差異個數，會得到 `TLE`

換一個方法：

int totalHammingDistance(int* nums, int numsSize){
    int count = 0;
    for (int i = 0; i < 32; i++) {
        unsigned int k = 0;
        for (int j = 0; j < numsSize; j++) {
            if ((nums[j] >> i) & 1) {
                k++;
            }
        }
        count += k * (numsSize - k);
        }
    return count;
    }

* 一個 `int` 有 32 個 bit ，所以做 `32` 次
* 把是 `1` 的 bit 的個數可能是 k 個，是 0 的個數有 `(numSize - k)` 這兩個數相乘就會是該 `bit` 要改變的次數
* Time Complexity: `O(n)`

## 測驗 `2`
* struct TreeAncestor 有一個 max_level
* `max_level = 32 - __builtin_clz(n) + 1;`
* 可以得到這棵 tree 最大的 level
* 在最開始幫 obj 配置一段 TreeAncestor 大小的記憶體空間
* 再來幫 obj->parent 配置 n 倍的 pointer to integer
* `malloc(n * sizeof(int *));`
* 從這裡可以看出 AAA = `(b)int **parent`
* 幫每個 `obj->pointer[i]` 配置最大可能祖先數的記憶體大小，這邊的 `i` 代表第幾個 node
* 每個 node i 的第0個 `obj->pointer[i][0]` 都是存自己的parent
* 下面程式碼

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

判斷如果 node i 是有 parent 的話，就會在自己的 `obj->parent[i][j]` 的 j 格上紀錄自己的 ancessor ，而這個 ancestor 是 2 的指數倍的祖先
e.g.
`obj->parent[i][0]` 紀錄 node i 第$2^0$輩的祖先，即為父親
`obj->parent[i][1]` 紀錄 node i 第$2^1$輩的祖先，即為祖父
`obj->parent[i][2]` 紀錄 node i 第$2^2$輩的祖先，為曾曾祖父，依此類推

BBB = `(-1)` ，在 treeAncestorCreate 建立時，也建立自己的 2 的指數祖先表。

* `treeAncestorGetKthAncestor`
* `k & CCC`
* 在判斷 有哪些 2 的次方，
* e.g. `101` 即為有 $2^0$ 以及 $2^2$
* 會先找到 第 $2^0$ 輩祖先
* 找第 $2^2$ 輩祖先
* 可知 CCC = `(f) 1<<i`

## 測驗 `3`
* 考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
* 如果是 5 的倍數，印出 “Buzz”
* 如果是 15 的倍數，印出 “FizzBuzz”
* 如果都不是，就印出數字本身

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

#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;
}
// KK1 = div5
// KK2 = div3
// KK3 = 2

**程式碼運作原理:**
* `uint8_t div3 = is_divisible(i, M3);`
* 可判斷 `i` 是否可被 `3` 整除，同理 div5
* `strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);`
* 若 `div3=1, div5=0` 則需到字串第0位元的位址 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 需為 `0` ，`KK2=div3` `KK3=2` 為 `8 >> 4` 得 `0`
* 若 `div3=0, div5=1` 則需到字串第4個字元的位址 ， `KK1=div5`，`8 >> 1` 得 `4`
* 若 `div3=1, div5=1` 則需到字串第0字元的位址
* 若 `div3=0, div5=0` 則需到字串地8個字元的位址

## 測驗 `4`
考慮到整數 PAGE_QUEUES 可能有以下數值:
* (1 2 3 4)
* (5 6 7 8) X ($2^n$), n from 1 to 14

給定 size_t offset，試著將原本運算:

#include <stdio.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) {
    CASES
}

考慮到整數 PAGE_QUEUES 可能有以下數值:

> 摘自 [Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html):
Built-in Function: int __builtin_ffs (int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
`__builtin_ffs(x) - 1` 可得 x 的 index

**程式碼運作原理:**
* `blockidx = offset >> ffs32(divident);`
* 如果要除的整數作因式分解後含有 `2` ，皆可透過右移運算消除此整數裡的 `2` 得到 `1 3 5 7` 等數，之後再對 `1 3 5 7` 做處理
* 而 `1` 除 offset 即為 offset 不需處理
* 答案為 (b)3 、 (d)5 、 (f)7

###### tags: `sysprog2020`