2020q3 Homework4 (quiz4)

contributed by < Holycung >
2020q3 Homework4 (quiz4) 題目

目錄

• 2020q3 Homework4 (quiz4)
  • 目錄
  • 測驗 1
    • 題目
    • 作答
    • 延伸問題
  • 測驗 2
    • 題目
    • 作答
    • 延伸問題
    • 延伸問題
  • 測驗 3
    • 題目
    • 作答
    • 延伸問題
  • 測驗 4
    • 題目
    • 作答
    • 延伸問題

測驗 1

題目

LeetCode 461. Hamming Distance 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。

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

請補完程式碼。

作答

這邊運用 xor 就可以找到哪些位元是不相同的，最後在使用 __builtin_popcount 就可以得到 Hamming distance，所以 OP = ^。

延伸問題

題目

練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時

作答

稍微觀察一下下表就可以發現，只要看第 n 個位置的 bit 總共有幾個 0 跟 1，一對 0 跟 1 就會有一個 hamming distance，所以最後我們只要找出第 n 個 bit 有幾個 1 跟 0 就可以計算出 hamming distance。

decimal	bit 2	bit 1	bit 0
0	0	0	0
1	0	0	1
2	0	1	0

實作方式如下，用 bit_count 的陣列紀錄每個 bit 1 出現的次數，第 5 行的 while 迴圈則是運用作業 3 的技巧去找到當中是 1 的 bit 位置並記錄到 bit_count，最後的 for 迴圈則是計算出每個位元的 hamming distance。

int totalHammingDistance(int* nums, int numsSize){
    int bit_count[sizeof(int) * 8] = {0};
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        while (num) {
            bit_count[__builtin_ctz(num)]++;
            num ^= num & -num;
        }
    }
    int sum = 0;
    for (int i = 0; i < sizeof(int) * 8; i++) {
        sum += (numsSize - bit_count[i]) * bit_count[i];
    }
    return sum;
}

提交到 Leetcode 上的結果。

TODO

• 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
  搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
• 研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。

測驗 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 個節點

以下是參考 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);
}

請補完。

作答

範例當中 [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]，第一個陣列的 7 代表 7 個節點，後面的陣列則是代表每個節點的 ancestor 是誰。再來這題並沒有說到這個 tree 是 binary 或是 full、complete tree，所以都是有可能的。

因此一個節點最多有可能會有 n-1 個 ancestor。如果一個一個找起了話時間是複雜度是

$O(n)$ 空間複雜度也是

$O(n)$，那如果在建樹的時候把所有的 ancestor 都用表紀錄下來，那查尋的時間複雜度就是

$O(1)$ 但是空間複雜度就是

$O(n^2)$，這邊題目為了取得一個平衡，所以選擇記錄下每個節點的

$\lfloor lo{g}_{2}n\rfloor +1$ 的祖先，那在空間上我們就只需要花

$O(nlogn)$，在查詢的時間複雜度是

$O(logn)$。

再探討一下這個方法，為何只要記錄下每個節點的

$\lfloor lo{g}_{2}n\rfloor +1$ 祖先，就保證能找到所有的祖先，那這邊要先知道一件事情，假設我們今天要找某個節點的第 k 個祖先，可以替換成某個節點的第 1 個祖先的第 k-1 個祖先，或是第 2 個祖先的第 k-2 個祖先，以此類推。所以第一個條件，不能去找某個節點大於

$\lfloor lo{g}_{2}n\rfloor +1$ 的祖先。

再來要怎麼確定再這樣的條件下一定可以找到所有的祖先，那就是本題的方法，從二進位的角度來想，假設 5 可以寫成，

$2^2+2^0$ 這樣的表示，那我們今天要找某一個節點的第 5 個祖先，就可以換成找第

$2^0$ 個祖先的第

$2^2$ 個祖先，那今天要找第 n 個祖先，這樣我們最多就只會找到第

$\lfloor lo{g}_{2}n\rfloor +1$ 個祖先，就可以滿足第一個條件，並且可以在時間複雜度

$O(logn)$ 下面完成。接下來看到程式碼。

第 11 行可以看到先配置了 n 個節點的大小，可以知道 TreeAncestor 裡面的 AAA 是一個二維的資料結構，所以是 **parent。
第 13 行變數 max_level = 32 - __builtin_clz(n) 就是

$\lfloor lo{g}_{2}n\rfloor +1$，但是這邊 32 - __builtin_clz(n) 還多加了一個 1，後面會提到。
第 14 行的迴圈則在初始化，第 19 行是先記錄下每個節點的第一個 ancestor。
第 25 行是把每個節點的 ancestor 記錄下來，所以 obj->parent[i][j + BBB] == -1 先判斷上一個祖先是不是 -1，不是的話就把去找到這個祖先記錄下來。

第 36 行 treeAncestorGetKthAncestor 這個是找到第 k 個 ancestor，迴圈的中止條件就是已經找到 -1 代表不存在，或是大於等於 max_level。第 40 行這邊就是我們上面講的方法，對二進為每個 bit 去做替換，假設找某一個節點的第 5 個祖先，5 的二進為是 101，就可以換成找第

$2^0$ 個祖先的第

$2^2$ 個祖先，所以 CCC 就是 1 << i，從最低位的開始替換。

延伸問題

在 treeAncestorCreate 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;

作答

剛剛上面有提到第 13 行變數 max_level = 32 - __builtin_clz(n) 就是

$\lfloor lo{g}_{2}n\rfloor +1$，但是這邊 32 - __builtin_clz(n) 還多加了一個 1，透過剛剛的解題思維，給定第 k 個祖先，我們最大只會用到第

$\lfloor lo{g}_{2}k\rfloor +1$ 個位元，所以這邊不需要 +1，節省記憶體的空間。

延伸問題

在 LeetCode 1483. Kth Ancestor of a Tree Node 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;

作答

在改進過程當中發現 leetcode 繳交同一份程式的時間會有些落差，連 memory 的使用也會有小誤差，所以以下都是繳交數次截圖比較優的一次，作為參考。

treeAncestorCreate

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

    int max_level = 32 - __builtin_clz(n);
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        memset(obj->parent[i], -1, max_level * sizeof(int));
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1; j < max_level; 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;
    return obj;
}

這邊的修改就是把 max_level 的 +1 拿掉，然後第 15 行的 for 迴圈要加上終止條件 j < max_level。
第 10 行原本的 for 迴圈改以 memset 進行初始化。

treeAncestorGetKthAncestor

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    while (k && node != -1) {
        node = obj->parent[node][__builtin_ctz(k)];
        k ^= k & -k;
    }
    return node;
}

查詢第 k 個祖先這邊原本是從最低位元一個一個開始找起，找到 1 的 bit 就做替換，那這個也可以換成上一個作業的技巧，透過 __builtin_ctz 直接找到最低位為 1 的位元，所以這邊改用 while 迴圈，中止條件多了一個 k == 0。

不過這裡應該要對 k 的大小進行判斷，仔細觀察發現原本的程式也沒有進行判斷，如果今天 k 給一個大於 max_level 的值，然後剛好是 2 的次方這個方法就會噴錯，於是自己寫了程式跑了一下驗證，果然是會有錯誤的，詳細的 code 放在 Github，神奇的是 leetcode 都通過了

。

• 原版
• max_level 修正 -1
• treeAncestorGetKthAncestor 改用 ctz 作法
• 改用 memset 初始化(以下是同一份程式兩次繳交，時間跟空間大小都有落差 )

測驗 3

題目

出處: 簡單的 FizzBuzz 藏有深度 (Google 面試題)

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

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

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.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;
}

請補完。

作答

這題判斷是否能整除有用到 作業二 quickmod 的技巧來判斷是否能整除，並且透過精準地控制 start、length，即可正確的輸出。

第 14 行可以看到 length 原本是 2，如果能整除 3 或 5 就往右邊 shift 一位，也就是乘二的意思，兩個都能整除就 shift 兩次，得到 8。

接下來看到 17 行要控制 string literal "FizzBuzz%u" 的 start 位置，於是用下表觀察一下。

div3	div5	length	start
0	0	2	8
1	0	4	0
0	1	4	4
1	1	8	0

這邊觀察 div3、div5、start 三個變數，在 div3 = 1 的時候 start 都要為 0，所以可以知道 KK2 << KK3 這邊應該是 div3 << 2 這樣就會把前面歸 0。剩下的推倒一下就可以得到 KK1 = div5。

延伸問題

評估 naive.c 和 bitwise.c 效能落差
避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf

作答

這邊要記得將所有的 printf 換成 sprintf，不然會大大影響實驗的結果，測試從 1 到 100000，並且重複執行 100 次，進行觀察。

cmp_fizzBuzz.c

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

#define TEST_RANGE 100000
#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[]) {
    long long time1 = 0LL, time2 = 0LL;
    struct timespec tt1, tt2;
    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (unsigned int i = 1; i <= TEST_RANGE; i++) {
        char s[MSG_LEN + 1];
        int div3 = i % 3;
        int div5 = i % 5;
        if (!div3) sprintf(s, "Fizz");
        if (!div5) sprintf(s, "Buzz");
        if (!div3 && !div5) sprintf(s, "FizzBuzz");
        if (div3 && div5) sprintf(s, "%u", i);
        sprintf(s, "%s\n", s);
        // printf("%s", s);
    }
    clock_gettime(CLOCK_MONOTONIC, &tt2);
    time1 += (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (unsigned int 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';

        sprintf(fmt, "%s\n", fmt);
        // printf(fmt, i);
    }
    clock_gettime(CLOCK_MONOTONIC, &tt2);
    time2 += (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

    printf("%lld %lld\n", time1, time2);
    return 0;
}

getTime.sh

#!/bin/bash
for i in {1..100}
do
  ./cmp_fizzBuzz >> time.txt;
done

實驗結果如下，可以看出 bitwise 的方法確實是比 naive 版本快，詳細的程式可以參考 Github。

TODO

• 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
• 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware

測驗 4

題目

考慮到整數 PAGE_QUEUES 可能有以下數值:

• (1 or 2 or 3 or 4)
• (5 or 6 or 7 or 8) × (
  $2^n$), n from 1 to 14

給定 size_t offset，試著將原本運算:

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

由於 PAGE_QUEUES 的數值分佈已知，在整數除法時，可思考加速運算的機制。需要注意，某些硬體平台缺乏整數除法指令 (如 Arm Cortex-A8)，即使 Intel 公司出品的 Core 處裡器 Sandy Bridge 微架構中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)

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

其中 CASES 可能形如:

    case 2: blockidx /= 2; 
        break;

這樣的組合，請用最少的 case-break 敘述做出同等 size_t blockidx = offset / PAGE_QUEUES; 效果的程式碼。

作答

這邊我們已知除數 PAGE_QUEUES 的範圍是

$k\times 2^n$，k 的範圍是 1~7，n 是 1~14，然後要對其整數除法進行加速，可以透過對除數跟被除數先進行約分的動作，就是先把

$2^n$ 用 shift 方式處理掉。

看到程式當中的 __builtin_ffs 可以參考 Built-in Functions Provided by GCC，所以這邊的 ffs32(x) 就是代表最低位有多少個 0，也就可以知道我們要往右 shift 幾位。

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

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

第 5 6 行就是對被除數 offset 跟除數 divident 先進行 shift，最後再透過 switch case 進行剩下的除法。不過因為已知除數 PAGE_QUEUES 的範圍是

$k\times 2^n$，所以把

$2^n$ 除掉後只剩下

$k$，可能的 k 有 3、5、7，因此 cases 需要包含這三個數字。

延伸問題

TODO
練習 LeetCode 51. N-Queens，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;