# 2020q3 Homework4 (quiz4)

contribute by <`hsiehong`>

###### tags: `進階電腦系統理論與實作`

outline
[TOC]

### [題目](https://hackmd.io/@sysprog/2020-quiz4)

## 測驗 1

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

OP = `^`
### 原理

要計算兩數 `x`, `y` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)，先將兩數做 xor 運算，所得結果的數的二進制中 1 的個數即為所求

### LeetCode 練習

[477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
* 作法一
最直覺的做法，用雙迴圈將所有結果加總起來，但會 TLE

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        size_t numSize = nums.size();
        int ham = 0;
        for (int i = 0; i<numSize; ++i) {
            for (int j = i + 1; j<numSize; ++j) {
                ham += __builtin_popcount(nums[i] ^ nums[j]);
            }
        }
        return ham;
    }
};

* 作法二

參考[解說](https://leetcode.com/problems/total-hamming-distance/discuss/720409/Python-Bit-Manipulation-Explanation-with-Diagram)

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        size_t numSize = nums.size();
        int bitCnt[32] = {0};
        for (int i = 0; i < numSize; i++) {
            for (int j = 0; j < 32; j++) {
                if (nums[i] & (1 << j)) {
                    bitCnt[j]++;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            sum += (numSize - bitCnt[i]) * bitCnt[i];
        }
        return sum;
    }
};

主要是利用 bit operation **每個 bit 都是各自獨立的**特性，記錄每個位置 1 跟 0 出現的次數，每個 1 跟每個 0 會貢獻一次 Hamming distance，將兩數相乘就是那個 bit 總共會貢獻的 Hamming distance

## 測驗 2

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

AAA = `int **parent`, BBB = `(-1)`, CCC = `1 << i`

* 在 func `treeAncestorCreate()` 內部，可以看到 line 11 先宣告一個一維空間給 parent ，在 line 15 在對每個單位空間宣告 max_level 大小的空間，可得知 `parent` 是一個二維陣列，所以 AAA = `int **parent`

* line 24 的 for loop 是在對每個點建立祖先，假設要建立第 j 個祖先，要先檢查第 j-1 的祖先是否存在，有的話才將第 $2^{j-1}$ 個 parent 的第 $2^{j-1}$ parent 加入 (binary tree) 寫入第 $2^j$ 個祖先，所以 `BBB = -1`

## 測驗 3

FizzBuzz !!!

從 1 數到 n，如果是 3的倍數，印出 “Fizz”，如果是 5 的倍數，印出 “Buzz”，如果是 15 的倍數，印出 “FizzBuzz”，如果都不是，就印出數字本身，觀察下列 offset，可以透過 offset 來控制期望的輸出

 string literal: "fizzbuzz%u"
         offset:  0   4   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 >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

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

KK1 = `div5`, KK2 = `div3`, KK3 = `2`

* `div3`, `div5` 分別代表 n 是否可以被 3, 5 整除，並決定好要複製的起點和長度。觀察 `length`
* 若只可被 3 整除 (2 << 1 << 0) = 4
* 只可被 5 整除 (2 << 0 << 1) = 4
* 若同時可被 3 跟 5 整除 (2 << 1 << 1) = 8
* 否則其他狀況 = 2

* 觀察每個狀態的起始位置

 string literal: "fizzbuzz%u"
         offset:  0   4   8

| div3 | div5 | start(MSG_LEN) |
|:----:|:----:|:--------------:|
| 1 | 0 | 0 |
| 0 | 1 | 4 |
| 1 | 1 | 0 |
| 0 | 0 | 8 |

可以推得 `(MSG_LEN >> KK1) >> (KK2 << KK3)`，其中 KK1 = `div5`, KK2 = `div3`, KK3 = `2`

## 測驗 4

TODO