---
tags: linux2024
---

# [2024q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 4 週測驗題

:::info
目的: 檢驗學員對 bitwise 和 [rbtree](https://hackmd.io/@sysprog/linux-rbtree) 的認知
:::

==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSe1JKHvdSyEWpkMux5YQ7uReAC4BJw0hp5LykxzF_M6mHwF_A/viewform)== (針對 Linux 核心「設計」課程)
==[作答表單: 測驗 3](https://docs.google.com/forms/d/e/1FAIpQLSfmtwv2i53ID3mlTF3ST4p1kHnP066ooTKc14KyUhY6hmeKtQ/viewform)== (針對 Linux 核心「實作」課程)

### 測驗 `1`

[population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `popcount` 指令，`popcount` 可處理 16-bit, 32-bit, 64-bit 整數。

對應到 C 程式的實作:

unsigned popcount_naive(unsigned v)
{
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

函式 `popcount_naive()` 利用不斷清除 LSB 直到輸入的數值 `v` 為 0。

`v &= (v - 1)` 的作用是將 LSB 設為 0 (**reset LSB**) 舉例來說，假設輸入數值為 `20`:

0001 0100  # 20          ; LSB in bit position 2
0001 0011  # 20 - 1
0001 0000  # 20 & (20 - 1)

> 類似的操作還有 `x & -x`，將 `x` 的 LSB 取出 (**isolate LSB**)

`n = -(~n)` 等同 `n++`，因為在二補數系統中，
$-n =\ \sim n + 1$
$-(\sim n) = n + 1$

因此 `popcount_naive()` 的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作:

unsigned popcount_branchless(unsigned v)
{
    unsigned n;
    n = (v >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;

    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v *= 0x01010101;                                     

    return v >> 24;
}

對於一個 32 bit 的無號整數，popcount 可以寫成以下數學式:

$popcount(x) = x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - ... - \left \lfloor{{\dfrac{x}{2^{{31}}}}}\right \rfloor$

假設 $x = b_{31}...b_3b_2b_1b_0$，先看看 $x[3:0]$ 4 個位元，用以上公式可以計算得:

$(2^3b_3 + 2^2b_2 + 2^1b_1 + 2^0b_0) -
(2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$
> $\left \lfloor{{\dfrac{x}{2}}}\right \rfloor$ 相當於 C 表達式中 `x >> 1`

稍微改寫可得到:
$(2^3 - 2^2 - 2^1 - 2^0)b_3 + (2^2 - 2^1 - 2^0)b_2 + (2^1 - 2^0)b_1 + 2^0b_0$

因此 popcount 的一般式可改寫為:
$popcount(x) = \sum\limits_{n=0}^{31} {}(2^n - \sum\limits_{i=0}^{n-1} 2^{i})b_n = \sum\limits_{n=0}^{31}b_n$

因為 $2^n - \sum\limits_{i=0}^{n-1} 2^{i} = 1$，只要對應的 $b_n$ 為 1，這個 bit 就會在 popcount 的總和中加一，剛好對應 `popcount_naive()`，因此映證上述數學式確實可計算出 population count。

且一個 32 位元無號整數最多有 32 個 1 (set bit)，剛好可用一個 byte 表示，所以可分成幾個區塊平行計算，最後再全部加總到一個 byte 中，進行避免檢查 32 次。

`popcount_branchless` 實作一開始以**每 4 個位元 (nibble) 為一個單位**計算 1 的個數，利用最初的公式計算 $x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - \left \lfloor{{\dfrac{x}{8}}}\right \rfloor$

關鍵的程式碼，逐行解釋:

n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;

1. `n = (v >> 1) & 0x77777777` : 將輸入數值 `v` 除以 2，得到 $\left \lfloor{{\dfrac{v}{2}}}\right \rfloor$

    b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0  // v
       0 b_31 b_30 b_29 ...  0 b7 b6 b4  0 b3 b2 b1  // (v >> 1) & 0x77777777

2. `v -= n` : 計算結果相當於 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor$
3. `n = (n >> 1) & 0x77777777` : 再對 `n` 除以 2，得到 $\left \lfloor{{\dfrac{v}{4}}}\right \rfloor$
4. `v -= n` : 計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor$
5. 和 6. 重複同樣動作

最後這段結束後計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor - \left \lfloor{{\dfrac{v}{8}}}\right \rfloor$，得到每 4 個位元為一個單位中 set bit 的個數

**`v = (v + (v >> 4)) & 0x0F0F0F0F`** : 將每 4 個位元中 set bit 的個數加到 byte 中:
1. 假設 $B_n$ 代表第 n 個 nibble (4 位元) 中的數值

    B7 B6 B5 B4 B3 B2 B1 B0  // v
     0 B7 B6 B5 B4 B3 B2 B1  // (v >> 4)

2. 加總可得到:

    // (v + (v >> 4))
    B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0)

3. 最後使用 `0x0F0F0F0F` 做 mask 可得

    // (v + (v >> 4)) & 0x0F0F0F0F
    0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)

**`v *= 0x01010101`** : 在最後一道敘述中，將 `v` 乘上 `0x01010101`。寫成直式如下

                         0 A6  0 A4  0 A2  0 A0
                      x  0  1  0  1  0  1  0  1
---------------------------------------------------
                         0 A6  0 A4  0 A2  0 A0
                   0 A6  0 A4  0 A2  0 A0  0
             0 A6  0 A4  0 A2  0 A0  0
       0 A6  0 A4  0 A2  0 A0  0
---------------------------------------------------
                            ↑_______________________A6+A4+A2+A0

我們可發現期望輸出就在原本 $A_6$ 的位置 ($2^7$)，因此將 `v` 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。
* 假設 $A = B_7 + B_6$, $B = B_5 + B_4$, $C = B_3 + B_2$, $D = B_1 + B_0$, 根據分配律可得:

    v * 0x01010101 = 
    (A + B + C + D)  (B + C + D)      (C + D)          (D)
    |<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|

**`return v >> 24`** : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。

GCC 提供對應的內建函式:
> `__builtin_popcount(x)`: 計算 x 的二進位表示中，總共有幾個 `1`

使用示範：

int x = 5328; // 00000000000000000001010011010000
printf("%d\n",  __builtin_popcount(x)); // 5

兩個整數間的 Hamming distance 為其二進位的每個位元的差

Example :
1 (0 0 0 1)
4 (0 1 0 0)

hamming distance = 2

| A $\oplus$ B | B = 0 | B = 1 |
| -------- | -------- | -------- |
| A = 0 | 0 | 1 |
| A = 1 | 1 | 0 |

`A ^ B`　就為二進位中兩數字的每個位元的差，再透過　popcount() 就可以得到答案

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

針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，考慮以下程式碼:

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0;i < numsSize;i++)
        for (int j = 0; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> AAAA;
}

從 popcount 角度出發，時間複雜度就被限制在 $O(n^{2})$。
以下嘗試從位元展現的樣貌，觀察 Total Hamming Distance 的規則。

digraph A{
b [shape=record  fontsize=24  label="{ n 'th bit|input 7|  input 5| input 10|input 17 }|{ 4|0|  0| 0|1 }|{ 3|0| 0| 1 |0}|{ 2|1| 1| 0 |0}|{ 1|1| 0| 1 |0}|{ 0|1| 1| 0 |1}"]
}

1. 第 0 個 bit 觀察 :
全部都是 1 -> Hamming Distance = 0
2. 第 1 個 bit 觀察 :
1 有一個，其餘皆為 0
可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1)
3. 第 2 個 bit 觀察 :
1 有兩個，其餘皆為 0
Hamming Distance (2)* (numsize - 2)

以 bit 找規則:
> 所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance

請補完程式碼。

:::success
延伸問題：
1. 參照《[Hacker's Delight](https://en.wikipedia.org/wiki/Hacker%27s_Delight)》和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。
2. 不依賴 popcount，嘗試以上述歸納的規則，針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) 撰寫出更高效的程式碼。
:::

---

### 測驗 `2`

摘錄自 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf):

**Remainder by Summing digits**
如何不使用任何除法就算出某數除以另一個數的餘數呢？若除數符合 $2^k \pm 1$，則可運用以下手法來達成這個目的。

若 $a \equiv b (mod \ \ m)$ 且 $c \equiv d (mod \ \ m)$ ，則 $a + c \equiv b + d (mod \ \ m)$ 且 $ac \equiv bd (mod \ \ m )$

假設
$$
a = q_a m + r_1, b = q_b m + r_1, c = q_c m + r_2, d = q_d m + r_2
$$

再進行運算。

以除數為 3 為例， $1 \equiv 1 (mod \ \ 3)$ 且 $2 \equiv -1 (mod \ \ 3)$ ，將後者不斷的乘上前者可得
$$
2^k \equiv \begin{cases}
1 (mod \ \ 3), \ \ k \ \ even\\
-1 (mod \ \ 3), \ \ k \ \ odd\\
\end{cases}
$$

因此若 n 的二進位表示為 $b_{n-1}b_{n-2}\cdots b_1 b_0$ ，則 $n = \sum_{i=0}^{n-1} b_i\cdot 2^i$ ，由以上的推論可得 $n \equiv \sum_{i=0}^{n-1} b_i\cdot (-1)^i \ \ (mod \ \ 3)$ 。
將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。
位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 。
利用以下定理可以進一步化簡。

$popcount(x \And \overline{m}) - popcount(x \And m) = popcount(x \bigoplus m) - popcount(m)$

於是 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 可以寫為 `n = popcount(n ^ 0xAAAAAAAA) - 16` ，將此式重複應用於得到的 `n` 上直到 `n` 介於 0~2 ，但為了避免 `n` 變成負數，我們要將它加上一個足夠大的 3 的倍數，文中的例子是加上 39 。範例程式如下

int mod3(unsigned n)
{
    n = popcount(n ^ 0xAAAAAAAA) + 23;
    n = popcount(n ^ 0x2A) - 3;
    return n + ((n >> 31) & 3);
}

另一種變形是利用 lookup table 。

int mod3(unsigned n)
{
    static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
    n = popcount(n ^ 0xAAAAAAAA);
    return table[n];
}

`tictactoe.c` 程式統計隨機的井字遊戲，參考執行輸出如下:

Win probability for first move with random agents:
0.115 0.102 0.116 
0.102 0.131 0.101 
0.116 0.102 0.116 
Player 1 won 584650 times
Player 2 won 288379 times
126971 ties
0.047604 seconds
21.006638 million games/sec

程式碼可見: [tictactoe.c](https://gist.github.com/jserv/9088f6f72a35a1fcaaf1c932399a5624) (部分遮蔽)

其中 `BBBB` 是 hex literal，`CCCC` 是十進位整數。以最精簡的形式撰寫。

:::success
延伸問題：
1. 參照《[Hacker's Delight](https://en.wikipedia.org/wiki/Hacker%27s_Delight)》和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。
2. 將上述手法應用於[第三次作業](https://hackmd.io/@sysprog/linux2024-ttt)中，追求更有效的賽局判定機制。
:::

---

### 測驗 `3`

> 搭配 [Linux 核心原始程式碼巨集: `container_of`](https://hackmd.io/@sysprog/linux-macro-containerof), [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)

考慮 XTree^名稱沒特別意思，不用去Google搜尋^ 是個嘗試兼具 AVL tree 和 red-black tree 部分特性的 binary search tree (BST) 實作，著重在快速的 insert/delete 操作且合理的 lookup 速度。

AVL tree 可確保每個節點的左右子樹高相差不超過 `1`，因此每個節點需要儲存目前高度來計算 balance factor 來決定是否需要旋轉 (rotate)。

red-black tree 則藉由以下規則來達到平衡：
1. 不能有兩個紅色節點相連;
2. 所有從該節點走到其子樹下的末端節點 (leaf) 的上之黑色節點數量必定

XTree 的平衡機制與 AVL tree 相似，利用 hint 來評估是否需要做 rotate，然而 xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。

以下是簡化的圖示，不區分左右節點。

1
∟———2
     ∟———8
          ∟———16
               ∟———33
                    ∟———73
                         ∟———82
                              ∟———83
                                   ∟———91
                                        ∟———1000
                                             ͱ———95

假設目前的 XTree 已經有 1000, 1, 2, 8 插入，接著插入 16 來觀察

- [ ] `xt_insert` 前

digraph Tree{
    graph[ordering=out]
    null0 [shape=point][color=white]
    null1 [shape=point][color=white]
    null2 [shape=point][color=white]

    1 -> 2
    1 -> null0[style=invis]
    2 -> 1000
    2 -> null1[style=invis]
    1000 -> null2[style=invis]
    1000 -> 8
}

- [ ] `xt_update` 前

digraph Tree{
    graph[ordering=out]
    null0 [shape=point][color=white]
    null1 [shape=point][color=white]
    null2 [shape=point][color=white]
    null3 [shape=point][color=white]

    1 -> 2
    1 -> null0[style=invis]
    2 -> 1000
    2 -> null1[style=invis]
    1000 -> null2[style=invis]
    1000 -> 8
    8 -> 16
    8 -> null3[style=invis]
}

- [ ] 對 16 進行 `xt_update`

由於 16 沒有左側或右側節點，因此不會做任何動作，但是由於 16 的 hint 為 0，所以會對其親代節點 8 進行更新。

- [ ] 對 8 做 `xt_update`

由於 `xt_balance` 為 1，因此不會做任何動作，但由於 8 的 hint 有經過更改 (0 -> 1) 所以會對其親代節點 1000 做進行更新。

- [ ] 對 1000 做 `xt_update`

旋轉完畢後，由於 1000 的 hint 沒有改變 (1->1)，因此結束。

digraph Tree{
    graph[ordering=out]
    null0 [shape=point][color=white]
    null1 [shape=point][color=white]
    null2 [shape=point][color=white]
    null3 [shape=point][color=white]

    1 -> 2
    1 -> null0[style=invis]
    2 -> 8
    2 -> null1[style=invis]
    8 -> 1000
    8 -> null3[style=invis]
    1000 -> null2[style=invis]
    1000 -> 16
}

由上可知，由於 hint 本身只要沒有改變且不等於 0，就不會往上更新，代表 XTree 只要更新末端節點時，發生 AVL 的 LR 或是 RL，就不會再往上更新。

參見 [XTree 的程式碼](https://gist.github.com/jserv/7374b3e031ec3a81441b1b93b008c5d2) (部分遮蔽)。

作答規範：
* `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF` 皆為表示式
* `BBBB` 和 `DDDD` 為 `xt_` 開頭的表示式
* 不包含空白，以最精簡的形式撰寫

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作
> 考慮到循序輸入和亂序輸入的狀況
3. 設計效能評比程式，探討上述程式碼和 Linux 核心 red-black tree 效能落差
:::