# 2020q3 Homework4 (quiz4)
contributed by < `sammer1107` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz4)
# 測驗 1 - Hamming Distance
```c=
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 實作換掉。
```c=
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$ 了。
```c=
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
```c=
#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
```c=
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 找起的方式。
```c=37
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
```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;
}
```
## 程式碼解說
+ `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
```c=
#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;
}
```
:::
### 測試方式
```bash
#!/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
```c=
#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` 的處理:
```c=
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 這三種情況。