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

> [2020q3 第 4 週測驗題](https://hackmd.io/@sysprog/2020-quiz4)

###### tags: `sysprog2020`

## 測驗一
### 題目解析

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

* 根據題意，hamming distance 是兩數在二進位編碼中同位置上相異的位元數量。
* `__builtin_popcount` 可計算出一數值的二進位編碼中 1-bit 的數量。
* 為計算位元相異數量可進行 XOR 運算，相同時結果為 0，相異為 1，再計算結果中 1-bit 的數量即為正解，因此 **OP 應選擇 `(c)` `^`**。

### 不使用 gcc extension 實作

int hammingDistance(int x, int y) {
    unsigned int count = 0;
    for (unsigned int i = 0; i < 31; ++i)
        count += ((x ^ y) >> i) & 0x1;
    return count;
}

* 此作法和上方實作方式類似，使用 XOR 運算取得兩數各位元的相互關係。
* 在迴圈逐一比對各位元取代 `__builtin_popcount` 功能，並使用 `count` 計量後回傳。

### 練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
#### 方法一：
* 嘗試暴力解，對所有組合計算 humming distance。
* 時間複雜度為 $O(n^2)$

int totalHammingDistance(int* nums, int numsSize){
    int count = 0;
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            count += __builtin_popcount(nums[i] ^ nums[j]);
        }
    }
    return count;
}

* LeetCode 執行結果為 TLE


#### 方法二：
* 以排列組合角度思考，若固定位元位置，此位元所計算出的 humming distance 應是每個 1-bit 分別對應每個 0-bit 的組合數，即 (1-bit 的數量) * (0-bit 的數量)
* 遍歷 32 個位元位置，計算各位置的 0、1 數量，再相乘取得該位置的 hamming distance
* 時間複雜度為 $O(n)$

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

* 附上 LeetCode 執行結果：


## 測驗二
### 題目解析

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

## 測驗三
### 題目解析

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

* 由題目中範例可知，此實作以設定字串起始位置及字串長度作為輸出字串的區分方式。

| 倍數 | 輸出字串 | MSG_LEN>>KK1>>(KK2<<KK3) | div3 | div5 | KK1+KK2<<KK3 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 3 | Fizz | 0 | 1 | 0 | 大於等於 4 |
| 5 | Buzz | 4 | 0 | 1 | 等於 1 |
| 15 | FizzBuzz | 0 | 1 | 1 | 大於等於 4 |
| 無 | 原數字 | 8 | 0 | 0 | 等於 0 |

因此根據上表進行推論，可選出：
**KK1 為 `(a)` `div5`**
**KK2 為 `(d)` `div3`**
**KK3 為 `(c)` `2`**

## 測驗四
### 題目解析

#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 二進位編碼中右側 0-bits 的數量，等同 x 數字中 $2^n$ 部分的 $n$
* `blockidx = offset >> ffs32(divident);` 把 offset 事先除以 PAGE_QUEUES 中的 $2^n$
* `divident >>= ffs32(divident);` 再把 PAGE_QUEUES 中自身的 $2^n$ 消去
* 最後只需確認 PAGE_QUEUES 中是否還留有非 $2^n$ 的數，再利用整數除法完成剩餘步驟，因此 **`CASES` 應包含 `(b)` `3`、`(d)` `5`、`(f)` `7`。**