2020q3 Homework4 (quiz4)

contributed by < OscarShiang >

作業要求

重新回答第 4 週測驗題

測驗 `1`

本題的用意在於實作出可以計算兩個給定數字之間的 Hamming distance

The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different.

假設給定的兩個字串 001 與 010 ，因為兩者有在對應位置上有兩處不同，因此 Hamming distance 是 2。

而看到本題實作的部分

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

因為使用 __builtin_popcount 來計算 Hamming distance ，所以我們只需要將相異的兩個位元設定為 1 即可，所以 OP 的答案就會是

OP = ^

測驗 `2`

本題嘗試實作一個樹狀結構以及相關的操作，包括

treeAncestorCreate
treeAncestorGetKthAncestor
treeAncestorFree

並且以下圖作為範例來實作

AAA

本題的部分是要補完樹狀結構元素的 struct，根據

typedef struct {
    AAA;
    int max_level;
} TreeAncestor;

的部分我們可以知道這個元素的結構包括一個 int 變數 max_level 用記錄從這個節點向上還有多少層元素。

接著我們可以看到 treeAncestorCreate 函式中關於節點初始化的部分

    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

從這邊我們可以看到 TreeAncestor * 這個變數 obj 的結構中有 parent 這個 field，並從 malloc 的參數得知，我們取得了一段可以存取 n 個 int * 型態的變數的空間，所以根據上述的線索我們可以推測在 AAA 中缺少的 field 應該是

AAA = int **parent

BBB

根據 BBB 所在位置的程式碼

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][BBB] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1)
                quit = 0;
        }
        if (quit)
            break;
    }

我們可以從三元運算子 else 的條件看到，如果 obj->parent[i][BBB] == -1 的條件不成立時，則會將 obj->parent[obj->parent[i][j - 1]][j - 1] 的數值賦值到 obj->parent[i][j] 中。

因此我們可以判斷 BBB 的部分是在確認是否存在 obj->parent[i][BBB] 亦即該變數的數值不等於 -1，才能做 obj->parent[obj->parent[i][j - 1]][j - 1] 取值的運算。

因為根據 ISO/IEC 9899 6.5.2.1 Array subscripting 的描述

The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

若我們嘗試取得一個 array 編號 -1 的元素時，根據上述的概念，我們實際上會存取到在 array 第 0 個元素之前的資料，除了程式將無法按照我們預期的執行之外，也會造成記憶體存取上的疑慮，因為我們正在對程式宣告的記憶體空間以外的其他位址進行操作。

因此為了避免這樣的問題，我們才需要事先確認 obj->parent[i][BBB] == -1 的情況是否發生

所以 BBB 的答案就會是

BBB = (-1)

CCC

為了了解這題的實作觀點，我們首先可以看到 treeAncestorCreate 函式中針對 max_level 的計算

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 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 max_level = 32 - __builtin_clz(n) + 1 這個部分本質上就是在做

l o g_{2} n + 1

的動作，也就是在計算這個二元樹的最多會有多大的 level。

在本題中，因為共有 7 個節點，所以最多會有 3 個 level (第 0 ~ 2 層)，而最後 +1 的部分是為了保留終止的數值 -1。

因此我們可以知道本題的結構在 obj->parent 中保存的狀態應該如下表所示

[0]: -1 -1 -1 -1
[1]: 0 -1 -1 -1
[2]: 0 -1 -1 -1
[3]: 1 0 -1 -1
[4]: 1 0 -1 -1
[5]: 2 0 -1 -1
[6]: 2 0 -1 -1

而接著在 treeAncestorGetKthAncestor 中，也就是 CCC 所在的位置

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

這邊所採取的方式是將給定的 k 利用 i 拆成二的次方的級數

例如我們給定

k = 7

則透過 for 迴圈，我們應該要將其拆成

\begin{aligned} k & = 1 + 2 + 4 \\ = 2^{0} + 2^{1} + 2^{2} \end{aligned}

接著將這些數字分別帶入 obj->parent 的陣列中找尋對應的節點

所以根據上述的條件，CCC 應該為

CCC = 1 << i

修改實作

從 CCC 中我們可以發現在尋找第 k 個祖先節點的時候我們是透過 2 的冪次逐漸求得我們所要的答案，但是因為這些資訊在 obj->parent 中全部都有記錄，所以我們也可以利用下列的方式來取得答案

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    if (k > max_level)
        k = max_level;
    node = obj->parent[node][k - 1];

    return node;
}

再來因為我們剛剛在解釋 BBB 的時候，有提到每個節點的最後面都有一個 -1 的數值作為終止的標記。

但是在 treeAncestorCreate 在最後有這麼一行操作

    obj->max_level = max_level - 1;

而在 treeAncestorGetKthAncestor 函式中是如此操作這個陣列

for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (CCC))
            node = obj->parent[node][i];

從這邊我們就可以看到在這些操作中，我們顯然根本不會使用到在 treeAncestorCreate 的時候考慮到的最後一個終止的數值。因為我們在設定完最後一個位置之後，有將邊界做調整，對應到 for 迴圈的邊界，所以在正常使用 max_level 作為邊界來操作的時候，我們是不會用到陣列的最後一個 -1 的。

因此我們可以再針對這個實作做以下的調整

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

-   int max_level = 32 - __builtin_clz(n) + 1;
+   int max_level = 32 - __builtin_clz(n);
    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];

    /* Construct the relations of each parents */
    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;
+   obj->max_level = max_level;
    return obj;
}

測驗 `3`

本題嘗試使用 bitwise 的方式實作一個滿足以下條件的 Fizzbuzz 題目

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

透過給定數值的規律來控制輸出字串的形式

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

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 →

關於 is_divisable 的解釋可以參考 2020q3 Homework2 (quiz2)

所以根據 is_divisable 函式的定義，div3 與 div5 只有 0 或 1 兩種結果，因此我們只要專注在如何用 div3 與 div5 湊出對應的字串即可。

因此我們可以考慮以下的情況

考慮給定的數字是 3 的倍數，亦即 div3 = 1 且 div5 = 0
因為我們要輸出的字串是 Fuzz，所以需要先透過 (MSG_LEN >> KK1) >> (KK2 << KK3) 計算出 0

假設 KK1 的答案是 div3 而 KK2 的答案是 div5，則表示 (8 >> 1) >> (0 << KK3) 得到 4

考慮到 8 這個數字至少要位移 4 次後才會是 0 ，所以可以組合出最大的可能就會是

KK1 = div5

KK2 = div3 (或 2)

KK3 = 2 (或 div3)

我們可以帶入 div3 = 0 且 div5 = 1 也就是給定數字是 5 的倍數的情況來驗算

考慮給定 div3 = 0 與 div5 = 1 的 (MSG_LEN >> div5) >> (div3 << 2) 與 (MSG_LEN >> div5) >> (2 << div3) 兩種情況

代入數字後兩式就會變成 (8 >> 1) >> (0 << 2) = 4 與 (8 >> 1) >> (2 << 0) = 1

所以根據計算的結果我們就可以知道正確的組合是

KK1 = div5

KK2 = div3

KK3 = 2

`naive.c` 實作的問題

根據題目給定的 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;
}

在給定數字 i 是 3 或是 5 的倍數的時候可以正常印出規定的字串形式，但是因為上述程式碼在邏輯上採用的是個別判斷是否為 3 或 5 的倍數的手法，所以在遇到 i = 15 * n (n >= 1) 的情況的時候會輸出以下的字串

i = 1,	1
i = 2,	2
i = 3,	Fizz
i = 4,	4
i = 5,	Buzz
i = 6,	Fizz
i = 7,	7
i = 8,	8
i = 9,	Fizz
i = 10,	Buzz
i = 11,	11
i = 12,	Fizz
i = 13,	13
i = 14,	14
i = 15,	FizzBuzzFizzBuzz
i = 16,	16

從上列的輸出可以看到在判斷的邏輯上，若 i 是 15 的倍數也就表示其是 3 與 5 的倍數，所以在這個實作中，我們不需要額外針對 i 是 15 的倍數的情況在處理，因為我們在判斷其為 3 的倍數的時候就會輸出 Fuzz；判斷其為 5 的倍數的時候就會輸出 Buzz 了

所以我們可以將 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;
}

省去多餘的邏輯判斷。

測驗 `4`

本題的用意在於使用 __builtin_ffs 來減少整數除法的開銷

考慮到 PAGE_QUEUES 的數值範圍如下

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

用以進行以下的運算

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

因為 PAGE_QUEUES 的數值最大可能是

8 \times 2^{14}

所以若不進行化簡而直接做整數除法的話會運算的成本，因此我們可以使用 __builtin_ffs 將被除數與除數先行化簡

#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 的範圍已知，所以如果經過 ffs 的化簡後則可能的除數剩下

1, 3, 5, 7

四種可能，除去被除數為 1 的情況，CASES 至少要包括

(b) 3
(d) 5
(f) 7

三個情況才行。

2020q3 Homework4 (quiz4)

作業要求

測驗 `1`

測驗 `2`

AAA

BBB

CCC

修改實作

測驗 `3`

`naive.c` 實作的問題

測驗 `4`

參考資料

tags: `sysprog2020`

2020q3 Homework4 (quiz4)

作業要求

測驗 1

測驗 2

AAA

BBB

CCC

修改實作

測驗 3

naive.c 實作的問題

測驗 4

參考資料

tags: sysprog2020

Read more

Banana Pi R4 - Debricking Guide

Interesting Facts of Pthread

OS HW1: Benchmark Your Computer Black Box

程式設計(二) Lab 3 講解

測驗 `1`

測驗 `2`

測驗 `3`

`naive.c` 實作的問題

測驗 `4`

tags: `sysprog2020`