2020q3 Homework4 (quiz4)

contributed by < quantabase13 >

程式運作原理

測驗一

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

根據題目提及，兩個數的 Hamming distance 其實就是其二進位表示中，相應位置數值不同的 bit 個數。
以 1 與 4 為例：

1   (0  0  0  1)
4   (0  1  0  0)
        ｜    ｜
      [相異] [相異]

有兩個位置的值不同，故 1 與 4 的 Hamming distance 為 2。
因此，對兩數使用 bitwise XOR 運算後，計算二進位表示中 1 的數目，即可求得兩數間的 Hamming distance。

測驗二

#include <stdlib.h>

typedef struct {
    int **parent/*AAA*/;
    int max_level;
    int n;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));
    obj->n = n;

    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)/*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 & (1 << i/*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);
}

為方便說明，我們以下面這個 tree 為例：

對 parent 中每一個 pointer to integer 指向的記憶體空間的內容初始化後，資料結構中的內容如下：

接著在 parent[i][0] 中填入第 i 個數的第一個 parent：

依照程式碼

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j + (-1)/*BBB*/] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }

最後資料結構的內容會變成這樣：

用表格分析會清楚一點：

i \ j	0	1	2	3	4
0	-1	-1	-1	-1	-1
1	0	-1	-1	-1	-1
2	1	0	-1	-1	-1
3	2	1	-1	-1	-1
4	3	2	0	-1	-1
5	4	3	1	-1	-1
6	5	4	2	-1	-1
7	6	5	3	-1	-1
8	7	6	4	0	-1
9	8	7	5	1	-1

可以觀察到， parent[i][j] 代表第 i 個數的第

$2^j$ 個 ancestor。
於是，在尋找數字 node 的第 k 個 ancestor 時，以 node = 9 , k = 7 為例，我們可以這麼想：
k 的 2 進位表示為

$0111=0100+0010+0001$，
node = 9 的第 0001 個 ancestor 為 8;
node = 8 的第 0010 個 ancestor 為 6;
node = 6 的第 0100 個 ancestor 為 2;
故得 node = 9 的第 7 個 ancestor 為2。
這些想法對應到程式碼：

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/*CCC*/))
            node = obj->parent[node][i];
    return node;
}

測驗三

#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/*KK1*/) >> (div3/*KK2*/ << 2/*KK3*/)], length);
        fmt[length] = '\0';

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

這題的關鍵，是透過 input number 性質控制從格式化字符串 "FizzBuzz%u" 的何處開始印起、總共印多少個字符。
我們可以透過表格分析這三者間的關係：

在字符串中的相對位置	印的字符量	input number 性質
0	4	divisible by 3
4	4	divisible by 5
0	8	divisible by 3 and 5
8	2	not divisible by 3 and 5

可以把表格分拆成兩部份：

在字符串中的相對位置	印的字符量	input number 性質
0	4	divisible by 3
8	2	not divisible by 3

可以寫成(8 >> (div3 << 2))

在字符串中的相對位置	印的字符量	input number 性質
4	4	divisible by 5
8	2	not divisible by 5

可以寫成(8 >> (div5))

兩者合併後，可以寫成 ((8 >> div5) >> (div3 << 3))，此即為所求。

測驗四

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

這裡要分析至少需要分成幾種 case 才能涵蓋所有 offset / PAGE_QUEUES 會遇到的情況。
這裡要先說明我們能不用除法指令的其中原理：
以

$7\cdot 2^n,nfrom1to14$ 為例，我們可以寫成

$(111\stackrel{n\mathrm{個}0}{\overbrace{000...000}}{)}_2$，拆成

$(111{)}_2\cdot (1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}{)}_2$。我們做除法時可以先除以

$(1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}{)}_2$ 這塊，接著再除以

$(111{)}_2$ ，步驟如下：

1. 首先是
   $(1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}{)}_2$，我們透過 ffs32(x) 算出 n ，先計算 offset >> n。
2. 接著計算
   $(111\stackrel{n\mathrm{個}0}{\overbrace{000...000}}{)}_2$ >> n，算出
   $(111{)}_2$ 。
3. 最後計算
   $(offset>>n)/(111{)}_2$ ，或是作其他處理。

可以看到從 2.開始分出了case。對於給定的集合，我們可以分析出如下 case:

case	數字	數字(2進位表示)
1	1 $\cdot 2^n$	1 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
2	2 $\cdot 2^n$	10 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
3	3 $\cdot 2^n$	11 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
4	4 $\cdot 2^n$	100 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
5	5 $\cdot 2^n$	101 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
6	6 $\cdot 2^n$	110 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
7	7 $\cdot 2^n$	111 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
8	8 $\cdot 2^n$	1000 $\cdot 1\stackrel{n\mathrm{個}0}{\overbrace{000...000}}$
case 1、2、4、8 只須做 shift 運算，不會進到最後的除法操作，所以要處理的 case 只有 3、5、7。