2020q3 Homework4 (quiz4)

contributed by < ccs100203 >

tags: linux2020

第 4 週測驗題

TODO 延伸問題 1、2、3、4

測驗 1

LeetCode 461. Hamming Distance

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

題目會給定一條 array，算出所有數字之間 hamming distance
最直覺的做法就是暴力解，對每個數字做 __builtin_popcount(x ^ y)，但這毫不易外的 TLE。
所以我採取的方法是，比較每一組 bit，每挑出一對 0 跟 1，hamming distance 就會 +1，所以得出以下結論，我只要找出每組 bit 中有多少 0 跟 1，運用組合的方式挑出所有答案。

$$(\genfrac{}{}{0ex}{}{n}{1})\ast (\genfrac{}{}{0ex}{}{numsSize-n}{1})$$

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

給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點

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

延伸問題

程式碼改進

int max_level = 32 - __builtin_clz(n);

for (int j = 1; j<max_level; j++)

• 將多餘的 + 1 移除掉，並且在 22 行新增終止條件，有效降低其記憶體空間的浪費。
• 原先版本繳交後占用 69.3MB，新版則是占用 67.8 MB。

執行時間領先 75% 提交者

在這邊遇到一個問題，繳交同一份程式碼會有各種不同的執行時間。

2. 

測驗 3

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

• 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
• 如果是 5 的倍數，印出 “Buzz”
• 如果是 15 的倍數，印出 “FizzBuzz”
• 如果都不是，就印出數字本身

先從這邊來看，此題的關鍵在於如何精準的控制 start 以及 length，藉由他們去印出答案。

#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

以下為完整程式碼:

#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) 的解釋
• &"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

在整數除法時，可思考加速運算的機制

#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;

將原本的運算轉換為下列形式

#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

• 必須運用 __builtin_ffs