# 2020q3 Homework4 (quiz4)
contributed by < `ccs100203` >
###### tags: `linux2020`
> [第 4 週測驗題](https://hackmd.io/@sysprog/2020-quiz4)
:::info
TODO 延伸問題 1、2、3、4
:::
## 測驗 1
[LeetCode 461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
- 這題要求 hamming distance，就是判斷兩組數字總共相差了多少 bit
觀察以下的 table，可以看出這就是使用 XOR 的情況，所以使用 XOR 將所有不同的 bit 設成 1，其餘為 0。最後用 `__builtin_popcount` 計算總共有多少 1 就可以知道答案。
| diff | A | B |
| :--: | :--: | :--: |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
### 延伸問題
#### [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
題目會給定一條 array，算出所有數字之間 hamming distance
最直覺的做法就是暴力解，對每個數字做 `__builtin_popcount(x ^ y)`，但這毫不易外的 TLE。
所以我採取的方法是，比較每一組 bit，每挑出一對 0 跟 1，hamming distance 就會 +1，所以得出以下結論，我只要找出每組 bit 中有多少 0 跟 1，運用組合的方式挑出所有答案。
$${n \choose 1} * {numsSize - n \choose 1}$$
```cpp=
int totalHammingDistance(int* nums, int numsSize){
int ans = 0;
for(int i=0; i<32; ++i){
int num = 0;
for(int j=0; j<numsSize; ++j){
num += (nums[j] & 0x1);
nums[j] >>=1;
}
ans += num * (numsSize - num);
}
return ans;
}
```
## 測驗 2
[LeetCode 1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)
> 給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點
```cpp=
#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 + (-1)] == -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<<i))
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);
}
```
- `treeAncestorCreate`
會建立出一個 n * max_level 的 TreeAncestor array，此 array 的用途為記錄 node 的 parent，比較特別的是這邊使用 $2^n$ 的方式去記錄，假設 n = 7，那只會記錄 3 個 parent，分別是第 $2^0$、$2^1$、$2^2$ 的 parent，其他的 parent 只需要利用 1、2、4 這三個值的組合就可以得到。這也是 max_level 的用處，就是存放 $\lfloor{\log_{2}{n}}\rfloor + 1$，代表 array 需要多少個 column。
- `int max_level = 32 - __builtin_clz(n) + 1;`實際上 `max_level` 宣告的時候是 $(\lfloor{\log_{2}{n}}\rfloor + 1) + 1$，最後的 + 1 我認為是浪費空間，他的存在原因為下方第 22 行的 for 並沒有寫終止條件。之後會對這個部分做修正。
- `quit` 就是用來當第 22 行 for 迴圈的終止條件，當有一個 column 全部為 -1 時就會 `break`。
- `treeAncestorGetKthAncestor`
這邊就是去做查表，利用 `if (k & (1<<i))` 去做到查詢的作用。
假設 k = 5，二進位為 0101，利用 $2^0$ + $2^2$ 去組合出 5。那麼答案就會是
`parent[ parent[node][1 << 0] ][1 << 2]`
### 延伸問題
#### 程式碼改進
```cpp=13
int max_level = 32 - __builtin_clz(n);
```
```cpp=22
for (int j = 1; j<max_level; j++)
```
- 將多餘的 + 1 移除掉，並且在 22 行新增終止條件，有效降低其記憶體空間的浪費。
- 原先版本繳交後占用 69.3MB，新版則是占用 67.8 MB。
#### 執行時間領先 75% 提交者
在這邊遇到一個問題，繳交同一份程式碼會有各種不同的執行時間。
1. 
2. 
## 測驗 3
考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身
先從這邊來看，此題的關鍵在於如何精準的控制 `start` 以及 `length`，藉由他們去印出答案。
```cpp
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下為完整程式碼:
```cpp=
#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;
}
```
- `unsigned int length = (2 << div3) << div5;` 若能整除 3 或 5 則為 4，兩者同時符合則為 8，剩下就是印數字本身所以長度為 2。
- `is_divisible` 可以參考 [2020q3 Homework2 (quiz2)](https://hackmd.io/@cccccs100203/linux2020-quiz2#%E6%B8%AC%E9%A9%97-4) 的解釋
- `&"FizzBuzz%u"[ (MSG_LEN >> KK1) >> (KK2 << KK3) ]` 括號內的動作就是在判定 `start` 的位置，用來當 array 的 index。
- 用一個表格表示 `start` 的可能性:
| div3 | div5 | start |
| :-: | :-: | :-: |
| 0 | 0 | 8 |
| 1 | 0 | 0 |
| 0 | 1 | 4 |
| 1 | 1 | 0 |
- 只要 `div3` 為 1， `start` 就應為 0，所以可判斷出 `(MSG_LEN >> KK1) >> (div3 << 2)`。再來藉由 `(MSG_LEN >> div5)` 去處理剩下的情況也就不難想到。
## 測驗 4
考慮到整數 PAGE_QUEUES 可能有以下數值:
- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) × ($2^n$), n from 1 to 14
在整數除法時，可思考加速運算的機制
```cpp=
#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;
```
將原本的運算轉換為下列形式
```cpp=
#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` 範圍，所以在 5~6 行先做 shift 就是為了降低除法的運算成本。可以藉由 `ffs32(x)` 得到 `divident` 有多少 tail zero，將這些 `/ 2` 的部分用 shift 取代掉。
- 在 shift 過後 `divident` 只會剩下 1、3、5、7 四種數值，所以最後的 `CASES` 就必須包含 3、5、7。
#### 延伸問題 [LeetCode 51. N-Queens](https://leetcode.com/problems/n-queens/)
- 必須運用 `__builtin_ffs`
Sign in with Wallet
Connect another wallet