---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework4 (quiz4)
contributed by < `RinHizakura` >

> [第 4 週測驗題](https://hackmd.io/@sysprog/2020-quiz4)
> [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz4)

## 測驗題 `1`
此題並不難理解，也就是讓兩個數字相同位元若相同則對應到 1，相異則對應到 0

| input a | input b | output |
| ------- |:------- |:------ |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

從真值表可以看出其實就是 XOR 運算，因此答案是 `OP = (c) ^`

### [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)

根據題意，要計算出陣列中的整數兩兩的 hamming distance，因此最粗暴的解法肯定是

int totalHammingDistance(int *nums, int numsSize)
{
    int hamming = 0;
    for (int i = 0; i < numsSize; i++)
        for (int j = i + 1; j < numsSize; j++)
            hamming += hammingDistance(nums[i], nums[j]);

    return hamming;
}

然而這個 O(n) 的解法如果不意外是會 TLE 的(~~反正我是不想試~~)，因此我們必須思考更佳的加法。

#### solution `1`
我的最初想法是，以下面的數字為例:

| num | bit2 | bit1 | bit0 |
|:--- | ---- | ---- | ---- |
| 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |

對於 4 來說，他與其他數字的總 hamming distance 就是**從 bit2 到 bit0，該 bit 與自己相異的總數量**，所以:
* 4 的 bit2 為 1，而 1、3 的 bit2 為 0 都和自己相異，因此這裡的總距離是 2
* 4 的 bit1 為 0，而 3 的 bit1 為 1 和自己相異，因此這裡的總距離是 1
* 4 的 bit0 為 0，而 1、3 的 bit0 為 1 都和自己相異，因此這裡的總距離是 2

所以 4 和 1、3 的 hamming distance 總和就是 2+1+2 = 5。

由此推廣，這題就可以理解為：對於目前數字 $a_n$ 的每個 bit，第 k 個 bit 前面共有多少相異的，則所有 bit 相異的數量總和，那就是 $a_n$ 和 $a_1$~$a_{n-1}$ 的總 hamming distance。那我們只要加總每次碰到的數字與前面所有數字的 hamming distance 總和，就可以得到這題的答案。

看程式碼應該會更好理解：

int totalHammingDistance(int *nums, int numsSize)
{   
    int bit[32] = {0,};
    int hamming = 0;

    if (numsSize < 2)
        return 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < 32; j++) {
            int b = nums[i] & 1;
            int tmp = (b == 0) ? bit[j] : i - bit[j];
            bit[j] += b;
            nums[i] >>= 1;
            hamming += tmp;
        }
    }

    return hamming;
}

* `bit` 用來紀錄每個 bit 至今為止出現過幾次 1
* 則對於目前掃描到的數字 n
* 假如他的第 k 個 bit 為 0，則前面的第 k 個 bit 出現幾次 1，就是該 bit 與前面數字的總 hamming distance
* 反之，如果第 k 個 bit 為 1，則前面的第 k 個 bit 出現幾次 0，也就是 i 減去出現 1 的次數，就是該 bit 與前面數字的總 hamming distance

在 leetcode 上測試後得到如下結果，可以看到還有許多改進的空間。


#### solution `2`
前面的解法中，因為外層的數字是陣列數量，然後內側是 bit 數量，所以我們會需要額外陣列空間來保存，然而如果我們把迴圈的順序倒過來呢？

int totalHammingDistance(int *nums, int numsSize)
{
    unsigned int hamming = 0;
    unsigned int bit = 0;

    if (numsSize < 2)
        return 0;

    for (int i = 0; i < 32; i++) {
        bit = 0;
        for (int j = 0; j < numsSize; j++) {
            unsigned int b = nums[j] & 1;
            nums[j] >>= 1;
            hamming += (b == 0) ? bit : j - bit;
            bit += b;
        }   
    }   
    return hamming;
}

:::info
我曾經想過把上面的第 14 行調整為沒有分支的 `hamming += ((unsigned)(b - 1) & bit ) | ((unsigned)-b & (j - bit));`，不過成效不彰，而且還會導致使用的 memory 還會因此增加。

:::

則結果如下，因為不需要額外建立 array，且頻繁的去存取 array 中的內容，可以有更好的表現。


#### solution `3`
我們可以換個思路來解決此題。

思考一下，如果假如所有的數字都是 1 bit，舉例來說 [0 1 0 0 1] 共 5 個數字，他們的 hamming bit 是多少？

我們知道，每次 hamming distance 加一，那就是找出一個 0 配上一個 1 的組合，因此上面問題的答案就是 $C_1^3 \times C_1^2$。則推廣到此題，程式碼為：

int totalHammingDistance(int *nums, int numsSize)
{
    unsigned int hamming = 0;
    unsigned int bit = 0;

    if (numsSize < 2)
        return 0;

    for (int i = 0; i < 32; i++) {
        bit = 0;
        for (int j = 0; j < numsSize; j++) {
            if(nums[j] & 1)  bit++;
            nums[j] >>= 1;
        }   
        hamming += bit * (numsSize - bit);
    }   

    return hamming;
}

別且可以得到結果如下：

### Error–Correcting Codes
為求版面的清晰，包含 Hamming codes / Reed–Solomon error correction 的理解，以及其在 linux 中如何實作等相關記錄都已整理到 [Error-Correcting Codes(ECC)](https://hackmd.io/@RinHizakura/r1IbsLjUP) !

### 抽離 [linux/lib/reed_solomon/](https://github.com/torvalds/linux/tree/master/lib/reed_solomon)

我們把 linux kernel 中的 Reed–Solomon 抽離。其中，進行了一些調整，使得操作的彈性比較小，但是在函式的呼叫則相對容易：
* 只能修正 error，不提供 erasure 的修正
* 不當的 generator $\alpha$ 會使得 RS 不能滿足某些在 GF 中運算的假設，而導致演算法的錯誤
* 此範例中固定為 2，這是一個可行的選擇
* 同樣的，不當的 primitive polynomial 也會使得 RS 無法運作。
* 範例中，假設我們使用的 symbol 都是 8 位元表示的 0 ~ 255
* 因此設定固定的 primitive polynomial = $x^8 + x^4 + x^3 + x^2 +1$ (0x11d)

使用的方法以下列程式為例：

int main()
{
    static struct rs_control *rs_decoder;
    rs_decoder = init_rs(10);

    uint16_t par[10];
    uint8_t data8[] = {0x40, 0xd2, 0x75, 0x47, 0x76, 0x17, 0x32, 0x06,
                       0x27, 0x26, 0x96, 0xc6, 0xc6, 0x96, 0x70, 0xec};
    /* Initialize the parity buffer */
    memset(par, 0, sizeof(par));
    encode_rs8(rs_decoder, data8, 16, par);

    for (int i = 0; i < 16; i++)
        printf("%x ", data8[i]);
    for (int i = 0; i < 10; i++)
        printf("%x ", par[i]);
    printf("\n");

    data8[0] = 0x50;
    data8[1] = 0x50;
    data8[2] = 0x50;

    int numerr = decode_rs8(rs_decoder, data8, 16, par);
    printf("numerr: %d\n", numerr);

    for (int i = 0; i < 16; i++)
        printf("%x ", data8[i]);
    for (int i = 0; i < 10; i++)
        printf("%x ", par[i]);
    printf("\n");
}

以這個程式為例，會輸出

40 d2 75 47 76 17 32 6 27 26 96 c6 c6 96 70 ec bc 2a 90 13 6b af ef fd 4b e0 
numerr: 3
40 d2 75 47 76 17 32 6 27 26 96 c6 c6 96 70 ec bc 2a 90 13 6b af ef fd 4b e0 

* `init_rs(10)`: 表示增加十個額外 parity，因此可以修正至多 5 個錯誤
* `encode_rs8`、`decode_rs8`: 編碼及解碼，input 為 `rs_control`、資料、資料長度、以及 parity

更多詳情請參考 [RinHizakura/Reed-Solomon-codes](https://github.com/RinHizakura/Reed-Solomon-codes)，並對照 [linux kernel 中的 Reed–Solomon codes](https://hackmd.io/@RinHizakura/r1IbsLjUP#linux-kernel-%E4%B8%AD%E7%9A%84-Reed%E2%80%93Solomon-codes) 對照理解(雖然可能說明得很不清楚 qq)
## 測驗題 `2`
### 程式原理
以下逐步觀察解釋程式運行原理:
#### `treeAncestorCreate`
* 在閱讀程式前，先注意到程式中的關鍵 `max_level` 的作用：
* 對於 n 個節點，最差情形下是有 n - 1 代的祖先，可以想到如果把每個節點從第 0 個到第 n - 1 個祖先都紀錄下來，就可以在 `treeAncestorGetKthAncestor` 時有 O(1) 的時間效率
* 然而這表示需要建立 `sizeof(int) * (n * n - 1)` 的空間，在 n 很大時是很龐大的成本
* 反之，如果不預先建立查詢的表，每一次 `treeAncestorGetKthAncestor` 就變成要在時間上承受成本
* 因此，這裡透過一個技巧去對時間和空間做出平衡，就是僅記錄每個點的第 1、2、4、...$2^n$ 個祖先是誰

因此回顧程式碼
* 首先 malloc 物件 TreeAncestor 的空間，以及每個節點與其一系列祖先的陣列空間，因此 `AAA = (b) int **parent`。也就是說 parent[i][j]，第一個 index i 用來 access 節點 i，第二個 index j 用來 access 第 $2^j$ 個祖先
* `max_level` 先初始為 `32 - __builtin_clz(n) + 1`，其實就是 $(\lfloor log_2{n} \rfloor + 1) + 1$
* 原題中的 14 到 20 行是在初始化空間並填入每個節點的第一個祖先
* 22 的 for 迴圈則是在建立第 $2^j$ 個祖先(j>0)，對於每個節點的第 j 個祖先，首先確認是否有第 j-1 個祖先，也就是 `obj->parent[i][j] = obj->parent[i][j + BBB] == -1 ? /**/ : /**/` 因此這裡的 `BBB = (b) (-1)`
* 如果有的話，舉例來說 a 的第 $2^j$ 個祖先就是第 $2^{j-1}$ 個祖先的第 $2^{j-1}$ 個祖先，也就是 `obj->parent[i][j] = obj->parent[obj->parent[i][j - 1]][j - 1]`

#### `treeAncestorGetKthAncestor`
則搜尋時，以搜尋第 5 個祖先為例，可以拆解成是搜尋第 4 個祖先的第 1 個祖先，也就是根據 5 = 0b101 去查詢即可，因此 `CCC = (f) 1 << i`

#### 運行結果

運行測驗題中的實作後，其結果為：

### 改進程式碼
#### 前情提要
我認為 leetcode 的執行時間計算在需要精確的比較下，其參考價值是很有限的。我發現同一段程式碼的不同次 submission，其執行時間可能會有很大的差異，且此差異間的人數比例很高。以下是我同對同一段程式碼的兩次提交結果:



原本我想，如果我可以成為 100% 應該就沒有這個問題吧？不過事實上，當我把第 1 名(顯示 240ms)的程式碼複製貼上重跑一次時，得到的結果則如下:


~~就很頭痛。~~

總之就儘可能的思考進步的空間吧 XD
:::warning
我也苦於 LeetCode 在執行時間分析的不精準，你嘗試去聯繫有無合作改進的機會吧？
:notes: jserv

> :ok_hand: 我可以先嘗試詢問一下他們是否有想要解決這個問題 :laughing:
:::

#### version 1:
在原始程式中，首先最顯而易見的浪費是額外的 n 空間( `max_level = 32 - __builtin_clz(n) + 1` 中的加一)，其目的僅僅是要因應 `for (int j = 1;; j++)` 迴圈沒有終止條件，而是依據 if 條件結束而可能導致額外的越界所配置。然而這個作法不但造成了空間上的浪費，也可能間接導致額外 n 次的迴圈執行。

為修正此問題，將 max_level 修改為 `32 - __builtin_clz(n)`，並將迴圈終止條件改成 `for (int j = 1;j < max_level; j++)` 來避免越界的存取，而最後對 obj max_level 的 assign 也要因應調整成 `obj->max_level = max_level`。

可以看到小幅度減少使用的記憶體。

#### version 2: row-based or column-based
對於查詢的陣列的建立，我們可以建立成 `n * max_level` (前面的作法)或者 `max_level * n` 的儲存空間，兩者對於陣列操作的 locality 會有差異。

以搜尋操作而言，由於接續的 access 沒有固定在某個 row 或 column 上的規律，兩個方法的效能差距應該不大，

而從建立搜尋陣列的角度來看，`n * max_level` 會是 column-based 操作，然而 `max_level * n` 則是 row-based 的操作，因此我預期這個調整是對時間有影響的，不過考慮到原題目對節點的數量限制，這個調整即使有益可能也不是極大幅度的，加上如前所述 leetcode 的執行時間計算問題，單從 leetcode 上的執行時間來看，兩個方法並沒有太大的差異。

不過在空間的使用上，可以看到 `max_level * n` 的儲存方式會使用相對較少的記憶體。由於兩個實作的方法是相同的，因此變數的使用並無區別，此記憶體的差異應是來自於維護的指標數量(因為顯然 `max_level` 會小於 `n`)。



雖然 leetcode 無法印證這個修改是否有益，但為了證明我的想法是正確的，我在自己的電腦上進行實驗，透過 perf 比較原本的實作以及我修正後的區別，實驗中會建立一個有 100000 個節點的 Complete Binary Tree，並進行 500 次的 隨機的 `GetKthAncestor`，可以看到實驗的結果如下：
* 建立成 `n * max_level`

Performance counter stats for './kans' (100 runs):

           511,493      cache-misses:u                                                ( +-  3.24% )

          0.011990 +- 0.000321 seconds time elapsed  ( +-  2.68% )

* 建立成 `max_level * n`

 Performance counter stats for './kans' (100 runs):

            48,067      cache-misses:u                                                ( +-  3.23% )

          0.003547 +- 0.000173 seconds time elapsed  ( +-  4.87% )

視覺化時間的差異(圖中的 y 軸單位為 ns)

可以明顯的看到善用 cache locality 對執行時間的差距。而從圖中也可以看到，以題目最大節點 50000 個節點而言，兩者的差距的大約是 2 ms，以我們在 leetcode 計時系統本身的總時間而言可以說是輕如鴻毛，也難怪看不出顯著的提升了。

## 測驗題 `3`

~~[這題首先要先建一個 neural network](https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/)...~~

此題的關鍵是透過 div3 和 div5 去調整要複製 "FizzBuzz%u" 的起點和長度為何，首先來看 length 的調整:
* 如果可以整除 "3" 和 "5"，length = 2 << 1 << 1 = 8
* 如果可以整除 "3" 或 "5"，length = 2 << 1 = 4
* 否則就是 2

而題目問的則是對起點的調整，我們可以觀察 "FizzBuzz%u" 這個字串
* 如果可以整除 "3" 或 "3 和 5"，則要從字串的位置 0 開始複製
* 如果只能整除 5，則要從字串 4 的地方開始複製
* 否則就從 8 的地方開始

歸納以上的法則，表示 (MSG_LEN >> KK1) >> (KK2 << KK3) 計算後的結果 start 需如下表:

| div3 | div5 | start |
| ---- | ---- |:----- |
| 0 | 0 | 8 |
| 0 | 1 | 4 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

我們可以依據此推理出最佳解為 (MSG_LEN >> div5) >> (div3 << 2)

## 測驗題 `4`
此題的重點在於把可以用位移取代的除法先行計算，從而減少過多複雜的除法指令。觀察 `PAGE_QUEUES`，可以知道其數值都可以表示成 $k \times 2^n$，其中 k 是介於 1 到 7 之間且不為 2 倍數的整數，n 則介於 0 到 14 之間。且我們都知道，對於 $2^n$ 的除法都可以透過位移取代，因此：
* `ffs32(x)` 的作用就是找到 $2^n$ 中的 n 是多少，
* `blockidx = offset >> ffs32(divident)` 先將 offset /= $2^n$
* `divident >>= ffs32(divident)` 將 `PAGE_QUEUES` /= $2^n$
* 因此 switch case 只要針對前面的 k 去計算即可，可能的 k 有 1、3、5、7 不過 1 的狀況是不需要額外處理的，因此答案為 `(b) 3 (d) 5 (f) 7`

### [51. N-Queens](https://leetcode.com/problems/n-queens/)

#### solution `1`

我們可以想像題目最簡單粗暴的解法就是直接窮舉所有可能，再一一檢查是否符合條件，但以 N-Queens 為例，4 x 4 的棋盤就有 $2^{16}$ 個下法(對於每一格，下或不下皇后)，顯然不是很好的作法。

對於此類需要輸出所有滿足條件的題目類型，最先想到的解法是 [Backtracking](http://web.ntnu.edu.tw/~algo/Backtracking.html)，大抵的概念可以理解為: 在遞迴中，每次前進到下個遞迴前就去檢查目前的狀況是否符合條件，如果已經不符合，就不需要去嘗試剩下的格子該怎麼下了。

初步想到的解法是直接分配一個 "棋盤" 的空間，並且在遞迴中去檢查棋盤是否符合條件。值得注意的是這裡使用了一些比較投機的作法:
* `sizes` 陣列儲存了 n x n 可能解數量，這使得我們在一開始就可以分配出足夠的空間
* 否則，就需要 malloc 足夠大的空間，或者呼叫 realloc
* 為甚麼這裡 `sizes` 的數量假設 `n <= 18` 呢？ 這是因為 `n > 18` 的解數量甚至超過 int 可容許的範圍了，考慮到我們要回傳的 `*returnSize` 是一個 int，所以可以如此假設
* `*returnSize` 是回傳的 `charr***` 的 2D array 數量，也就是解的數量，因此同上概念預先 assign 為 `sizes[n]`
* `**returnColumnSizes` 則是 `charr***` 每個 2D array 的 columns 數，實際上都必須 `= n`，所以就直接 assign 了

額外補上了一些幫助理解的註解，因此程式行數比較多，完整的程式請參考 [(4323917)NCKU-System-Software-Quiz4/NQueen.c](https://github.com/RinHizakura/NCKU-System-Software-Quiz4/blob/43239e75ab377f7e49fcbfc1f4ebd3ef0cb8dc5f/NQueen.c)。

這個解法有許多可避免的 overhead，不過我認為整體的程式邏輯是比較清晰的，作為初步的理解應該還不錯XD。執行後得到的結果如下：

#### solution `2`
原本上述程式設計的考量點，除了比較容易理解之外，也考慮到 n 的大小是不可預期的，這個作法會比較 general 一點。不過在前面我們也看到了基於 n 對應的解數量，n 在測資中理應不會太大。

事實上，根據 [guaneec](https://hackmd.io/@guaneec/sp2020q3-quiz4#Q4---ffs) 的筆記，實際上的測資內容是:

4
1
2
3
5
6
7
8
9

這使我想到之前在老師的課程中看到的 [2019q1 第 1 週測驗題](https://hackmd.io/@sysprog/SyrZMGYr4)，如果 n 最多為 9，則一個整數的 bit 數量足夠對應每個位置，我們可以將檢驗正確與否的操作轉換成對 bitmask 的 bitwise operation!(有興趣的話可以參考我之前嘗試寫的[題解](https://hackmd.io/IuZvjukcRbu-DN74aB37Iw?view#2018q3-%E7%AC%AC-1-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C))

static int sol = 0;
int sizes[] = {1,      1,       0,        0,        2,        10,    4,
               40,     92,      352,      724,      2680,     14200, 73712,
               365596, 2279184, 14772512, 95815104, 666090624};

void recursive_solver(int n,
                      int row,
                      char **queen,
                      char ***p,
                      int maj_con,
                      int min_con,
                      int col_con)
{
    int queen_pos;
    int conflicts = min_con | maj_con | col_con;

    min_con &= 65535;
    for (int col = 0; col < n; col++) {
        queen_pos = 1 << (16 - col);
        if (!(queen_pos & conflicts)) {
            if (row == n - 1) {
                queen[row][col] = 'Q';
                for (int i = 0; i < n; i++)
                    memcpy(p[sol][i], queen[i], n + 1);
                sol++;
                queen[row][col] = '.';

            } else {
                queen[row][col] = 'Q';
                recursive_solver(
                    n, row + 1, queen, p, (maj_con | queen_pos) >> 1,
                    (min_con | queen_pos) << 1, (col_con | queen_pos));
                queen[row][col] = '.';
            }
        }
    }
}


char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes)
{
    sol = 0;
    *returnColumnSizes = malloc(sizes[n] * sizeof(int));
    *returnSize = sizes[n];
    for (int i = 0; i < sizes[n]; i++)
        (*returnColumnSizes)[i] = n;

    char ***p;
    p = malloc(sizes[n] * sizeof(char **));

    for (int i = 0; i < sizes[n]; ++i)
        p[i] = malloc(n * sizeof(char *));


    for (int i = 0; i < sizes[n]; ++i)
        for (int j = 0; j < n; ++j) {
            p[i][j] = malloc((n + 1) * sizeof(char));
        }

    char **queen;
    queen = malloc(n * sizeof(char *));
    for (int i = 0; i < n; i++) {
        queen[i] = malloc((n + 1) * sizeof(char));
        for (int j = 0; j < n; j++)
            queen[i][j] = '.';
        queen[i][n] = '\0';
    }

    recursive_solver(n, 0, queen, p, 0, 0, 0);

    for (int i = 0; i < n; i++)
        free(queen[i]);
    free(queen);

    return p;
}

將檢查轉換成 bitwise 操作後，可以看到執行時間可以得到進步。程式部份請參考[(723c31a)NCKU-System-Software-Quiz4/NQueen.c](https://github.com/RinHizakura/NCKU-System-Software-Quiz4/blob/723c31a429367cdd74f4d2dcae86cedca63dbbf6/NQueen.c)

:::warning
尚未想到何種作法下可以應用到 `__builtin_ffs (int x)`，唯一想到只有對 `queen_pos`，不過事實上已經等於 `col` 所以這個反而多此一舉了...
:::