2020q3 Homework4 (quiz4)

contributed by < JimmyLiu0530 >

tags: `進階電腦系統理論與實作`

測驗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);
}

程式說明

唯有兩數的某一位元相異，他們的 hamming distance 才會加1，因此先對兩數 x, y 作 ^，再利用 __builtin_popcount計算有幾個位元為1，即為 hamming distance，所以OP = ^。

延伸問題

1. 舉出不使用 gcc extension 的 C99 實作程式碼。












int hammingDistance_v2(int x, int y) {
    int total = 0;
    for (int i = 0; i < 31; i++) {
        int oneCount = 0;
        if (((1 << i) & x) != 0)
            oneCount++;
        if (((1 << i) & y) != 0)
            oneCount++;
        total += oneCount * (2 - oneCount);
    }   
    return total;
}

仿照延伸問題2的做法，詳細的原理見下方。

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

(第一次提交)用最直覺的方法兩層 for 迴圈，結果超時
(第二次提交)此方法採 bit-by-bit 的觀點來實作












int totalHammingDistance(int* nums, int numsSize){
    int total = 0;
    for (int i = 0; i < 31; i++) {
        int oneCount = 0;
        for (int j = 0; j < numsSize; j++) {
            if (((1 << i) & nums[j]) != 0)
                oneCount++;
        }
        total += oneCount * (numsSize - oneCount);
    }
    return total;
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

假設在某一位元共有 oneCount 個數字為1，那麼就有 (n - oneCount) 個數字為0，因為陣列中的每個數字皆會與其他數字計算過一次 hamming distance，所以就會使 hamming distance 總和增加 oneCount * (n - oneCount)。如此一來，遍歷所有位元的總和即為最後的答案。

3. 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說

搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源

Hamming weight, 記作

w_{H} (x)

, 表示 x 向量有幾個位元為1; 而 Hamming distance, 記作

d_{H} (x, x^{'})

, 表示兩個向量有幾個不同的位元，又可透過相加兩向量再取其 hamming weight 得到，因此可以寫成

w_{H} (x + x^{'})

(即

d_{H} (x, x^{'})

w_{H} (x + x^{'})

)。

假設模擬從 sender 取得的16個位元，其中11個 data bits，4個 parity bits:






char bits[16];
for (int i = 0; i < 16; i++) {
    bits[i] = rand()%2;
}

/*output:{1,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0}*/

接著針對所有位元為1的作 XOR，會得到:







int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 9*/

為了讓上述的 XOR 結果為0，9的二進位為1001，因此對第 1 及第 8 個進行位元反轉:










bits[1] = !bits[1];
bits[8] = !bits[8];

int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 0*/

接下來我們就可以模擬資料傳送過程中受干擾的情況，例如假設第 10 個位元在傳送中受到干擾，XOR 結果就會得到 10，也就是錯誤的位元，因此可以馬上找到錯誤的位元加以修正:









bits[10] = !bits[10];

int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 10*/

4. 研讀 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 個節點



















































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

程式說明

首先，根據 line 10-11及15得知 obj->parent 是一個指標的指標，因此 AAA = int **parent。

此題的原理: 假設要找某節點的第 k 個祖先，k = 3 (=

2^{0} + 2^{1}

) 為例，那麼意同於找此節點的第

2^{0}

個祖先的第

2^{1}

個祖先。

為甚麼要這樣做?
因為 n 個點的樹在最差的情況下有 n-1 個祖先，若將每個節點從第 0 到第 n-1 個祖先記錄下來，則需要 O(
$n^{2}$ ) 的空間，但取得第 k 個祖先只需要 O(1) 的時間。

相反的，若不額外記錄各節點的祖先，時間複雜度就會提高。因此本方法能在時間與空間取一個平衡 - 僅記錄第
$2^{0}$ 、
$2^{1}$ 、…、
$2^{n}$ 個祖先。

obj->parent[i][j] 的意義就是第 i 個節點的第

2^{j}

個祖先是誰，所以 line 14-20 就在對此二維陣列初始化及設定每個節點的第一個祖先。

接著，line 22-31 建立每個節點 i 的第

2^{j}

個祖先，會先看此節點是否存在第

2^{j - 1}

個祖先，

若不存在，則此節點必不存在第
$2^{j}$ 個祖先;
若存在，則此節點的第
$2^{j}$ 個祖先 = 此節點的第
$2^{j - 1}$ 個祖先的第
$2^{j - 1}$ 個祖先，因此 BBB = -1。

最後呼叫 treeAncestorGetKthAncestor 時，根據上述第二段的原理去拆解 k ，因此 CCC = 1 << i。

延伸問題

1. 指出可改進的地方，並實作對應的程式碼

Compile error
在 TreeAncestor struct 中，新增 int n;




typedef struct {
    ...
    int n;
} TreeAncestor;

並在 treeAncestorCreate 中，新增 obj->n = n;






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

減少使用的記憶體
在原本的程式碼中，之所以 max_level = 32 - __builtin_clz(n) + 1; 需要 +1 ，為的就是多額外配置空間給 obj->parent[i] ，好讓底下 line 22 的 for 不會越界存取。(因為這裡 for 是靠 quit 來離開迴圈的)

也就是說若新增 for 的中止條件，就不用擔心越界，也不需要配置額外空間，來達到節省記憶體的目的。

因此，修改後的部分程式碼如下:


















TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    ...
    int max_level = 32 - __builtin_clz(n); // remove +1
    ...
    for (int j = 1; j < max_level; j++) { // add j < max_level
        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; // remove +1
    return obj;
}

修改前的程式碼需要 70.3 MB 的記憶體空間，而修改過後只需 68.5 MB，減少了 1.8 MB。

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

測驗3: FizzBuzz

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

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

直覺的實作程式碼如下: (naive.c)











#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 printf 的(格式)字串，可分類為以下三種:

整數格式字串 "%d" : 長度為 2 B
“Fizz” 或 “Buzz” : 長度為 4 B
“FizzBuzz” : 長度為 8 B

考慮下方程式碼:






#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 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;
}

gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。

程式說明

首先，回顧一下 quiz 2 所學的快速 mod 運算即可了解 line 3-4, 7-8 及 12-13 的原理，在此不贅述。

根據題目給的提示可以整理成下列四種可能:

被n整除	start	length
n = 3	0	4
n = 5	4	4
n = 15	0	8
X	8	2
(X:不被3或5整除)

再回頭看程式碼，在 line 12-13，div3 及 div5 若為 1，代表 i 分別被 3 跟 5 整除，否則為0，於是根據上面表格可以推算出 length = (2 << div3) << div5。

處理完 length 接著換 start。在 line 17，此處(MSG_LEN >> KK1) >> (KK2 << KK3)即為 start，一樣根據上表，即可推得 KK1 = div5, KK2 = div3, KK3 = 2。

延伸問題

1. 評估 `naive.c` 和 `bitwise.c` 效能落差

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

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: 已知除數範圍，加速除法運算

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

(1 or 2 or 3 or 4)
(5 or 6 or 7 or 8) x
$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 個處理器週期，運算成本仍屬沉重。

來源: Agner Fog’s instruction tables，第 180 頁

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 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; 效果的程式碼。

程式說明

此方法原理就是先對被除數以及除數同時右移 ffs32(divident)位元，剩下的運算再交給 case 處理。

divident(dec)	divident(binary)	divident >> ffs(divident)
1* $2^{n}$	00010…0	0001=1
2* $2^{n}$	00100…0	0001=1
3* $2^{n}$	00110…0	0011=3
4* $2^{n}$	01000…0	0001=1
5* $2^{n}$	01010…0	0101=5
6* $2^{n}$	01100…0	0011=3
7* $2^{n}$	01110…0	0111=7
8* $2^{n}$	10000…0	0001=1

根據上面張表可得知 CASES 至少需要包含 1, 3, 5, 7 這四個數字，但又因為任何數除以 1 還是原數，所以只需 3, 5, 7 三數即可。

延伸問題

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







































































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

int *QueenPos;
int ***res;
int count = 0;

void StoreAnswer(int n)
{
    char* queen = malloc((n + 1) * sizeof(char));
    queen[n] = '\0';
    for (int i = 0; i< n; i++){
        for(int j = 0; j< n; j++){
            queen[j] = (QueenPos[i] == j) ? 'Q' : '.';
        }
        memcpy(res[count][i], queen, n + 1);        
    }
    free(queen);
    count++;
}

bool checkQueen(int row, int col)
{
    for (int i = 0; i < row; i++) {
        if (col == QueenPos[i] || abs(col - QueenPos[i]) == abs(row - i))
            return false;
    }
    return true;
}

void NQueens(int row, int n)
{
    if (count == ways[n])
        return;
    
    for (int j = 0; j < n; j++) {
        if (checkQueen(row, j)) {
            QueenPos[row] = j;
            if (row == n - 1)
                StoreAnswer(n);
            else
                NQueens(row + 1, n);
        }
    }   
}

char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes)
{
    *returnSize = ways[n];
    *returnColumnSizes = malloc(ways[n] * sizeof(int));
    for (int i = 0; i < ways[n]; i++) {
        (*returnColumnSizes)[i] = n;
    }
    
    QueenPos = malloc(n * sizeof(int));
    
    res = malloc(ways[n] * sizeof(char **));
    for (int i = 0; i < ways[n]; i++) {
        res[i] = malloc(n * sizeof(char *));
    }
    for (int i = 0; i < ways[n]; i++) {
        for (int j = 0; j < n; j++) {
            res[i][j] = malloc((n + 1) * sizeof(char));
        }
    } 
    
    NQueens(0, n);
    count=0;
    return res;
}

程式說明:

大致流程(可搭配下面的圖來看):
- 從第0列開始，一列一列往下看。
- 每一列中，由左至右一行一行看，透過呼叫 CheckQueen 檢查是否 Queen 可以放在此位置
  - 若可以，則遞迴的往下一列去看(即NQueens(row+1))
  - 這裡還要檢查是否為最後一列，若是，則以找到其中一種棋盤擺放方式，呼叫 PushAnswer 將結果存入 res
- 若已找到全部的擺放方式，則 return

***solveNQueens(int n, int *returnSize, int **returnColumnSizes)
- *returnSize: 記錄 res 的 2D array 數量(即 ways[n])
- **returnColumnSizes: 記錄每個 2D array 的行數(即 n)
- QueenPos: 記錄各列 Queen 所在的行數(即 QueenPos[1]=3 代表 Queen在第一列第三行)
- ***res: 記錄每個答案的棋盤擺放方式
NQueens(int row, int n)
- 主要就是遞迴的去找可能的擺放方式
- line 34-35 用來判斷是否已找到全部擺放方式
checkQueen(int row, int col)
- 檢查該 row 以上的所有格子看是否已存在 Queen 使得
  1. 與 col 同一行或
  2. 在 (row, col) 的右上或左上
- 若都沒有，代表 (row, col) 可以放 Queen，反之，則不行放
StoreAnswer(int n)
- 根據 QueenPos 將一種擺放方式存到 res 中
  - 看過所有 n x n 個格子，若該格有擺放 Queen，則為 'Q'，否則為 '.'

2020q3 Homework4 (quiz4)

tags: 進階電腦系統理論與實作

測驗1: LeetCode 461. Hamming Distance

程式說明

延伸問題

1. 舉出不使用 gcc extension 的 C99 實作程式碼。

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

3. 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說

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

測驗2: LeetCode 1483. Kth Ancestor of a Tree Node

程式說明

延伸問題

1. 指出可改進的地方，並實作對應的程式碼

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

測驗3: FizzBuzz

程式說明

延伸問題

1. 評估 naive.c 和 bitwise.c 效能落差

測驗4: 已知除數範圍，加速除法運算

程式說明

延伸問題

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

Read more

台灣萬萬稅

CS:APP 第一章重點整理 - Introduction

GDB介紹

Ubuntu 20.04 wifi 選項消失之解決方法

tags: `進階電腦系統理論與實作`

1. 評估 `naive.c` 和 `bitwise.c` 效能落差

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