owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework4 (quiz3+4)
contributed by < `yinghuaxia` >
## [第三週測驗](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗一
測驗一當中使用以下的程式碼計算平方根，以下解析對其演算法：
```c
#include <math.h>
int i_sqrt(int N)
{
int msb = (int) log2(N);
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
首先我們先對傳入的數字 $N$ 做 `(int) log2(N)` 的運算，意思是找到 $N$ 這個數字轉成二進位後的 most signficant bit( `msb` )，原理是因為 $x = \log_2(N)$ 意即 $2^x = N$，因此對 $x$ 取整數就可以得知 $N$ 換成二進位的最高 bit 位置。接著我們將讓 `int a = 1 << msb`，讓 `a` 為 2 的 `msb` 次方，也就是讓 `a` 在小於或等於 $N$ 的情況下為 2 的最高次方。
接著先初始化 `int result = 0`，並且進入一個終止條件為 `a == 0` 的 while 迴圈。While 迴圈裡面的判斷是為：如果 `(result + a) ^ 2 <= N`，意思是 `result + a` 比 `N` 開根號的數值還要小，所以將 `result += a` 使得 `result` 逐漸逼近 $N$ 的開根號；否則代表目前 `a` 的平方仍大於 `N`，因此不對 `result` 做任何動作，然後讓 `a` 變成原本的 $\frac{1}{2}$ 再繼續進行判斷及運算。
可以改寫 `i_sqrt` 使其不用依賴 $\log_2$ 的運算：
```c
int msb = 0;
int n = N;
while (n > 1) {
n >>= 1;
msb++;
}
```
這邊的寫法也就是當 $N$ 大於 1 時，讓他不停的向右移動一個 bit，計算總共移動了幾個 bit 就可以知道 $N$ 的 most significant bit 是在哪一位。
### 測驗二
以下的程式進行 mod 10 和 div 10 的操作：
```c
static void str_add(char *b, char *a, char *res, size_t size)
{
int carry = 0;
for (int i = 0; i < size; i++) {
int tmp = (b[i] - '0') + (a[i] - '0') + carry;
carry = tmp / 10;
tmp = tmp % 10;
res[i] = tmp + '0';
}
}
```
這個函式輸入四個參數：
`b`：指向第一個字串的指標，代表的是一個數字
`a`：指向第二個字串的指標，代表的是一個數字
`res`：指向一個字串的指標，代表的是結果會被儲存的位置
`size`：字串的大小
`carry` 這個變數被初始化為 0，用來儲存在加法時的進位
`-'0'` 的目的是為了將字串轉換為數字的形式，並對兩個字串進行從個位數開始的加法運算。將兩個數值該位數的相加暫存到 `tmp` 中，如果在該位數兩個數值相加有進位的情形，會因為 `tmp / 10` 操作而把進位的數值存到 `carry` 這個變數中；接著對 `tmp % 10` 得到該位數的數值。透過 for 迴圈對每一個位數做相同的操作，就可以得到兩個數值相加的結果。
### 測驗三
以下程式是進行 $\log_2$ 運算的方式，對其內容作解析：
```c
int ilog2(int i)
{
int log = -1;
while (i) {
i >>= 1;
log++;
}
return log;
}
```
先將輸入的 `i` 轉換為二進位，因為 $log = \log_2(i)$ 意即 $2^{log} = i$，我們想要求的是 $i$ 可以被轉換為 2 的冪，因此透過 while loop 來對 $i$ 做逐個 bit 的右移，用 `log` 來紀錄 `i` 的二進位總共有幾個 bit 即可得到取 $\log_2$ 的結果。
改寫成以下：
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= AAAA) { //AAAA = 65536
result += 16;
i >>= 16;
}
while (i >= BBBB) { //BBBB = 256
result += 8;
i >>= 8;
}
while (i >= CCCC) { //CCCC = 16
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
這個方式可以更快速的知道輸入的 `i` 換成二進位之後有幾個 bit。一開始在 while loop 裡面會判斷 `i` 是否大於 $2^{16}$，如果這個條件為真，則代表 `i` 的 msb 後至少有 16 個 0，因此可以直接把 `result` 加上 16，下面的判斷是也是同樣的道理，希望可以一次移動較多 bit 來減少逐個移動的時間成本。因此 `BBBB` 我們填入 $2^{8} = 256$；`CCCC` 填入 $2^4 = 16$；`DDDD` 填入 $2^1$。
我們也可以使用 gcc 內建函式 `__builtin_clz` 來達到一樣的結果。該內建函式在 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fclz) 的解釋是：
> Built-in Function: `int __builtin_clz (unsigned int x)`
Returns the number of leading 0-bits in x, starting at the most
significant bit position. If x is 0, the result is undefined.
也就是這個函式會回傳從最高位 (msb) 之前的連續的 0 的個數，如果輸入 0 則行為不會被定義。可以使用下面的程式碼對輸入值進行取 $\log_2$：
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(DDDD)); //DDDD = v | 1
}
```
`31 - (__builtin_clz(v | 1))`：這個操作會將 `v` 的 least significant bit 設為 1，確保可以得到至少有一個 bit 不是 0 的數值，再透過 `__builtin_clz` 函式找到 msb 前面有幾個連續的 0，用 31 位元減掉前面連續的 0 的部分就可以知道 `v` 的最高位元的位置。因為 `v` 最多只有連續的 31 個零 (因為 `v | 1` 的操作)，因此使用 31 對 `__builtin_clz` 得到的結果做相減。
在 Linux 核心提供 [include/linux/log2.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/log2.h) 標頭檔，裡面包含一些基於 $\log_2$ 的運算，像是 `__ilog2_u32`、`__ilog2_u64` 等，主要會使用在處理記憶體管理和資料結構等相關的任務時會使用到。舉例來說：
* `linux / arch`： 跟架構相關的檔案裏面會使用 `log2`，來做記憶體相關的管理。
* `drivers/`：在處理裝置初始化、配置相關或是處理資料時會使用到 `log2`，如 [drivers/dma/xilinx/zynqmp_dma.c](https://github.com/torvalds/linux/blob/317c7bc0ef035d8ebfc3e55c5dde0566fd5fb171/drivers/dma/xilinx/zynqmp_dma.c#L536)所示，該函式主要是在配置 `ZynqMP DMA channel`。
```c
static void zynqmp_dma_config(struct zynqmp_dma_chan *chan)
{
u32 val, burst_val;
val = readl(chan->regs + ZYNQMP_DMA_CTRL0);
val |= ZYNQMP_DMA_POINT_TYPE_SG;
writel(val, chan->regs + ZYNQMP_DMA_CTRL0);
val = readl(chan->regs + ZYNQMP_DMA_DATA_ATTR);
burst_val = __ilog2_u32(chan->src_burst_len);
val = (val & ~ZYNQMP_DMA_ARLEN) |
((burst_val << ZYNQMP_DMA_ARLEN_OFST) & ZYNQMP_DMA_ARLEN);
burst_val = __ilog2_u32(chan->dst_burst_len);
val = (val & ~ZYNQMP_DMA_AWLEN) |
((burst_val << ZYNQMP_DMA_AWLEN_OFST) & ZYNQMP_DMA_AWLEN);
writel(val, chan->regs + ZYNQMP_DMA_DATA_ATTR);
}
```
其中 `burst_val = __ilog2_u32(chan->src_burst_len)` 透過 `ilog2_u32` 得到 register 設定 burst length 的 offset。
* linux / fs / ocfs2：是一個共用磁碟檔案系統，主要用於 Oracle Real Application Clusters (RAC) 環境。他提供 Linux 系統在運行 Oracle 資料時可以有共用儲存存取的功能，提升系統的可用性和可擴充性。在 OCFS2 中，ilog2 用於計算區塊大小、確定資料結構索引或最佳化儲存分配演算法等任務。
### 測驗四
[Exponentially Weighted Moving Average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 是一種取平均的方式。其原理是將較早的輸出搭配較低的權重，意思是較早的輸出對現在的輸出影響力較低；反之，較晚的輸出則對現在輸出的影響力較高。而權重與輸出的搭配與 $(1 - \alpha) ^ t$ 有關。$\alpha:$ 權重隨時間過去降低的程度； $t:$ 時間。以下對 EWMA 的實作做說明：
```c
#include <assert.h>
/* Exponentially weighted moving average (EWMA) */
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
定義一個 `ewma` 的架構，包含三個 `unsigned long` 型態的變數，分別是 `internal`、`factor` 和 `weight`。
* `internal` 是用來儲存 moving average 現在的狀態，會隨著新的輸出被加到 moving average 中而更新。
* `factor` 表示的是 `internal` 的縮放倍率，影響 `internal` 的精度和粒徑。
* `weight` 代表新舊輸出的權重，`weight` 愈高表示新的輸出對整體的平均有較大的影響；反之則表示可以更長時間的保留舊的輸出所造成的影響。通常會被設定為 2 的冪使得計算有效率。
```c
/* This section contains universal functions designed for computing the EWMA.
* It maintains a structure housing the EWMA parameters alongside a scaled
* internal representation of the average value, aimed at minimizing rounding
* errors. Initialization of the scaling factor and the exponential weight (also
* known as the decay rate) is achieved through the ewma_init(). Direct access
* to the structure is discouraged; instead, interaction should occur
* exclusively via the designated helper functions.
*/
/**
* ewma_init() - Initialize EWMA parameters
* @avg: Average structure
* @factor: Scaling factor for the internal representation of the value. The
* highest achievable average is determined by the formula
* ULONG_MAX / (factor * weight). To optimize performance, the scaling
* factor must be a power of 2.
* @weight: Exponential weight, also known as the decay rate, dictates the rate
* at which older values' influence diminishes. For efficiency, the weight
* must be set to a power of 2.
*
* Initialize the EWMA parameters for a given struct ewma @avg.
*/
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
}
```
`ewma_init` 對 EWMA 的參數進行初始化。在 `if` 判斷式中，如果 `weight` 和 `factor` 不是 2 的冪，則 assert 一個錯誤訊息，以確保這兩個參數的設置需要符合計算的效率。接著將 `avg` 的 `weight` 和 `factor` 分別設為 `weight` 和 `factor` 的對數，並將 `avg` 的 `internal` 設為 0，開始 EWMA 的計算。
```c
/**
* ewma_add() - Exponentially weighted moving average (EWMA)
* @avg: Average structure
* @val: Current value
*
* Add a sample to the average.
*/
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << EEEE) - avg->internal) +
// EEEE = avg -> weight
(val << FFFF)) >> avg->weight
// FFFF = avg -> factor
: (val << avg->factor);
return avg;
}
```
`ewma_add()` 函式實作了簡單的 EWMA 流程。判斷式會檢查 `avg -> internal` 是否為 0，若不為 0 則表示現在已經有輸出的數值存在 `avg -> internal` 中，那運算就需要遵從 EWMA 的公式，也就是將已經有的舊輸出乘上 $1 - weight$，因為我們的 `weight` 已經取過對數，因此我們可以使用平移的方式做乘法的運算，在程式碼中寫成 `((avg->internal << avg -> weight) - avg->internal)` 的形式，再加上新的輸出經過 `factor` 的調整後乘上權重；若為 0 則表示沒有已經存在的輸出數值，只需要將現在的輸出數值 `val` 根據 `avg -> factor` 做縮放並存在 `avg -> internal` 中。
```c
/**
* ewma_read() - Get average value
* @avg: Average structure
*
* Returns the average value held in @avg.
*/
unsigned long ewma_read(const struct ewma *avg)
{
return avg->internal >> avg->factor;
}
```
此函數回傳儲存在 ewma 結構 `avg` 中的平均值，並按 `factor` 右移。透過右移 `avg->factor`，函數會撤銷在 EWMA 計算期間實施在平均值的縮放。
在 linux kernel 中，EWMA 可以用來平滑和預測資源的使用方式，以利於資源的分配與排程。舉例來說，CPU 資源的調度可以藉由 EWMA 的方式做動態的工作負載調整，像是在 [linux/kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 的 `util_est_update` 函式中，EWMA 的功能在於計算執行一個任務的虛擬運算時間，透過知道一個任務的虛擬運算時間，可以反應 CPU 的使用情況，進而影響一個任務的優先順率。`fair.c` 這個檔案本身實現了 Linux kernel 中的 CFS 調度器，旨在確保 CPU 資源的公平分配。
### 測驗五
延伸測驗三，計算 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 和 [log2](https://man7.org/linux/man-pages/man3/log2.3.html) 的組合並轉型成整數：
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
先將輸入值減 1（`x--`），這麼做的目的是確保如果 x 不是 2 的冪時，計算出的對數會向上取整。因為 `x--` 會將 x 減少 1，所以如果 x 原本是 2 的冪，減 1 後會導致其二進位表示最高位外的其他位全部為 1，而 x 原本不是 2 的冪時，減 1 會將最高位以外的第一個 1 轉換為 0。透過右移 x 的來檢查 x 的最高有效位元。每次，它都會檢查 x 是否大於 2 的某些冪（0xFFFF、0xFF、0xF 和 0x3），如果是，則設定 shift 對應的位元數。在每次右移操作後，將右移的位數添加到一個變數 r 中，這個變數儲存了最高非零位所在的位置。
最後回傳的值是 `(r | shift | x > 1) + 1`，`r` 和 `shift` 變數保存了找到的最高位的位置，而 `x > 1` 是判斷變數 `x` 是否大於 1，判斷為真則將最低位設置為 1；判斷為假則最低位為 0，需做此判斷的原因在於判斷 `x > 0x3` 時，在 `x == 0x2` 或 `x == 0x3` 的情況下，則 `shift` 為 0，透過多做這個判斷可以避免這個情形的發生。`+ 1` 的目的則是將整個表達式的值加 1，這是為了確保不論 `x` 是否為 2 的冪，結果都會向上取整。
## 第四週測驗
[題目](https://hackmd.io/@sysprog/linux2024-quiz4)
### 測驗一
popcount 是用來計算一個數值轉成二進位之後有多少位元為 `1`，以下進行實作說明：
```c
unsigned popcount_naive(unsigned v)
{
unsigned n = 0;
while (v)
v &= (v - 1), n = -(~n);
return n;
}
```
一開始先定義一個無號數來記錄被設置為 `1` 的位元數量，之後進入一個 while 迴圈做 bit 數的計算，其條件為 `v` 不為 `0`，也就是 `v` 中還有位元為 `1` 時會不斷進行運算。在迴圈中使用了一個叫做 [Brian Kernighan's](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwiP9Yb6irWFAxXnaPUHHUUTDkgQFnoECBwQAw&url=https%3A%2F%2Fyuminlee2.medium.com%2Fbrian-kernighans-algorithm-count-set-bits-in-a-number-18ab05edca93&usg=AOvVaw3WIaFt_UL3M2EmRi2lC0el&opi=89978449) 的演算法，其想法如下所述：
> Subtract one from n to flip bits after the rightmost set bit (including the rightmost set bit itself) and use n & (n-1) expression to clear the rightmost set bit of n until n becomes zero. The number of times we clear the rightmost set bit of n will be the set bit count.
做`v - 1` 的運算時，會將 `v` 當中最右邊的 `1` 位元變成 0，並將該位元右邊的 `0` 變成 `1`，再將 `v` 和 `v - 1` 做 `&` 的操作時，會將 `v` 最右邊的 `1` 位元變成 `0`。舉例 $v = 22 = 10110_2$ 來說 (下圖以 `n` 表示)：
> 出處: [Brian Kernighan's Algorithm: Count set bits in a number](https://yuminlee2.medium.com/brian-kernighans-algorithm-count-set-bits-in-a-number-18ab05edca93)
`n = -(~n)` 則是先將 `n` 取反，再對其取二補數，也就是再取反後加一，也因此這邊的操作就是在將 `n` 隨著 while 迴圈對 `v` 位元的計算加 1。
因此上面的 `popcount_naive` 執行時間會取決於輸入 `v` 的位元數量，為了將其變成常數時間複雜度的操作，我們做以下的改寫：
```c
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;
}
```
為了使用公式 $popcount(x) = x - \lfloor \frac{x}{2}\rfloor - \lfloor \frac{x}{4}\rfloor -...- \lfloor \frac{x}{2^{31}}\rfloor$ 來完成 popcount 的計算 (原理參見[第四週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1))，我們使用 `n = (v >> 1) & 0x77777777`的方式做運算。`v >> 1` 的操作其實就是在做 $\lfloor{\frac{x}{2}}\rfloor$ 的動作，對 `0x77777777` 做 `&` 運算其實是想要得到在 `v` 的每個 4 位元中計算出 1 的位元數，因為 $7 = 0111_{2}$。這樣做的好處是可用四位元 (即 [nibble](https://en.wikipedia.org/wiki/Nibble)) 為單位逐步計算出 32 位元數字中為 1 的位元數，不需要使用迴圈，進而提高運算效率。
經過三次 `v -= n` 的運算之後會得到 $v - \lfloor\frac{v}{2}\rfloor - \lfloor\frac{v}{4}\rfloor - \lfloor\frac{v}{8}\rfloor$
最後做 `v >> 4` 的原因是，我們在前面計算的 $v - \lfloor\frac{v}{2}\rfloor - \lfloor\frac{v}{4}\rfloor - \lfloor\frac{v}{8}\rfloor$ 會算出每 4 個位元的 `1` 位元數，因此我們將所得右移 4 個位元再與原數相加，經過 `0x0F0F0F0F` 的 masking 後就可以在奇數 byte 得到兩兩 byte 的 `1` 位元數相加數量，最後乘上 `0x01010101` 就可以在第 $2^7$ 位元處得到我們想要的 popcount 結果，因此向右移動 $2^6 = 24$ 個位元就可以在 LSB 得到最終回傳值。
兩個數值的 Hamming distance 可以藉由 `popcount` 巨集來求出所得。我們先對兩個數值做 [Exclusive or](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjz0fG3ybaFAxW2aPUHHWLLC9YQFnoECBYQAQ&url=https%3A%2F%2Fzh.wikipedia.org%2Fzh-tw%2F%25E9%2580%25BB%25E8%25BE%2591%25E5%25BC%2582%25E6%2588%2596&usg=AOvVaw2Agb7Pa0tLB52mnb8XvvBR&opi=89978449) 的運算，就可以將兩者位元相異處標示為 `1`，其餘標示為 `0`，接著再使用 `__builtin_popcount` 就可以得到答案。
```c
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; //AAAA = 1
}
```
給定的程式碼想要計算多個數值之間兩兩的 Hamming distance，但存取每個數值的兩個 for 迴圈皆是從 `0` 到 `numSize`，因此數與數之間的 Hamming distance 會被計算兩次，因此最後我們需要將 `total` 除以 2 來得到最後正確的結果，所以要將 `total` 往右移 1 個位元。
然而，如果我們直接將上面的程式碼提交到 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，會在測資有 10000 筆時發生 Time Limit Exceeded 的錯誤，是因為兩個 for 迴圈總共計算 `numsSize ^ 2` 次 popcount 的計算，但其實我們只需要做 $C^{numsSize}_2 = numsSize \times (numsSize - 1) / 2$ 次運算，因此將程式碼的 for 迴圈改成以下所示，並直接回傳 `total` 數值就可以通過。
```diff
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
int count = 0;
for (int i = 0;i < numsSize - 1;i++)
- for (int j = 0; j < numsSize;j++)
+ for (int j = i + 1; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
return total;
}
```
> 所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance
根據以上提示，我們就可以不用使用兩兩做 XOR 和 popcount 來得到所有數字之間的 Hamming distance。
> 第 0 個 bit 觀察 :
全部都是 1 -> Hamming Distance = 0
第 1 個 bit 觀察 :
1 有一個，其餘皆為 0
可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1)
第 2 個 bit 觀察 :
1 有兩個，其餘皆為 0
Hamming Distance (2)* (numsize - 2)
實作如下：
```c
int totalHammingDistance(int* nums, int numsSize) {
int ans = 0;
for(int i = 0; i < 32; i++){
int ones = 0;
for(int j = 0; j < numsSize; j++)
ones += nums[j] >> i & 0b1;
ans += ones * (numsSize - ones);
}
return ans;
}
```
第一層 for 迴圈存取數值中的 32 個位元，第二個 for 迴圈則是存取所有要比較的數值。透過 `ones = nums[j] >> i & 0b1` 可以知道有多少數字的 `i` 位元跟 `0b1` 做 `&` 為 `1`，也就可以透過 `ones * (numsSize - ones)` 得到該位元會造成的 Hamming distance 大小。
比較兩者執行時間，前者花了 1764 ms 而後者僅花了 19 ms，兩者的差異除了 for 迴圈執行的次數外，也需考慮巨集展開所耗費的成本。
### 測驗二
在除數符合 $2^k \pm 1$ 的情況下，可以用下述的方式算出某數除以另一數的餘數。根據[第四週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-2)中提出的歸納原理，以除數為 3 為例，餘數 $n$ 應為 $\Sigma_{i = 0}^{n - 1} \ b_i \cdot (-1)^i (mod\ 3)$。此公式可以寫成 `n = popcount(n & 0x55555555) - popcount(n & AAAAAAAA)`。`n & 0x55555555` 的意思是取 `n` 的奇數位元，`n & 0xAAAAAAAA` 的意思是取 `n` 的偶數位元，對應公式中偶數位元會乘上 $-1$，奇數位元會乘上 $1$，因此有上面呈現的寫法，解釋這個表示方式為 `n` 中奇數位和偶數位中 $1$ 的數量之差。
接著我們可以透過 $popcont(x \& \bar m) - popcount(x \& m) = popcount(x \oplus m) - popcount(m)$ 將 $n$ 表示為 `popcount(n ^ 0xAAAAAAAA)`，原因是因為當我們對 $n$ 和 `0xAAAAAAAA` 做 XOR 運算時，由於 `0xAAAAAAAA` 的二進位表示法為所有偶數位都為 $1$，所有奇數位都為 $0$，因此會將 $n$ 中偶數位的位元進行反轉，奇數位不變，因此省略原公式中將奇數位清零的動作。需要減去 $16$ 的原因在於我們忽略了減法借位的運算，偶數位在 $32$ 位元的數值中有 $16$ 個，因此需要將我們進行 XOR 忽略的 $16$ 進行扣除的動作，這樣就會造成結果介於 $-16$ 到 $16$ 間，因此需要再加上一個三的倍數來保證餘數為正，文中給的例子是加上 $39$。
[《Hacker's Delight》](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 中有說明選 $39$ 這個數值的原因：
> We want to apply this transformation again, until n is in the range 0 to 2, if possible. But it is best to avoid producing a negative value of n, because the sign bit would not be treated properly on the next round. A negative value can be avoided by adding a sufficiently large multiple of 3 to n. Bonzini’s code, shown in Figure 10–21, increases the constant by 39. This is larger than necessary to make n nonnegative, but it causes n to range from –3 to 2 (rather than –3 to 3) after the second round of reduction. This simplifies the code on the return statement, which is adding 3 if n is negative. The function executes in 11 instructions, counting two to load the large constant.
這個步驟可以防止 $n$ 在第二輪縮減之後範圍不會介於 $-3$ 到 $3$ 之間，讓回傳值不需要再執行「如果結果為負則加三」的動作。
下面舉例說明：
```c
int mod3(unsigned n)
{
n = popcount(n ^ 0xAAAAAAAA) + 23;
n = popcount(n ^ 0x2A) - 3;
return n + ((n >> 31) & 3);
}
```
首先，我們將 $n$ 和 `0xAAAAAAAA` 做 XOR 的運算，取 `popcount` 之後再加 $23$，避免 `n` 為負數。`0x2A` 展開是 `0x00101010`，也因此`n ^ 0x2A` 的運算會保留奇數位元，並改變第 2、4、6 位元的數值。
:::info
:bulb: 加上 $23$ 這個數值是否有特別原因？為何需要做 `popcount(n ^ 0x2A) - 3;` 及回傳 `n + ((n >> 31) & 3)`? 是否跟 tic-tac-toe 作業有關連？
:::
另外也可以透過計算 $n$ 和 `0xAAAAAAAA` 做 XOR 後做 `popcount` 得到的數值進行查表，得到我們要的結果。
針對 [tictactoe.c](https://gist.github.com/jserv/9088f6f72a35a1fcaaf1c932399a5624) 中部份被遮蔽的程式碼進行說明：
文件中的輸出是模擬一百萬次棋局的結果，棋盤的大小為 3 x 3，引此玩家有 9 種可能的位置選擇。根據 [vax-r](https://hackmd.io/@vax-r/linux2024-homework4#%E6%B8%AC%E9%A9%97%E4%BA%8C1) 的解釋：
> 相較於把下棋看成在九宮格中選擇一格並標記，可以把棋局看成是 8 種可能的路線（三條橫線、三條縱線、兩條對角線，分別對應到 uint32_t 以 16 進位表示的不同位元，第一條橫線為 msb，第二條橫線為 msb - 1，依此類推。
觀察 `move_mask` 可以發現，`move_mask[0] = 0x40040040`，是針對將九宮格中第一、五、九的位置標記來贏得遊戲，也就是第一列：同理 `move_mask[1]` 和 `move_mask[2]` 分別代表的是第二列和第三列。如果對三者做 OR 運算會得到 `0x70044444`，也就是當有連成一直線的情況發生時會有一個位元為 7，因此透過將 `board + 0x11111111` 的操作，再和 `0x88888888` 做 AND 運算就能得知是否有獲勝的情況發生。
```c
/* Determine if the tic-tac-toe board is in a winning state. */
static inline uint32_t is_win(uint32_t player_board)
{
return (player_board + BBBB) & 0x88888888; //BBBB = 0x111111111
}
```
由於 `x & UINT32_C(0x7FFF)` 的操作只會保留最低的 15 位，因此在 `CCCC` 填入 $15$ 來減小 `x` 的數值避免 overflow 的情況發生。
```c
static inline int mod7(uint32_t x)
{
x = (x >> CCCC) + (x & UINT32_C(0x7FFF)); //CCCC = 15
/* Take reminder as (mod 8) by mul/shift. Since the multiplier
* was calculated using ceil() instead of floor(), it skips the
* value '7' properly.
* M <- ceil(ldexp(8/7, 29))
*/
return (int) ((x * UINT32_C(0x24924925)) >> 29);
}
```
### 測驗三
Google Drive
Gist
Clipboard
Sign in with Wallet
