# 2020q3 Homework4(quiz4)

contributed by < `Uduru0522` >

###### tags: `perspective and application of computer systems 2020`

----

# 測驗一：計算 Hamming Distance
:::success

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

:::

## 程式說明
Hamming Distance 可以透過計算兩個 string 的相異處數量而得。
由於題目之 x 及 y 長度相同，且 $L = \{0, 1\}$，
於是我們可以利用 XOR 逕直計算滿足 $X[I] \neq Y[I]$ 的 $I$ 的數量。

## 延伸問題
### 不使用 gcc extension 的 C99 實做

int hammingDistance(int x, int y){
    uint32_t mask = 0x01, temp = x ^ y;
    int h_distance = 0;
    for(int i = 0;i < 32;++i){
        h_distance += (mask & temp);
        temp >>= 1;
    }

    return 
}

計算 `x ^ y` 之後再透過 `mask` 以及右移得出 Set Bit, 即為兩數的 Hamming Distance。

### LeetCode 477. Total Hamming Distance
:::success
Input 為一長度為 `numsSize` 的 int array,
求陣列中所有 pair 的 Hamming Distance 總和。
:::

#### 程式碼

int totalHammingDistance(int* nums, int numsSize){
    char mask = 0x01;
    int count_ones, total_distance = 0;
    
    for(int i = 0; i < 32; ++i){
        count_ones = 0;
        for(int j = 0; j < numsSize; ++j){
            count_ones += (nums[j] >> i & mask);
        }
        total_distance += (count_ones * (numsSize - count_ones));
    }
    
    return total_distance;
}

#### 說明
測驗一之中我們可以看出來，計算 Hamming Distance 時，可以每個位元分開計算。
因此，可以將問題簡化為 **對 numsSize 個 bit 來說，Hamming Distance 為何？**，
並進行 32 次 (int 的長度) 這個運算。

接著，**由於 Hamming Distance 即是算 (0, 1) 及 (1, 0) 的組數**，
當每個 input 只有一個位元時便很好計算：
$\text{num of 1's} \times \text{num of 0's}$
因此，我們只要對 array 中每個數的每個 bit 都掃過一次即可計算出 Hamming Distance 的總和。
時間複雜度為 $O(n)$。

### 錯誤更正碼簡介及抽象代數的實務應用
**TODO**

### Linux 核心中的 Reed–Solomon Error Correction

----
# 測驗二：計算 Tree 之中 Node 的第 K 個父節點
> [LeetCode 1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)
:::success

#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 + (-2)] == -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 & (1))
            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);
}

:::
## 程式說明

## 延伸問題
### 記憶體浪費檢測
### Top 25% 實做

----
# 測驗三：FizzBuzz 問題之解答優化
:::success

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

:::
## 程式說明
### 檢測可被 3 / 5 整除 (無求餘運算)
觀察程式碼，
可以注意到**以下的不等式用來得知一 32-bit 整數是否能被 d($d\in\{3,5\}$) 整除**：
> $\text{Assume } S_{i, 64}=\text{0xiiiiiiiiiiiiiiii}, i\in{[0_{16},F_{16}]}$

$n\times (S_{F,64}\div 3+1)\leq S_{F,64}\div 3$
經過化簡，可得
$n\times S_{5,64}+n\leq S_{5,64}$

接著，考慮三個不同 n 的值：整除、除三餘一、除三於二：
| $n\equiv$ | 0 (mod 3) | 1 (mod 3) | 2 (mod 3) |
| :-------: | :-------: | :-------: | :-------: |
| LHS ($n\times S_{F,64}+n$) | $\xrightarrow[]{\text{overflow}} n$ | $\xrightarrow[]{\text{overflow}}S_{5, 64}+n$ | $\xrightarrow[]{\text{overflow}}S_{A,64}+n$ |
利用 overflow 來取代除法運算中重複減去的過程，節省時間，
其中只有 $n\equiv 0(\text{mod 3})$ 時， 等式才成立。

:::info
此等式可以應用於檢測所有 $S_{F,64}$ 之因數 $M$ 且 $S_{F,64}\div M > L, L=$ **檢測範圍 bit 長度** 的
整數的因數上，舉例來說，
若要檢測是否可被 15 整除，M15 即可設成 $S_{1,64}+1$。
:::

<span style="color:red">**優點：$M_k$ 可提前計算，大幅減少除法運算的次數(僅一次)**</span>

### 字串輸出優化
程式中字串輸出以『同個字串，不同起點和終點』來輸出，如以下表格：
| **字串內容** | F | i | z | z | B | u | z | z | %u | \0 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| **起始點 (included)** | $0(mod 3)$ $0(mod 15)$| | | | $0 (mod 5)$ | | | | Others | |
| **終點 (excluded)** | | | | | $0(mod 3)$ | | | | $0 (mod 5)$ $0(mod 15)$ | Others |

#### 目標
由 `div5` 以及 `div3` 兩個值計算出**起點**以及**字串長**，`div5` $,$`div3` $\in\{0,1\}$
將上方表格轉換成數值：
| `div3` | `div5` | **起點** | `length` |
| :------: | :------: | :------: | :------: |
| 0 | 0 | 8 | $\geq$ 1 |
| 0 | 1 | 4 | 4 |
| 1 | 0 | 0 | 4 |
| 1 | 1 | 0 | 8 |

:::info
**起點方程式**
透過觀察，可以發現滿足以下方條件的方程式可以為解：

0. $\text{start_point}(0,0)=8$
1. **只要 `!div3` 便為0**
2. `div5` 會造成除以 2 的效果

可得 `start_point(div3, div5) = !div3 & (8 >> div5)`。(我的算法)
與題目中解答的相異之處為條件 ㄅ 的處理，題目使用的方式為
『若 `div3`，向右移 4-bit』，
無論運算值為何 (8 或 4) 皆會被消除。

#### `length` 方程式
透過觀察，可以發現滿足以下方條件的方程式可以為解：

0. $\text{length}(0,0)\geq 1$
1. `div3` 和 `div5` 任一為 1，結果為 4
2. `div3` 和 `div5` 同時成立會造成額外乘以 2 的效果

可得 `length = 2 << div3 << div5`。
:::

## 延伸問題
### 更換 bitmask 減少指令維持 branchless

----

# 測驗四：
:::success

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

+ (1 or 2 or 3 or 4)
+ (5 or 6 or 7 or 8) $\times$ (2n), n from 1 to 14

給定 size_t offset，計算 `blockidx = offset / PAGE_QUEUES`
<br>

#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) {
    case 3: blockidx /= 3; 
        break;
    case 5: blockidx /= 5; 
        break;
    case 7: blockidx /= 7; 
        break;
}

:::

## 程式說明
### `ffs32(n)`
> 根據 Gcc Online Documentation, 6.59 Other Built-in Functions Provided by GCC:
> > **`int __builtin_fss(int x)`**
> > Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

此 Macro 與 `__builtin__ctz(x)` 有類似作用(計算末尾 0 的數量)，然而後者對 `x == 0` 時之應對為 Undefined.

### 消除公因數 $2^n$ 及計算
將 `offset` 以及 `divient` 皆右移 `ffs32(divient)`，消除末尾所有的 0，也就是公因數 $2^n$。
觀察 `PAGE_QUEUES` 範圍，看得出可以以 $2^n\times3^a\times5^b\times5^c$ 來表示，因此 switch block 僅需處理 3、5、7 三個質因數。

## 延伸問題
### LeetCode 51. N-Queens ，使用 `__builtin_ffs()`
TODO