2024q1 第 4 週測驗題

目的: 檢驗學員對 bitwise 和 rbtree 的認知

作答表單: 測驗 1-2 (針對 Linux 核心「設計」課程)
作答表單: 測驗 3 (針對 Linux 核心「實作」課程)

測驗 1

population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。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-\lfloor {\displaystyle \frac{x}{2}}\rfloor -\lfloor {\displaystyle \frac{x}{4}}\rfloor -...-\lfloor {\displaystyle \frac{x}{2^{31}}}\rfloor$

假設

$x=b_{31}...b_3{b}_2{b}_1{b}_0$，先看看

$x[3:0]$ 4 個位元，用以上公式可以計算得:

$(2^3{b}_3+2^2{b}_2+2^1{b}_1+2^0{b}_0)-(2^2{b}_3+2^1{b}_2+2^0{b}_1)-(2^1{b}_3+2^0{b}_2)-2^0{b}_3$

$\lfloor {\displaystyle \frac{x}{2}}\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^0{b}_0$

因此 popcount 的一般式可改寫為:

$popcount(x)=\sum _{n=0}^{31}(2^n-\sum _{i=0}^{n-1}{2}^i)b_n=\sum _{n=0}^{31}{b}_n$

因為

$2^n-\sum _{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-\lfloor {\displaystyle \frac{x}{2}}\rfloor -\lfloor {\displaystyle \frac{x}{4}}\rfloor -\lfloor {\displaystyle \frac{x}{8}}\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，得到
   $\lfloor {\displaystyle \frac{v}{2}}\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-\lfloor {\displaystyle \frac{v}{2}}\rfloor$
3. n = (n >> 1) & 0x77777777 : 再對 n 除以 2，得到
   $\lfloor {\displaystyle \frac{v}{4}}\rfloor$
4. v -= n : 計算出
   $v-\lfloor {\displaystyle \frac{v}{2}}\rfloor -\lfloor {\displaystyle \frac{v}{4}}\rfloor$
5. 和 6. 重複同樣動作

最後這段結束後計算出

$v-\lfloor {\displaystyle \frac{v}{2}}\rfloor -\lfloor {\displaystyle \frac{v}{4}}\rfloor -\lfloor {\displaystyle \frac{v}{8}}\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，考慮以下程式碼:

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 的規則。

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

請補完程式碼。

延伸問題：

1. 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理。
2. 不依賴 popcount，嘗試以上述歸納的規則，針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。

---

測驗 2

摘錄自 Hacker's Delight:

Remainder by Summing digits
如何不使用任何除法就算出某數除以另一個數的餘數呢？若除數符合

$2^k\pm 1$，則可運用以下手法來達成這個目的。

若

$a\equiv b(modm)$ 且

$c\equiv d(modm)$ ，則

$a+c\equiv b+d(modm)$ 且

$ac\equiv bd(modm)$

假設

$$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(mod3)$ 且

$2\equiv -1(mod3)$ ，將後者不斷的乘上前者可得

$$2^k\equiv \{\begin{array}{l}1(mod3),keven\\ -1(mod3),kodd\end{array}$$

因此若 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(mod3)$ 。
將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。
位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為 n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA) 。
利用以下定理可以進一步化簡。

$popcount(x\mathrm{\&}\bar{m})-popcount(x\mathrm{\&}m)=popcount(x⨁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 (部分遮蔽)

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

延伸問題：

1. 參照《Hacker's Delight》和 CS:APP 第二章，解釋上述程式碼運作原理。
2. 將上述手法應用於第三次作業中，追求更有效的賽局判定機制。

---

測驗 3

搭配 Linux 核心原始程式碼巨集: container_of, Linux 核心的紅黑樹

考慮 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 前

• xt_update 前

• 對 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)，因此結束。

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

參見 XTree 的程式碼 (部分遮蔽)。

作答規範：

• AAAA, BBBB, CCCC, DDDD, EEEE, FFFF 皆為表示式
• BBBB 和 DDDD 為 xt_ 開頭的表示式
• 不包含空白，以最精簡的形式撰寫

延伸問題:

1. 解釋上述程式碼運作原理
2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作

   考慮到循序輸入和亂序輸入的狀況

3. 設計效能評比程式，探討上述程式碼和 Linux 核心 red-black tree 效能落差