# 2020q3 Homework4 (quiz4)
[toc]
## 測驗 1
```c=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
將上下 exclusive or 後,不一樣的位置會得到 1,再數 1 的數量
`OP = (c) ^`
## 測驗 2
```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;//加一是為了包含 root 的 parent -1
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
```
從這裡可以看出
`AAA = (b) int **parent`
```c=16
for (int j = 0; j < max_level; j++)
obj->parent[i][j] = -1;//全都先預設為-1
}
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];//設定各 node 的 parent
for (int j = 1;; j++) {//因為 parent 已經設好了,所以從 1 開始
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];
```
若第 j-1 個 parent 已經不存在,則第 j 個 parent 也不存在
`BBB = (b) (-1)`
第 27 行似乎有錯,應改為`: obj->parent[obj->parent[i][j - 1]][0];`
```c=28
if (obj->parent[i][j] != -1) quit = 0;
}
if (quit) break;
}
obj->max_level = max_level - 1;//把 max_level 改為真正的 level
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;
}
```
這邊無法理解 for 迴圈的用意何在
應該可以根據先前建立的 parent 直接回傳
`return obj->parent[node][k-1]` 才對
```c=44
void treeAncestorFree(TreeAncestor *obj)
{
for (int i = 0; i < obj->n; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj);
}
```
第 46 行的 obj->n 應該是指 node 數,但在 struct 中未定義
## 測驗 3
```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;
}
```
div3 與 div5 為用設計好的 M 快速判斷能否被 3 與 5 整除
接下來要靠 div3 與 div5 與 shift 來控制 "FizzBuzz%u" 的起始位置
div3 為 1 時,須將 8 shift 到 0 ,div3 為 0 div5 為 1 時 shift 到 4 ,否則保持 8
`KK1 = (a) div5`
`KK2 = (d) div3`
`KK3 = (c) 2`
## 測驗 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
}
```
第 6 行將除數特性中 $2^n$ 先去除,使 LSB 為 1
考慮 `PAGE_QUEUES` 可能的數值,在做過此操作後只剩下 1, 3, 5, 7 這些可能,而如果是 1 不需要計算
`CASES = (b) 3 (d) 5 (f) 7`