---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `YiChainLin` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
實驗的 gcc 編譯器版本
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
```
## 測驗1
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`，其作用是依據給定的範圍，產生連續的 [bitmask](https://en.wikipedia.org/wiki/Mask_(computing))，例如:
* GENMASK(6, 4) 產生 01110000~2~
* GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
* 本題要根據示例要的結果是要產生在二進位元中，第 h + 1 (high) 位 ~ 第 l + 1 (low) 位的 `1` 遮罩
* 在無號整數下，使用[邏輯移位(logical shift)](https://en.wikipedia.org/wiki/Logical_shift) shift 移位補 0 的效果，完成本題
* 以範例來說我們預期的 `bitmask` 為:
```
GENMASK(39, 21):
0000...00111...111111000...000 (64位元)
^ ^
(第40位) (第22位)
```
在 `((~0UL) >> (LEFT))` 敘述中要能產生最高位前面的 0，所以透過邏輯移位補 0 的特性中，要向右 shift 64 - (h + 1)，64 位元是來自於題目的架構，如果是 32 位元的架構則 為 31 - h
:::success
LEFT = 63 - h
:::
所以對應這個敘述可以產生這樣的結果:
```
000..00001111111...11111 (64位元)
^
(第40位)
```
再來就是要將尾段清零，透過與 0 的 `&` 計算去除，所以透過向左移位補 0 的特性，可以補 `l` 個數的 0
所以在 `((~0UL) >> (l) << (RIGHT))` 的敘述中，透過右移補 0 的方式產生，先進行向右移位 `l` 次，再左移 `l`次
:::success
RIGHT = l
:::
```
右移 l: 再左移 l:
0000....00111...11111 (64位元) 111...1100...00 (64位元)
^ ^
(第 63 - l 位) (第 l 位)
```
最後再將 high 的位移結果加入進行 `&` 運算
```
000..000011111111..11111 (64位元)
& 111..1111111111100...000
...........................
000..000011111110...0000 <-產生 (h + 1) ~ (l + 1)位的 1 bitmask
```
:::info
有一點比較不懂的是在 `(~0UL) >> (l)` 這段敘述中，為什麼要右移，如果只是想要在尾端補 0 的時候，那只要左移 `l` 次就可以了
也就是在右半部分只要 `(~0UL) << (l)` 能達到一樣的效果
:::
## 測驗2
考慮以下程式碼
```c
struct foo;
struct fd {
struct foo *foo;
unsigned int flags;
};
enum {
FOO_DEFAULT = 0,
FOO_ACTION,
FOO_UNLOCK,
} FOO_FLAGS;
static inline struct fd to_fd(unsigned long v)
{
return (struct fd){EXP1, v & 3};
}
```
函式 `fo_fd` 接受指定的地址 `v`，填入一個 `fd` 結構體，並確保第一個成員的地址，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 `align_down`)。
:::info
>參考[C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory?type=view)
* 首先要先了解電腦的 CPU 如何抓取資料，CPU 抓取資料的單位是 4 byte 或是 8 byte (分別為 32 位元與 64 位元的電腦架構)，在處理上才會快速，不會想一個一個 1 byte 抓取
* 若資料的分布狀況不在 4 byte 的情況下，如下圖，分別抓取藍色的資料與黃色的資料，在透過移位(shift)的方式調整所需要的資料，最後再結合一起
* 但是這樣的做法比較沒有效率，所以編譯器在分配記憶體時就會做 data alignment 的動作
* 舉例在 int 的 alignment 方式，int 為 4 byte 、 char 為 1 byte ，理論上加起來要為 5 byte ， 但是 char 為了 alignment int，所以會從 1 byte 多加 3 個 byte，變成 8 byte 的形式，所以 CPU 就能因為這樣的倍數關係不會降低抓取資料的速度
```c
struct s1 {
char c;
int a;
}
```
:::
* 對 4 個位元組向下對齊，因此要將 `v` 的值處理能被 4 整除的數字，所以在二進位元的表示中，在最後兩位的 bit 要等於 0
* 所以 3 的二進位元為 00..0011~2~ ， 在透過取反獲得 11..1100~2~ ，再透過 `&` 運算子可將 v 的最後兩個 bits 變成 00~2~
* 回傳的結構是 `struct fd` 所以在將型態強制轉型成結構內的型態 `struct foo *` ，始能將 `v` 記憶體位址取址
:::success
EXP1 = (struct foo *)(v & ~3)
:::
測試:
```c
long long a = 5;
struct fd test = to_fd(a);
printf("alignment : %p %p\n", &test.foo, &test.flags);
```
結果:
```
alignment : 0x7fff11a83dd0 0x7fff11a83dd8
```
可以看到在記憶體的表現上以 8 byte 的空間分配
## 測驗3
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | (EXP2);
x = ((x & 0xAA) >> 1) | (EXP3);
return x;
}
```
* 觀察函式中 `0xCC` 與 `0xAA` 在 8 位元下的二進位表示分別為 `11001100` 與 `10101010`，利用 `&` 的運算子，可將對應位置的 bit 紀錄，也就是指定相對應的 bit 進行 shift
* 可得知在交換順序時候為
* 前 4 個與後 4 個 bit 交換
* 再來鄰近每兩個 bit 成對交換
* 最後將鄰近一組的 2 個 bit 互換
* 所以在左半部分都是對 x 數值向右 shift，可推測右半部分是對 x 數值向左 shift
* 因此將 `0xCC` 與 `0xAA` 的二進位取反:
```
0xCC : 11001100
~0xCC : 00110011 /* 0x33 */
0xAA : 10101010
~0xAA : 01010101 /* 0x55 */
```
:::success
EXP2 = (x & 0x33) << 2
EXP2 = (x & 0x55) << 1
:::
* 以 `x = 0x35` 為例，`8-bit` 二進位為 00110101~2~，預期結果為 10101100~2~
1. `x = (x >> 4) | (x << 4);`
```
00000011 (x >> 4)
| 01010000 (x << 4)
...........
01010011 (4 個 4 個交換)
```
2. `x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);`
```
01010011 (x) 01010011 (x)
& 11001100 (0xCC) & 00110011 (0x33)
........... ...........
01000000 00010011
00001000 ((x & 0xCC) >> 2)
| 01001100 ((x & 0x33) << 2)
...........
01011100 (2 個 2 個交換)
```
3. `x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);`
```
01011100 (x) 01011100 (x)
& 10101010 (0xAA) & 01010101 (0x55)
........... ...........
00001000 01010100
00000100 ((x & 0xAA) >> 1)
| 10101000 ((x & 0x55) << 1)
...........
10101100 (相鄰交換)
```
## 測驗4
延伸〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉，我們嘗試將 [foreach](https://en.wikipedia.org/wiki/Foreach_loop) 巨集 予以擴充，使得支援以下寫法:
```c
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
printf("i is %i\n", i);
}
const char *p;
foreach_ptr(p, "Hello", "world") {
printf("p is %s\n", p);
}
```
預期輸出如下:
```
i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world
```
對應的巨集定義:
```c
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
#define foreach_int(i, ...) \
for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
* 可發現巨集 `__VA_ARGS__` 主要用於宣告任意的變數在 function 的引數中，方便在宣告時不使用太多不同型態的宣告(可變引數的宣告方式)，在 C99 以後的版本新增的功能
> A macro can be declared to accept a variable number of arguments much as a function can. The syntax for defining the macro is similar to that of a function.
> 來源 : [gcc 文件](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)
* 程式的功能在於要能走訪 `foreach_int` 函式中的每一個 `int` 的引數，觀察到函式定義中的 `i` 即代表每一個引數的變數，所以變數 `i` 為範例中的 `(0, -1, 100, 0, -99)`
* 分析 for 迴圈的初始條件 `unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0);`
* 拆部分來看 `((i) =((int[]){__VA_ARGS__})[0])` ，前面的 `int[]` 表示整數的陣列宣告，放入的資料為 `__VA_ARGS__` 也就是說將函式的引數值都存入了陣列當中 `(0, -1, 100, 0, -99)` ，而 `[0]` 表示陣列第一個位置的元素，以範例來說是 `0`
* 再來是給定 `_foreach_i` 變數值為括弧後的 `0` ，就好像是宣告了某個變數的過程時，再宣告一個變數，`_foreach_i` 也不會拿到 `i` 的值
* 看到判斷條件 `_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)` 右半部分的內容，計算整個陣列的記憶體長度，除上 `int` 的長度，也就是計算整個陣列元素的數量，所以就可以觀察到 `_foreach_i` 的變數用於走訪的次數，會根據傳入引數值的個數
* `(i) = ((int[]){__VA_ARGS__, 0})[EXP4]` 所以根據上述的分析，可以得知 `[EXP4]` 為整數陣列中元素的位置，需要走訪每一個元素，為持續遞增的變數，因此 `EXP4` 為 `++_foreach_i` ，所以觀察 `foreach_ptr` 函式功能也相似，所以 `EXP5` 也為 `++_foreach_i`
:::success
EXP4 = ++_foreach_i;
EXP5 = ++_foreach_i;
一開始想法比較簡單，會選擇 `_foreach_i++`，但是經時跑過程式後發現會是錯誤的，原因是在下一次的迴圈時，變數 `i` 比 `_foreach_i++` 早賦值，因此再第一次迴圈的時候會重複 `(i) = ((int[]){__VA_ARGS__, 0})[0]` 的結果，將第一個引數重複走訪兩次
:::
* 測試 `_foreach_i++` 結果:
```
i is 0
i is 0
i is -1
i is 100
i is 0
```
* 利用 `typeof()` 取得引數的變數型態並宣告一個陣列存取
:::info
[參考 gcc 文件解釋](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
>Another way to refer to the type of an expression is with typeof. The syntax of using of this keyword looks like sizeof, but the construct acts semantically like a type name defined with typedef.
:::
* 對於 `const char *` 處理方式透過 `void *` 可以彈性處理傳入的型態，可用於指向不同型態的變數，有暫存的效果，可以再還原
[void * 參考文章](https://medium.com/@racktar7743/c%E8%AA%9E%E8%A8%80-%E6%8C%87%E6%A8%99%E6%95%99%E5%AD%B8-%E4%BA%94-1-void-pointer-c1cb976712a3)
* 範例:
```c
int a = 10;
void *void_ptr = &a;
printf("%d\n", *(int *)void_ptr); /* 結果為 10 */
```
* 使用 assert() 函式，用來檢驗敘述的正確性，在本範例中要檢驗每個資料的是否存在
[assert() 參考文章](https://www.itread01.com/content/1550463517.html)
```c
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
```
* 若 `p` (元素)為 `NULL` 且 `i` 的數量少於陣列元素的個數，所以為了確保函式能順利走訪每一個資料
* 當 `assert` 情況產生，出現以下的訊息:
```shell
main: Assertion `(_foreach_i) >= sizeof(((const void *[]){"Hello", "world"})) / sizeof(((const void *[]){"Hello", "world"})[0])' failed.
```
## 測驗5
針對 [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```c=
#include <limits.h>
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
* 在兩整數二進位的除法中也可以利用長除法的觀念下去執行，如圖
* 先看到 4 ~ 15 行中分別處理被除數與除數的正負號問題，在執行上將兩個未知的整數都先取正數，使用的方式是利用二補數的行為取正，先取反 `~` 再 +1
* 再來看到 17 ~ 19 行中根據長除法的方式，除數要先從被除數最前端的位元開始進行，所以利用迴圈的方式檢查被除數與除數相差的位元位數
>應該不用使用到迴圈進行位元數的判斷，可以使用 `ctz` 類的相關函式進行修改
:::danger
另外，若除數為零的情況下，在 17 ~ 19 行的敘述中會進入無窮迴圈，為本題的缺陷之處
:::
:::success
EXP6 = dvs << shift
:::
* 看到 22 ~ 27 行，首先看到第一層的迴圈，用於判斷被除數在大於除數時能持續進行，所以 `EXP7` 會與這個判斷式有關，對於被除數或是除數的增減有影響
* 再來看到第二層的迴圈，在每一輪的除法中判斷是否可以進行相減的情況(換言之就是商數可以填入 1 的時候)，若不行則退一位( `shift--` )，確保每一輪的減法是大減小的情況
* 利用 `res` 儲存商的結果，觀察到 `(unsigned int) 1 << shift` 就是由第二層迴圈判斷的結果，將商數儲存，利用 `|` 運算子根據 `shift` 移位的結果將該輪可進行一次減法的 `1` 存下
* 也就是說在 `EXP7` 中為每一輪除法的減法敘述，因此 `EXP7` 為
:::success
EXP7 = dvd -= dvs << shift
:::
* 最後看到 28 ~ 29 行的敘述，因為使用 `unsigned int` 儲存結果，因此要避免 overflow 的問題產生，所以把特例的情況將結果固定為 `int` 的最大數值結果
>例外的情況為當除數為 -1 或 1 的情況就會有這種狀況的發生，能讓 `res` 的最左邊第一個位置(對於有號整數來說是正負號的判斷位元)的位元為除數 -1 或 1
## 測驗7
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```c
int ilog32(uint32_t v)
{
int ret = v > 0;
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;
m = (v > 0xFU) << 2;
v >>= m;
ret |= m;
m = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
* 題目解析:計算一個無號整數的二進位元表示中，最高的 1 bit 位元前扣除掉不必要的 0 位元，所需要能表現該數的有效位元數量
* 分為 4 個階段判斷:
* 判斷數字是否為 16 位元以上的數值 (0xFFFFU = 111..11~2~)，大於則將判別的結果 1 儲存 16 的結果，也就是 `1 << 4` = 10000~2~ = 16~10~
* 將 v 檢查完後 16 位元後就可以移除 `v >>= m` ，進行下一階段 8 個位元的檢查
* 以此類推在這 4 個階段的檢查，每一次都是對半檢查
```
前 3 個階段分別的 bitmask為
0xFFFF = 1111111111111111
0xFF = 11111111
0xF = 1111
```
* 所以 `EXP10` 為 `11` 的 bitmask ，轉為 16 進制 = 0x3U
:::success
EXP10 = (v > 0x3U) << 1
:::
* 剩下還有最後一位 bit 的檢查，用要將 ret 結果的最後一個 bit 確認 1 的與否，與前面的檢查方式類似，只不過要濃縮成一句，要達成兩件事情:
1. 檢查最後 1 的 bitmask
2. 將結果填入 1 或 0
* 根據前面的檢查方式可以變成以下兩句:
1. m = (v > 0x1U) << 0;
2. ret += m;
>流程上需要 v >> m; 用於下一階段的檢查，但已是最後一次的判斷所以不用再移位
* 將兩句結合，0x1U = 1~2~ ,`<< 0` 沒有實質作用所以刪除，再將 ret 結果補上 1 或 0 剛好為判斷式的結果，因此
:::success
EXP11 = ret += v > 1
:::
## 測驗9
考慮以下進行記憶體地址對齊 ([alignment](https://en.wikipedia.org/wiki/Data_structure_alignment)) 的巨集:
```c
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
* 題目解析:巨集功能要能把傳入引數進行 `alignment` 的動作，將 1 ~ 16 的數值，都改為 16~10~ 也就是 10000~2~最後的 4 個 bit 要為 0，若傳入 0 則要回傳 0
* 而後 4 個位元的的數值為 1~10~ ~ 15~10~ (0001~2~ ~ 1111~2~)，但這不是我們要的，因此要把它清零，所以要產生 0000 的 0 bitmask，所以可以推測 `~(NNN)` 為相關作法
* `NNN` 產生 0000~2~ 的方法為對 1111~2~(15~10~) 取反，如何找出 15 這個數字，就是由 16 - 1 得來
> 如果要產生 000 的 bitmask 也可以利用 8~10~ -> 1000~2~，再 - 1 為 0111，最後取反得到 1000
:::success
NNN = MAX_ALIGNMENT - 1
:::
* 獲得 0 的 bitmask 後就可以用 `&` 計算子清零，理解後就可以觀察到前面的敘述: `((x) + MAX_ALIGNMENT - MMM)` ， `x + MAX_ALIGNMENT` 將 x 加上不影響的最後 4 個位元的數值(保留第 5 位元 16 的值)再搭配清零的動作就可以得到 16 的數值
* 那假設傳入的是 0 代表要把加入的 16 清除，才能回傳 0，所以 MMM 就是在處理 0 的特例情況，要把 10000~2~ 降一位透過 -1 的方式進行(可得到 01111~2~)
:::success
MMM = 1
:::
* x 傳入 1 ~ 15 範圍的值
```
以 8 bits 表現
x 00000110
MAX_ALIGNMENT 00010000
x + MAX_ALIGNMENT 00010110
^
(保留 alignment 值)
MAX_ALIGNMENT - 1 00001111 取反 `~` -> 11110000
00010011 x + MAX_ALIGNMENT - 1 (-1不影響結果)
& 11110000 ~(MAX_ALIGNMENT - 1)
...........
00010000 <- 16 的結果
```
* x 傳入 0
```
以 8 bits 表現
x 00000000
MAX_ALIGNMENT 00010000
x + MAX_ALIGNMENT 00010000
MAX_ALIGNMENT - 1 00001111 取反 `~` -> 11110000
00001111 x + MAX_ALIGNMENT - 1 (-1 將最高位降一位)
& 11110000 ~(MAX_ALIGNMENT - 1)
...........
00000000 <- 0 的結果
```
## 測驗10
考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:
```c
#define DIVIDE_ROUND_CLOSEST(x, divisor) \
({ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
(((__x) > 0) == ((__d) > 0))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
注意: 當除數 (即 `divisor`) 為負值時，行為沒有定義。
參考執行結果:
* `DIVIDE_ROUND_CLOSEST(7, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(6, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(5, 3) = 2`
看到前三個敘述的判斷條件，分別為:
* `((typeof(x)) -1) > 0`
* `((typeof(divisor)) -1) > 0`
* `(((__x) > 0) == ((__d) > 0))`
前兩項為:將傳入 `x` 、 `divisor` 的型態轉型到 `-1` 上，分兩種情況為有號數與無號數，這個判斷式就是要確保在計算的時候皆為無號數，所以透過 `-1` 的強制轉型判斷
```c
unsigned int a;
int b;
printf("result : %d\n", ((typeof(a)) -1) > 0);
printf("result : %d\n", ((typeof(b)) -1) > 0);
```
結果為:
```
result : 1
result : 0
```
而第三項的判斷式，也是確保傳入的兩數皆為正數的情況下進行計算
* 再來看到除法的取最接近整數的運算方式， `/` 在運行的方式為無條件捨去小數的形式，所以要透過對結果有四捨五入的結果產生，所以要對 `/` 結果 + - 除數的一半數值，也就是說要將***被除數捨棄掉的數值進行處理***
* 若是捨棄掉除數的一半以上則需要加上除數的 0.5 進位
* 若是捨棄掉除數的一半以下則需要扣除除數的 0.5
:::success
RRR = (__x) + ((__d) >> 1)
SSS = (__x) - ((__d) >> 1)
:::
## 測驗11
考慮以下計算整數開平方根的實作:
```c
static inline unsigned long fls(unsigned long word)
{
int num = 64 - 1;
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
if (!(word & (~0ul << (64 - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (64 - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (64 - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (64 - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (64 - 1))))
num -= 1;
return num;
}
unsigned long i_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (fls(x) & ~1UL);
while (m) {
b = y + m;
XXX;
if (x >= b) {
YYY;
y += m;
}
ZZZ;
}
return y;
}
```
* `i_sqrt` 函式的作用等同於 `floor(sqrt(x))`
首先看到 `fls()` (find the last bit set)函式的作用，目的是要找到一數在二進位中由最低位至到最高位的 `1` 的位置，檢查的方式為產生 1 的 bitmask 在不同位置檢查，檢查的順序為 32 位元、 48 位元、 56 位元、 60 位元、 62 位元、 63 位元，遞增的順序為 +16 +8 +4 +2 +1，以 4~10~ (100~2~) 為例
```
第一層:
num = 63
1111...1100...000 (~0ul << 32) 前 32 個位元為 1
& 100
....................
00000000000000000 num = 63 - 32 = 31
第二層: (看前 32 個位元)
num = 31
1111...11000...000 (~0ul << 48)
& 100 ( 4 << 32)
....................
0000...0000...000 num = 31 - 16 = 15
第三層: (看前 16 個位元)
num = 15
1111111100000000 (~0ul << 56)
& 100 ( 4 << 16)
..................
0000000000000000 num = 15 - 8 = 7
第四層: (看前 16 個位元)
num = 7
1111000000000000 (~0ul << 60)
& 10000000000 ( 4 << 8)
..................
0000000000000000 num = 7 - 4 = 3
第五層: (看前 16 個位元)
num = 3
1100000000000000 (~0ul << 62)
& 100000000000000 ( 4 << 4)
..................
0100000000000000 結果不為 0, num = 3
第六層: (看前 16 個位元)
num = 3
1000000000000000 (~0ul << 62)
& 100000000000000
..................
0000000000000000 num = 3 - 1 = 2
4 = 0100
最高位 1 為第 2 個位元位置 (第一個位置是第 0 位)
```
* `m` 透過 `fls()` ，找出數字的最高位元位置，目的為了找出小於該數值最大二進位中完全平方數，(例如: 1, 4, 16, 64)，用 `& ~1UL` 將 `fls()` 的最低位數去除
* 參考 [平方根的算法1](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2))、[平方根的算法2](https://hackmd.io/@sysprog/sqrt?type=view)
首先一個數可假設$$N^2 = (a_n+...a_0)^2$$
而在二進位中可將每一項的 $a$ 表示為 $a_m = 2^m$ 或是 $a_n = 0$ 可由二進位的數值進行逼近，對 $2^m$ 進行迭代，假設為:$$P_m = a_n + a_{n-1}+...+a_m$$
>m+1為迭代的下一位
決定$a_m = 2^m$ 或是 $a_n = 0$，假設$$P_m=P_{m+1} + 2^m \ \ -(1)$$
若 $N^2 \geq P_m^2$，則表示 $a_m = 2^m$ (表示$a_m$ 存在於平方數中)，若無則 $a_m = 0$ 根據上式則為 $P_m=P_{m+1}$，而為防止迭代停止的狀況，則為更新目標數字的數值為$$X_m = N^2 - P_m^2$$，持續更新數值為:$$X_m = X_{m+1} - Y_m$$，其中 $$Y_m = P_m^2 - P_{m+1}^2 = 2P_{m+1}a_m+a_m^2$$
>(由式 1 平方結果而來)
分別表示:$$c_m = 2P_{m+1}a_m, \ \ d_m = a_m^2$$
又因$a_m = 2^m$$$c_m = P_{m+1}2^{m+1}, \ \ d_m = (2^m)^2$$
可得在 `m-1` 時:$$c_{m-1} = P_m2^m=(P_{m+1}+a_m)2^m=P_{m+1}2^m+a_m2^m$$
所以當 $a_m=2^m, c_m/2 + d_m$ ,而 $a_m = 0, c_m/2$，$d_{m-1} =d_m/4$
根據上述的計算方式就可以發現對應題目中的變數
* $c_m = y$
* $d_m = m$
對應程式為:
* 每次的迭代都需要 $c_m/2$
* $d_{m-1} =d_m/4$
:::success
XXX = y >>= 1
ZZZ = m >>= 2
:::
所以當平方數在 `x` 存在則需要扣除，因此:
:::success
YYY = x -= b
:::
Sign in with Wallet
Connect another wallet