2020q3 Homework4 (quiz4)

tags: sysprog2020 homework

contributed by < JKChun >

第 4 週測驗題

測驗 1

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

延伸問題1 : 解釋上述程式碼運作原理

解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼;

• answer：
  • OP : ^

什麼是 Hamming Distance ?

以下節錄自 Wikipedia 的 Hamming Distance

the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
The symbols may be letters, bits, or decimal digits, among other possibilities.

所以二進位數的 Hamming Distance 就是指兩個二進位數有幾個 bit 不一樣。
Example：

• 1011101 和 1001001 有兩個 bit 不一樣，所以 Hamming Distance 為 2。
• XOR 運算在輸入不同的 input 時，會輸出 1，所以將上述將兩數作 XOR 運算的結果為 0010100，結果的 1 代表的意義就是兩數的 bit 不一樣，所以運用__builtin_popcount 去計算一個 binary 中有幾個 1，就是有幾個 bit 不一樣，來算出 Hamming Distance。

不使用 gcc extension 的 C99 實作程式碼

直覺版：

int hammingDistance(int x, int y){
    int count=0;
    x ^= y;
    while(x){
        if( x & 1 ){
            count++;
        }
        x >>= 1;
    }
    return count;
}

不使用 gcc extension 的話，就自己實作 __builtin_popcount()，想法就是在 while loop 裡檢查兩數在 XOR 運算後的結果的 LSB 是否為1，接著往右 shift 一個位元，直到每個位元都檢查一遍。

應該可以用 bitwise operation，不需要用 while loop 去實作 __builtin_popcount()

延伸問題2 : LeetCode 477. Total Hamming Distance

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

先以直覺的想法，兩兩比對 array 中的所有元素，以 input 為 2、4、6、10、14 舉例：

Combination	HammingDistance
(2,4)	2
(2,6)	1
(2,10)	1
(2,14)	2
(4,6)	1
(4,10)	3
(4,14)	2
(6,10)	2
(6,14)	1
(10,14)	1
total hamming distance	16

假設有 n 個元素，則比對的次數為：

$C_2^n=\frac{n\ast (n-1)}{2}$ 次，時間複雜度為

$O(n^2)$，在此例 n = 5，要比對 10 次，total hamming distance 為 16，有沒有辦法降低時間複雜度？
這次把數字的二進位列出來看：

input	4th bit	3rd bit	2nd bit	1st bit
2	0	0	1	0
4	0	1	0	0
6	0	1	1	0
10	1	0	1	0
14	1	1	1	0
hamming distance	6	6	4	0

1. 先看第 1 個 bit，全部數字的 1st bit 皆為 0，所以全部數字之間彼此在 1st bit 的 Hamming Distance 為 0。
2. 接著第 2 個 bit，除了 4 的 2nd bit 為 0 以外，其餘皆為 1，所以全部數字之間彼此在 1st bit 的 Hamming Distance 為 4。
3. 以此類推，全部數字之間彼此在 3rd bit 的 Hamming Distance 為 6。
4. 全部數字之間彼此在 4th bit 的 Hamming Distance 為 6。
5. total hamming distance 為 1st bit 的 hamming distance + 2nd 的 hamming distance + 3nd bit 的 hamming distance + 4th bit 的 hamming distance = 0+4+6+6 = 16。

可以發現所有數字在同一位置的 bit 的 hamming distance 全部累加起來即為 total hamming distace 以及特定位置的 bit 的 hamming distance 就是 0 的總數乘上 1 的總數。
例：1st bit 有 5 個 0、0 個 1，所以全部數字之間彼此在 1st bit 的 Hamming Distance 為 5x0 = 0。

n'th bit	0的數量	1的數量	hamming distance
1st	5	0	5x0 = 0
2nd	1	4	1x4 = 4
3rd	2	3	2x3 = 6
4th	3	2	3x2 = 6

C語言實作

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

• 用一個 array：counter_for_one_bit 去記錄每個位置的 bit 有幾個 1，以 input 為 2、4、6、10、14 舉例：
  • counter_for_one_bit[0] 的值為 0
  • counter_for_one_bit[1] 的值為 4
  • counter_for_one_bit[2] 的值為 3
  • counter_for_one_bit[3] 的值為 2

input	4th bit	3rd bit	2nd bit	1st bit
2	0	0	1	0
4	0	1	0	0
6	0	1	1	0
10	1	0	1	0
14	1	1	1	0
	one_bit[3]	one_bit[2]	one_bit[1]	one_bit[0]
	2	3	4	0

• 用 for 迴圈走訪 nums 一次，每次用 while 迴圈去檢查 input 有幾個 1
• 第 8 行解釋：
  • 由於是用 __builtin_ctz() 去找出離 LSB 最近的 1，所以記錄完該 bit 的 1 之後要把該 bit 變 0，這樣 __builtin_ctz() 才能找出下一個 1 在哪裡。
  • 以 10 為例：一開始 number 為 1010，我們希望在下一個迴圈時 number 為 1000，這樣 __builtin_ctz(number) 才能找出下一個 1 的位置，所以要製作一個 0010 的 mask，由於我們要削除的 1 一定是從 LSB 數過來的第一個 1，所以取 number 的 2 補數可以把第一個 1 後面的 bit 全部作 NOT 運算(從 1010 變成 0110)，利用 A．
    $\overline{A}$=0 的特性，number & -number就可以得出 mask 0010，再讓 number 和 mask 做 XOR 運算就可以削除 1。

iteration	1	2
number	1010	1000
__builtin_ctz(number)	1	3
-number	0110	1000
number & -number	0010	1000
number ^ (number & -number)	1000	0000

延伸問題3

研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源

延伸問題4

研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。

---

測驗 2

給你一棵樹，樹上有 n 個節點，編號自 0 到

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

範例 input ：

["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

範例 output ：

[null,1,0,-1]

依照範例 input 建立出來的 tree：

• 在範例 input [7,[-1,0,0,1,1,2,2]]中，7為treeAncestorCreate()的 parameter n，n代表樹的節點數量，[-1,0,0,1,1,2,2]為treeAncestorCreate()的 parameter parent，其中-1代表節點 0 為 root 沒有父節點，兩個0代表節點 1 和 2 的父節點為節點 0，剩下的兩個1和2分別代表節點 3 和 4 的父節點為節點 1 及節點 5 和 6 的父節點為節點 2。

完整題目程式碼

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

延伸問題 1

解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼;

• answer：
  • AAA ： int **parent
  • BBB ： (-1)
  • CCC ： 1 << i

延伸問題 2

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

延伸問題 3

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

---

測驗 3

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

延伸問題 1

解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差

• 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf

• answer：
  • KK1 ： div5
  • KK2 ： div3
  • KK3 ： >=2

延伸問題 2

分析 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

延伸問題 1

解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;

• 對應的原始程式碼 src/mem/sizeclass.h

延伸問題 2

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

---