---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `sternacht` >
> [作業要求](https://hackmd.io/@sysprog/BJJMuNRlq)
### 測驗 1
#### 答案
LEFT = `63 - h`
RIGHT = `l`
#### 延伸 - 解釋上述程式碼運作原理
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
題目要求實做一個巨集 GENMASK ，回傳一個長度為 64 且從 h 到 l 之間的 bits 為 1 ，其餘為 0 的值。從題目給的程式碼不難看出這是一個用 ＆ 達成的實做，目標就是要湊出 `l ~ 63 為 1` 以及
`0 ~ h 為 1` 這兩個值，知道這個概念之後 LEFT 的答案就很明顯了，藉由無號數的右移是補 0 的原則，右移 `63 - h` 就會得到 `0 ~ h 為 1`。
接著 `(~0UL) >> (l)` 會得到前 l bits 為 0 的值，需要做左移 l bits 得到 `l ~ 63 為 1` 的值，RIGHT 答案為 `l`
#### 延伸 - 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
在 [ linux/tools/power/x86/intel-speed-select/isst.h ](https://github.com/torvalds/linux/blob/df04fbe8680bfe07f3d7487eccff9f768bb02533/tools/power/x86/intel-speed-select/isst.h) 可以找到 GENMASK 的實作。基本上概念與測驗的題目一樣，不同的是題目在 `((~0UL) >> (l) << (l))` 的作法比較多餘，實作上就只需要 `((~0UL) << (l))` ，此外測驗中是只以 64-bits 的架構為考量，而實作上則額外考慮是否會運行在 32-bits 的架構上（如 LLP64），若是運行在 32-bits 的架構上，則 long 的長度僅有 4 byte， 回傳的 GENMASK 的長度也該有所改變，另外在 linux kernel 中也提供了 long long 長度的實做。
```c
#define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (sizeof(long) * 8 - 1 - (h))))
#define GENMASK_ULL(h, l) \
(((~0ULL) << (l)) & (~0ULL >> (sizeof(long long) * 8 - 1 - (h))))
```
#### 延伸 - 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例
- [drivers/net/wireless/mediatek/mt76/mt7921/mac.h](https://github.com/torvalds/linux/blob/fc02cb2b37fe2cbf1d3334b9f0f0eab9431766c4/drivers/net/wireless/mediatek/mt76/mt7921/mac.h)
```c
#define MT_RXD0_LENGTH GENMASK(15, 0)
#define MT_RXD0_PKT_FLAG GENMASK(19, 16)
#define MT_RXD0_PKT_TYPE GENMASK(31, 27)
```
在 linux kernel 中搜尋 GENMASK，會看到很多類似的定義，尤其是在通訊之類需要資料傳輸的檔案中，推測是資料在壓縮之後，解壓縮時會用到這些由 GENMASK 實作的 mask
- [include/soc/mscc/ocelot_dev.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/include/soc/mscc/ocelot_dev.h)
```c
#define DEV_CLOCK_CFG_LINK_SPEED(x) ((x) & GENMASK(1, 0))
```
這個函式呼叫的時候會傳入另一個定義過的常數，用該常數的最後兩位來區分接下來的動作。
### 測驗 2
#### 答案
EXP1 = `(struct foo*)(v & ~3)`
#### 延伸 - 解釋上述程式碼運作原理
```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};
}
```
題目要求根據傳入的地址 v ，以向下對齊的方式建立結構 fd，使結構中的第一個成員之地址符合
4 bits 的 alignment。而 align down 的定義是往記憶體位址低的地方作對齊，以 2 進位來說就是要使後 2 位為 00，因此答案 `(struct foo*)(v & ~3)` 就是利用 bitwise 的操作來保留前面的位元，使後 2 位為 00 ，並指定型態為 foo 的指標。
### 測驗 3
#### 答案
EXP2 = `(x & 0x33) << 2`
EXP3 = `(x & 0x55) << 1`
#### 延伸 - 解釋上述程式碼運作原理
```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;
}
```
這題的概念就是將數字拆分成一半，然後將前後的位置對調，一開始先把 8 bits 的前後 4 bits 對調，接著再把 4 bits 中的前後 2 bits 對調，以此類推再將 2 bits 前後對調。為了達到這個目標， EXP2 就需要取得 4 bits 中的後 2 bits，也就是 `x & 0x33` ，並將其往前放 2 bits，答案就是 `(x & 0x33) << 2` ，以此類推 EXP3 是 `(x & 0x55) << 1`。
### 測驗 4
#### 答案
EXP4 = `++_foreach_i`
EXP5 = `++_foreach_i`
#### 延伸 - 解釋上述程式碼運作原理
```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__})))
```
題目中定義一個巨集 foreach ，能夠走訪傳入的參數。先看 foreach_int ，變數 `_foreach_i` 用來判斷目前所在的地方是否超過傳入的個數範圍，一開始設為 0 ，而變數 `i` 則用來表示傳入的各個參數，在進到下一次迴圈的時候要改變 `i` 的內容並使 `_foreach_i` + 1，而這就是 EXP4 這一行所做的事。要使 `_foreach_i` + 1 有前置 ++ 與後置 ++ 兩種，因為 `i` 一開始已經表示第一個傳入參數了，因此這裡要使用 `++_foreach_i` 使其先 + 1 再賦值給 `i`，才會是正確的內容。
相同的道理， foreach_ptr 傳入的參數是字串，能取得的就是字元的指標的開頭，但是這些指標的開頭在傳入時會整合成一個指標陣列，因此 `_foreach_i` 的任務並沒有改變， EXP5 的答案也是 `++_foreach_i`，不同的是這裡的結束條件改成只用 `i` 是否為 0 來判斷，前一個巨集之所以不能這麼做的原因是必須考慮傳入值為 0 的情況，但在指標中若是指向 0 則通常表示結束。
#### 延伸 - 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
- [drivers/scsi/aic7xxx/queue.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/drivers/scsi/aic7xxx/queue.h)
```c
#define SLIST_FOREACH(var, head, field) \
for ((var) = SLIST_FIRST((head)); \
(var); \
(var) = SLIST_NEXT((var), field))
```
除了前一兩周用過很多的 list_for_each 之類的 double linked-list 實作之外，linux 也有為 single linked-list 所寫的一套巨集， var 與 head 都是 linked-list 的指標，因為是單向的，因此當 var 的 next 指向 NULL 的時候就表示已經到底了。
### 測驗 5
#### 答案
EXP6 = `dvs << shift`
EXP7 = `dvd -= dvs << shift`
#### 延伸 - 解釋上述程式碼運作原理，指出可改進之處，並予以實作
```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;
}
```
題目要求傳入兩個數值，分別為被除數與除數，要回傳商數，而這一段程式碼實作運用的原理就是
dvd = dvs * res + remainder ，其中 remainder < dvs ，且這四個數都用整數表達。而 res 用 2 進位表達的時候，可以想成是多個不同的 2 的冪去乘以 dvs ，在程式裡就會是用左移的方式去呈現。
知道上述概念之後，接著看程式碼，首先先將 dvd 與 dvs 轉成正整數，並保留負號在最後使用。接著在 EXP6 的迴圈中要找到 res 在 2 的冪之中的上界， res 不會超過該 2 的冪之值，而乘以 2 的冪可視作左移，因此 EXP6 =`dvs << shift`，至此我們確定 res 的答案小於等於 `1 << shift` 。
接下來對位置小於 shift 的 bits，我們以遞減的方式逐一去做比較，如果 dvs 左移 shift 的結果大於 dvd ，則表示該位元在 res 中為 0 ，否則 res * dvs 會大於 dvd。反之，如果小於等於 dvd ，則我們可以確定該位置之位元在 res 中為 1 ，將其記錄到 res 中，並使 dvd 減去該結果，重複直到 dvd 小於 dvs ，則剩下的 dvd 就是餘數。
程式的最後有一個 if 判斷式，推測是因為傳入值的型態是有號數，會出現負數的最大值除以 -1 這種特例，在這種情況下，商是 INT_MAX + 1，但這是用有號數無法表示的，因此回傳 INT_MAX 代替答案。
這段程式我認為在計算 shift 初值的地方可以做一些改善，原本的方式用逐步增加 shift 的方式去做比較，效率較差，當被除數遠大於除數時，需要做很多次迭代，以下是我的方式
```c
int shift = __builtin_clz(dvs) - __builtin_clz(dvd);
```
透過直接比較兩個數的 clz ，我們可以確認 dvs 至少需要左移幾位才會使 last bit 對齊 dvd，也就能找到 2 的冪的上界。
### 測驗 7
#### 答案
EXP10 = `(v > 0x3) << 1`
EXP11 = `ret += v > 1`
#### 延伸 - 解釋上述程式碼運作原理
```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;
}
```
這段程式碼的目的是去計算 v 最少需要幾位元來存取，也就是最高位的位元在哪裡，若有支援硬體相關指令的時候可以使用 `__builtin_clz` 來得到答案，但這裡先不考慮。這題的概念基本上就是二元樹，先去比較 `v` 的最高位在前半邊還是後半邊，如果是在前半邊，就再將前半邊分成兩半，然後重複相同的動作， `m` 用來記錄每一輪的結果是在前半或後半，如果在前半的話就需要將比較的範圍往左移(程式碼中是把 v 往右移)，並把結果加到 `ret`。需要注意的是，雖然這段程式碼基本上就是不斷重複並縮小範圍，但在最後面 EXP11 的地方是三個指令和在一起，分別是 `m = (v > 0x1) << 0` 、 `ret |= m` 、 `v >>= m`，因為 v 不會再被使用到、第三個指令可以省略，合併 1, 2 可以得到 `ret |= (v > 1)` ，而這樣得到的值是最高位之後的位數，因此還要再加上一，而函式的第一行就預先做了判斷是否要補上這個 1 ，綜合這點，EXP11 應該寫成 `ret += v > 1` 。
代數字下去看例如:
```c
v = 0x00800000 // (0000 0000 1000 0000 ...)
ret = 1 // (v > 0)
m = 16 // (v > 0xFFFF)
v = 0x0080 // (v >>= 16)
ret = 10001 // (ret |= m)
m = 0 // (v < 0xFF)
v = 0x0080 // (v >>= 0)
...
```
#### 延伸 - 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
先找找 de Bruijn Sequences 的概念 : 由 0, 1 組成的二進位數值，長度為 $2^n$，則我們隨意取 n 個 bits 來看都不會重複，就構成一種 de Bruijn Sequences。
論文中將這種計算方式分成三個步驟，第一步首先要簡化問題，從在很多個 0 與 1 的數值，簡化成只有最高位為 1 的數值，或是像[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics#Count-Leading-Zero)中的範例，使最高位的 1 以後都是 1 的數值，其目的就是要讓這個數值變得獨一無二，論文中使用 bitwise 的技巧示範如何找到 first set ，然而這題我們希望找的是最高位元的 1 ，因此我們可以以第二種方式實作，如剛剛提到的範例
```c
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
...
}
```
透過以上的 bitwise 操作，value 將變成一個根據最高位元位置，而有固定值的數。
再來第二步要將剛才得到的數作 hash ，建立一個 hash table，而前面之所以要簡化，就是為了縮減 hash table 的大小，如此一來長度 $2^n$ 的數，hash 值的範圍就是 $2^n$ ，且每一個 hash key 都只會對應一個值，也就是沒有 collisions 發生。
最後就是找到 de Bruijn Sequences，這個值並不是只有唯一解，可能存在多組解，在討論[Fast computing of log2 for 64-bit integers](https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers)中，即對 64 bits 的 de Bruijn Sequences 提供兩種解答。而有了這組數字之後，再透過乘法及位元位移，就能得到 hash key，進而得到答案。例如
```c
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
```
運用這種演算法，不須依賴 clz/ctz 等指令，並且計算的過程也實現了 branchless。
### 測驗 8
#### 答案
EXP12 = `p = &(*p)->left`
EXP13 = `p = &(*p)->right`
EXP14 = `&(*r)->left`
#### 延伸 - 解釋上述程式碼運作原理
```c
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
本題題目是一個二元搜尋數的實作，上述程式碼是要將一個存有值為 d 的節點從二元樹之中移除掉，於是第一步就是要找的該節點。二元樹的搜尋不外乎就是比較當前節點的值然後看要往左或往右繼續搜尋，直到找到為止，且根據題目先前的描述，左子樹存放的值會比當前的值還小，右子樹則較大，依據這個規則，我們可以知道 EXP12 及 EXP13 分別是移動指標往左及往右， p 是指標的指標，因此在賦值的時候要 assign '指向下一個節點的指標 的指標'，於是乎形式就是 `p = &(*p)->left`
若沒找到節點，就直接結束函式，而找到節點之後，接下來的動作就是要將節點移除，移除則再跟三種不同的情況有不同動作，沒有左子樹、沒有右子樹、左右子樹皆存在。在第三種情況中，本題的作法是拿整個樹中，比自己大的節點裡最小的一個節點來補，而這個節點就會在右子樹(比自己大)的最左邊的節點(最小)。所以程式中先令 r 指向節點的右子樹，然後就一路往左走到底找最小的節點，並用來取代掉要刪除的節點。
### 測驗 9
#### 答案
MMM = `1`
NNN = `MAX_ALIGNMENT - 1`
#### 延伸 - 解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
ROUND UP 的概念相似於無條件進位，假設有一個整數除以 10 之後有餘數 0 ~ 9，並要無條件進位，餘數會進位的區間就是 1 ~ 9 都會進位，只有整除不進位，我們希望在捨棄小數的情況下，讓除出來的結果就會是進位的結果，因此要加上一個 offset 為 9，才能讓原本餘 1 的數也進位。
相同的概念套回來程式上，round up alignment 所需的 offset 就是 `MAX_ALIGNMENT - 1` = 15，然後將後四個位元(相當於除以 16 後的小數部分)捨棄，也就是令其為 0。而這部份透過 botwise 操作達成，除了後四 bits 為 0 ，齊餘為 1 的 mask，可以寫作 `~(0xF)`，然而題目要求必須用到 MAX_ALIGNMENT ，因此就寫作 `~(MAX_ALIGNMENT - 1)`
```c
#define MAX_ALIGNMENT 16
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
相對之下ROUND DOWN 的概念也可以對應到無條件捨去，也就是除了整數以外，小數部位全部捨棄，不需要加上 offset ，因此套到程式上就寫成
```c
#define MAX_ALIGNMENT 16
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(x & ~(NNN))
```
#### 延伸 - 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
在 linux kernel 中可以找到 [linux/align.h](https://github.com/torvalds/linux/blob/a48b0872e69428d3d02994dcfad3519f01def7fa/include/linux/align.h) 提供了 ALIGN(對應 align_up) 及 ALIGN_DOWN 兩個巨集，以 ALIGN 來看，巨集的定義如下
```c
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
```
`__ALIGN_KERNEL` 則可以在[ linux/const.h ](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/tools/include/uapi/linux/const.h)中找到定義
```c
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
將巨集整理過後會得到 ALIGN 實作為 `(((x) + ((typeof(x))(a) - 1)) & ~((typeof(x))(a) - 1))`，在簡化一些可以寫成 `((x) + (a) - 1) & ~((a) - 1)` ，跟題目中提到的就很相似了，唯在巨集中， a 是可以根據需求做調整，條件是 a 必須是 2 的冪。同樣經過整理可以得到 ALIGN_DOWN 為
`(((x) - (a) - 1)) + (a) - 1) & ~((a) - 1)`，也就等同於 `(x) & ~((a) - 1)`
### 測驗 10
#### 答案
RRR = `(__x) + ((__d) >> 1)`
SSS = `(__x) - ((__d) >> 1)`
#### 延伸 - 解釋上述程式碼運作原理
```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)); \
})
```
這題的概念與上一題有些相似，同樣是在該如何進位的問題，以這題來說我們希望除法後得到較靠近的整數，有點像是四捨五入的想法，於是接著要思考 offset 該是多少才能達到這樣的效果。假設除數為 d ，餘數範圍是 0 ~ (d - 1)，餘數靠近 d 的一半會進位，靠近 0 的則捨去， offset 就是 d / 2 ，換成 bitwise 操作則是 `d >> 1`。因題目以明確表示 `__d` 是負數時為 undefined behavior ，不考慮 `__d` 為負的狀況，因此在 `__x` > 0 的範圍， offset 應該為正，如 RRR 的程式碼所寫，反之在`__x` < 0 的範圍， offset 應該為負，如 SSS 的程式碼。
### 測驗 11
#### 答案
XXX = `y >> 1`
YYY = `x -= b`
ZZZ = `m >> 2`
#### 延伸 - 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
```c
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` 函式的作用相當於 $\lfloor \sqrt(x)\rfloor$ ，直覺的辦法就是從小的數開始，一路用平方的方式去看何時會超過原本的值，就能得到答案，但這樣做相當浪費時間。於是這題採用的想法是，我只要確保一個數，加上某一個 2 的冪的平方後不會大於原本的值，我就可以確定這一個 2 的冪是 $\sqrt(x)$ 的一部分，當然條件是必須由上往下找。
首先我們先找到 `x` 的最高位元 `m` ，$\sqrt(m)$ 必然會是 $\sqrt(x)$ 的一部分， `y` 紀錄目前符合條件的所有 2 的冪總和， `m` 與 `y` 有種快慢指標的味道，在每一輪迴圈中， `y` 會右移 1bit ，`m` 則右移 2bits ，直到最後當 `m` 為 0 的時候， `y` 中的每個 bits 恰好右移一半的距離，也就是開平方的意思。 `b` 則是用來判斷加上 `m` 之後的答案會不會大於 `x`，如果不會就可以放心加上去，並在加上去之後把已有的值從 `x` 中扣除。
`fls` 是用來找最高位元的 1 出現在哪個位置，題目中使用的是類似測驗 7 的方式，以二元搜尋來逐步找出答案
```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;
}
```
因此相同的，這一段程式碼我們可以用 clz 來改寫，如下
```c
m = 1UL << (63 - clz(x));
```
#### 延伸 - 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景
在 [linux/lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/lib/math/int_sqrt.c) 中有一模一樣的實作 `int_sqrt` ，而一個應用的例子是在同目錄底下的 [prime_number.c](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/lib/math/prime_numbers.c) 裡，用來找質數。一個數若不是質數，我們可以寫成兩個大於 1 的數相乘，而這兩數中小的一方，最大值就是 $\lfloor \sqrt(x)\rfloor$ ，因此透過 `int_sqrt` 函式，可以大幅縮短我們尋找的範圍。
```c
static bool slow_is_prime_number(unsigned long x)
{
unsigned long y = int_sqrt(x);
while (y > 1) {
if ((x % y) == 0)
break;
y--;
}
return y == 1;
}
```
Sign in with Wallet
Connect another wallet