---
tags: linux2022
---

# 2022q1 Homework3 (quiz3)
contributed by < `StevenChou499` >
* [作業需求](https://hackmd.io/@sysprog/BJJMuNRlq)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-7)

---

## 測驗 `1`
> 在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:
> * `GENMASK(6, 4)` 產生 01110000
> * `GENMASK(39, 21)` 產生0x000000FFFFE00000 (64位元)
> 已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
> ```c
> #define GENMASK(h, l) \
> (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
> ```

### 思考與想法
因為是要產一個 `bitmask` ，所以其中的 `&` 運算應該是要利用分別只有單邊的 `1` 做 `&` 運算後只剩下中間同時為 `1` 部份。

                0000001111111111
             &  0000001111000000
           -------------------------
                0000001111000000
                      ^  ^
                      同時都擁有1的部份

而 `&` 的左側為 `(~0UL) >> (LEFT)` ，若變數為 `64` 位元，則需要往右側 shift `(63 - h)` 次，因為變數的最右側位元為第 `0` 個位元，因此 `LEFT` 為 `63 - h` ，而 `&` 的右側為 `(~0UL) >> (l) << (RIGHT)` ，便是將 `64` 個 `1` 向右 `shift` 再向左 `shift` ，以便創造出只有中間有 `1` ，兩側皆為 `0` 的情形。因此 `RIGHT` 為 `l` 。

:::success
LEFT : 63 - h
RIGHT : 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 結構體，並確保第一個成員的地址得以依據〈[所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。其中 struct foo; 運用〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。

### 思考與想法
由題目可以知道，輸入一地址之後，回傳之 `struct foo *` 指標必須為 4 的倍數，因此必須將 4 以下之位數都清除，所以 `EXP1` 之值為 `(struct foo *)(v & ~3)`。

:::success
EXP1 : (struct foo *)(v & ~3)
:::

## 測驗 `3`
> 考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. 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;
> }
> ```

### 思考與想法
由未完成的程式碼可以知道其實該程式碼是想要透過三次的四四互換、兩兩互換和一一互換達成反轉的結果。
* 函式中的第一行：

    x = (x >> 4) | (x << 4);

為左邊四位與右邊四位做互換

* 函式中的第二行：

    x = ((x & 0xCC) >> 2) | (EXP2);

由 `0xCC` 轉成 `binary` 為 `11001100` 可以知道其作用是將為 `0` 的部份透過 `&` 的方式轉為 `0` ，做 `>> 2` 則代表原本與 `11` `&` 的位置移動到與 `00` `&` 的位置。所以其實式為了將 `11` 與 `00` 的位置互換。因此 `EXP2` 為剛好反過來，需要 `x` 與 `00110011` 做 `&` 再 `<< 2` ，這樣剛好可以達成兩兩互換的結果。所以 `EXP2` 的值為 `(x & 0x33) << 2` 。

* 函式中的第三行：

    x = ((x & 0xAA) >> 1) | (EXP3);

由 `0xAA` 轉成 `binary` 為 `10101010` 可以知道其作用是將為 `0` 的部份透過 `&` 的方式轉為 `0` ，做 `>> 1` 則代表原本與 `1` `&` 的位置移動到與 `0` `&` 的位置。所以其實式為了將 `1` 與 `0` 的位置互換。因此 `EXP3` 為剛好反過來，需要 `x` 與 `01010101` 做 `&` 再 `<< 1` ，這樣剛好可以達成兩兩互換的結果。所以 `EXP3` 的值為 `(x & 0x55) << 1` 。

以 `1~8` 舉例：

以下為 `1~8` 的牌子

digraph INIT {
rankdir = "LR"
    poker_1to8[label="
    {1|2|3|4|5|6|7|8}", shape=record, fixedsize=true,width=4]
}

先將左右各四份交換

    x = (x >> 4) | (x << 4);

digraph INIT {
rankdir = "LR"
    poker_56781234[label="
    {5|6|7|8|1|2|3|4}", shape=record, fixedsize=true,width=4]
    equal[label = "||\n",shape = none]
    poker_5678[label="
    {5|6|7|8||||}", shape=record, fixedsize=true,width=4]
    omit[label = "+\n",shape = none]
    poker_1234[label="
    {||||1|2|3|4}", shape=record, fixedsize=true,width=4]
}

再兩兩交換

    x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);

digraph INIT {
rankdir = "LR"
    poker_56781234[label="
    {7|8|5|6|3|4|1|2}", shape=record, fixedsize=true,width=4]
    equal[label = "||\n",shape = none]
    poker_5678[label="
    {7|8|||3|4||}", shape=record, fixedsize=true,width=4]
    omit[label = "+\n",shape = none]
    poker_1234[label="
    {||5|6|||1|2}", shape=record, fixedsize=true,width=4]
}

最後再各自交換

    x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);

digraph INIT {
rankdir = "LR"
    poker_56781234[label="
    {8|7|6|5|4|3|2|1}", shape=record, fixedsize=true,width=4]
    equal[label = "||\n",shape = none]
    poker_5678[label="
    {8||6||4||2|}", shape=record, fixedsize=true,width=4]
    omit[label = "+\n",shape = none]
    poker_1234[label="
    {|7||5||3||1}", shape=record, fixedsize=true,width=4]
}

**完成！**

:::success
EXP2 : (x & 0x33) << 2
EXP3 : (x & 0x55) << 1
:::

## 測驗 `4`
> 延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:
> ```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__})))
> ```

### 思考與想法
由上述的程式碼可以看出該巨集是循序訪問陣列中的元素，其中 `_foreach_i` 為 `0` ，而在宣告 `_foreach_i` 的同時也宣告 `i` 為一代表 `int` 或是 `const char` 的陣列。在聚集中可以看到其實內容為一 `for` 迴圈，而 `for` 迴圈的最後一個敘述式為若第二個敘述式為真才要執行的結果，又因為 `_foreach_i` 為代表 `i` 陣列的元素位置，因此 `EXP4` 與 `EXP5` 的值皆為 `++_foreach_i` 。

:::success
EXP4 : ++_foreach_i
EXP5 : ++_foreach_i
:::

## 測驗 `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;
> }
> ```

### 思考與想法
看到程式碼時可以想到這個程式是想要利用 `shift` 一一從二進位的高位數進行比較，若大於 `dvd` 則 `shift` 減 `1` ，直到 `dvs << shift` 小於 `dvd` 的第一次則代表 `res` 在這位式可以紀錄 `1` 的，因此使用 `res |= 1 << shift` 的方式將 `1` 的位置記錄下來，而此時應該要將 `dvd` 減去 `dvs * (1 << shift)` ，這樣才可以計算剩下的值對於 `dvs` 的倍數為何，一直進行下去直到 `shift` 的值為 `1` 為止。一開始我將 `EXP6` 的值輸入 `dvs << shift` ，而 `EXP7`的值輸入 `dvd -=res * dvs` ，發現一直會有錯誤，結果發現我的想法是對的，但是直接將 `dvd` 的值減去 `res * dvs` 會導致多次減去高位數的 `1` ，導致做 `while` 判斷式時會發生錯誤，從而進入一無限迴圈。因此 `EXP6` 的值為 `dvs << shift` ，而 `EXP7`的值應為 `dvd -= (1 << shift) * dvs` 。

簡單來說，程式碼可以算做是二進制的長除法（以 `133` 除以 `7` 為例）：

                 res = 16 +  2 +  1 = 19
                     /-------------------
                   7/ 133
                      112
                      -------------------
                       21 ->21
                            14
                      -------------------
                             7 ->7
                                 7
                      -------------------
                                 0

:::success
EXP6 : dvs << shift
EXP7 : dvd -= (1 << shift) * dvs
:::

## 測驗 `6`
> 針對 [LeetCode 149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
> ```c
> #include <stdbool.h>
> #include "list.h"
>
> struct Point {
> int x, y;
> };
>
> struct point_node {
> int p1, p2;
> struct list_head link;
> };
>
> static bool can_insert(struct list_head *head, int p1, int p2)
> {
> struct point_node *pn;
> list_for_each_entry (pn, head, link)
> return EXP8;
> return true;
> }
>
> static int gcd(int x, int y)
> {
> while (y) {
> int tmp = y;
> y = x % y;
> x = tmp;
> }
> return x;
> }
>
> static int maxPoints(struct Point *points, int pointsSize)
> {
> if (pointsSize <= 2)
> return pointsSize;
>
> int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
> int *dup_cnts = malloc(pointsSize * sizeof(int));
> int *hori_cnts = malloc(pointsSize * sizeof(int));
> int *vert_cnts = malloc(pointsSize * sizeof(int));
> int *slope_cnts = malloc(slope_size * sizeof(int));
> memset(hori_cnts, 0, pointsSize * sizeof(int));
> memset(vert_cnts, 0, pointsSize * sizeof(int));
> memset(slope_cnts, 0, slope_size * sizeof(int));
>
> for (i = 0; i < pointsSize; i++)
> dup_cnts[i] = 1;
>
> struct list_head *heads = malloc(slope_size * sizeof(*heads));
> for (i = 0; i < slope_size; i++)
> INIT_LIST_HEAD(&heads[i]);
>
> for (i = 0; i < pointsSize; i++) {
> for (j = i + 1; j < pointsSize; j++) {
> if (points[i].x == points[j].x)
> hori_cnts[i]++, hori_cnts[j]++;
>
> if (points[i].y == points[j].y)
> vert_cnts[i]++, vert_cnts[j]++;
>
> if (points[i].x == points[j].x && points[i].y == points[j].y)
> dup_cnts[i]++, dup_cnts[j]++;
>
> if (points[i].x != points[j].x && points[i].y != points[j].y) {
> int dx = points[j].x - points[i].x;
> int dy = points[j].y - points[i].y;
> int tmp = gcd(dx, dy);
> dx /= tmp;
> dy /= tmp;
> int hash = dx * dy - 1333 * (dx + dy);
> if (hash < 0)
> hash = -hash;
> hash %= slope_size;
> if (can_insert(&heads[hash], i, j)) {
> struct point_node *pn = malloc(sizeof(*pn));
> pn->p1 = i;
> pn->p2 = j;
> EXP9;
> }
> }
> }
> }
>
> for (i = 0; i < slope_size; i++) {
> int index = -1;
> struct point_node *pn;
> list_for_each_entry (pn, &heads[i], link) {
> index = pn->p1;
> slope_cnts[i]++;
> }
> if (index >= 0)
> slope_cnts[i] += dup_cnts[index];
> }
>
> int max_num = 0;
> for (i = 0; i < pointsSize; i++) {
> if (hori_cnts[i] + 1 > max_num)
> max_num = hori_cnts[i] + 1;
> if (vert_cnts[i] + 1 > max_num)
> max_num = vert_cnts[i] + 1;
> }
> for (i = 0; i < slope_size; i++) {
> if (slope_cnts[i] > max_num)
> max_num = slope_cnts[i];
> }
>
> return max_num;
> }
> ```

## 測驗 `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;
> }
> ```

### 思考與想法
由原本的程式瑪可以看出，函式的第一行為判斷數字 `v` 是否為不小於零。皆著判斷 `v` 是否大於 `0xFFFFU` ，若大於 `0xFFFFU` 則為 `1` ，並且向右位移 4 次變成 16 ，而 `v >>= m` 則是向右位移 16 次，最後 `ret |= m` 便是加上 `m` 的過程，以此類推，最後便可以算出需要的位數。

由於傳入的數值 `v` 剛好為 `uint32_t` ，因此在計算之後透過 `|` 的動作若為 32 位皆為 1 則剛好可以，因此我們可以知道 `EXP10` 為 `(v > 0x3U) << 1` ，且 `EXP11` 因為已經剩下最後一位，不需要經過位移，因此其值為 `ret |= v > 0x1U` 。

:::success
EXP10 : (v > 0x3U) << 1
EXP11 : ret |= v > 0x1U
:::

## 測驗 `8`
> 考慮以下 C++ 二元搜尋樹的程式:
> ```c
> typedef struct tnode *tree;
> struct tnode {
> int data;
> tnode *left;
> tnode *right;
> tnode(int d)
> {
> data = d;
> left = right = 0;
> }
> };
>
> void remove_data(tree &t, int d)
> {
> tnode *p = t;
> tnode *q;
> while (p != 0 && p->data != d) {
> if (d < p->data) {
> q = p;
> p = p->left;
> } else {
> q = p;
> p = p->right;
> }
> }
> if (p != 0) {
> if (p->left == 0)
> if (p == t)
> t = p->right;
> else if (p == q->left)
> q->left = p->right;
> else
> q->right = p->right;
> else if (p->right == 0)
> if (p == t)
> t = p->left;
> else if (p == q->left)
> q->left = p->left;
> else
> q->right = p->left;
> else {
> tnode *r = p->right;
> while (r->left) {
> q = r;
> r = r->left;
> }
> p->data = r->data;
> if (r == p->right)
> p->right = r->right;
> else
> q->left = r->right;
> p = r;
> }
> delete p;
> }
> }
> ```
> 函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
> ```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;
> }
> ```

## 測驗 `9`
> 考慮以下進行記憶體地址對齊 (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))
> ```

### 思考與想法
根據題意，該巨集需要返回一經過記憶體對齊後的大小，也就是說若傳入介於 `1~16` 之值，需要回傳 `16` ，若傳入 `0` ，則需要回傳 `0` 。我們先不考慮傳入值為 `0` 的情形，若假設傳入數值為 `3` ：

                        x 00000011
        x + MAX_ALIGNMENT 00010011

因為需要回傳 `16` 也就是 `00010000` ，且 `bitwise` 的運算為 `&` ，因此我們可以知道 `~(NNN)` 的值為 `11111100` ，但是因為最後面的 `0` 是根據 `x + MAX_ALIGNMENT` 才知道需要什麼樣的 `~(NNN)` ，因此 `~(NNN)` 應該是依靠前方的 ` - (MMM)` 來完成 `&` 的。由於 `~` 的關係，大部分的位元應該都是 `1` ，若要前方皆為 `1` ，後方不為 `1` ，只能令 `NNN` 為 `MAX_ALIGNMENT - 1` ，此時 `~(NNN)` 為 `11110000` ，這樣變可以讓 `MAX_ALIGNMENT` 位元中的 `1` 可以被 `&` 到，並且 `x + MAX_ALIGMENT` 的剩下位元也不會計算出來。

但是當傳入值為 `0` 時， `x + MAX_ALIGNMENT` 為 `00010000` ， `~(NNN)` 為 `11110000` ，此時卻會回傳 `16` ，但是其實必須回傳 `0` ，因此 `MMM` 應該為 `1` ，因為 `x + MAX_ALIGnMENT - 1` 為 `00001111` ，而 `~(NNN)` 為 `11110000` ，此時剛好會回傳 `0` ，並且輸入 `1~16` 時也不會影響原本的輸出。

:::success
MMM : 1
NNN : 15
:::

## 測驗 `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)); \
> })
> ```

### 思考與想法
由程式碼中可以總共分出四種情況，分別為 `x` 是 `int` 或是 `uint` ，和 `divisor` 分別是 `int` 和 `uint` 。

* `x` 為 `int` 且 `divisor` 為 `int`

由於 `__x` 會與 `x` 的變數型態相同，且 `__d` 會與 `divisor` 的變數型態相同。因此在進入 `? :` 判斷式時，因為型態皆為 `int` ，因此前兩個條件 `-1 > 0` 為否，第三個條件 `(__x > 0) == (__d > 0)` 因為 `__d` 必定大於零，因此要依 `__x` 是否大於零或小於零，若大於零則為真，會回傳第一個結果： `(RRR) / (__d)` 若不大於零則為否，會回傳第二個結果： `(SSS) / (__d)` 。

* `x` 為 `int` 且 `divisor` 為 `uint`

此時 `((typeof(x)) -1) > 0` 為否，而 `((typeof(divisor)) -1) > 0` 為真，所以也會回傳第一個結果 `(RRR) / (__d)` 。

* `x` 為 `uint` 且 `divisor` 為 `int`
此時 `((typeof(x)) -1) > 0` 為真，而 `((typeof(divisor)) -1) > 0` 為否，所以也會回傳第一個結果 `(RRR) / (__d)` 。

* `x` 為 `uint` 且 `divisor` 為 `uint`
此時 `((typeof(x)) -1) > 0` 為真，而 `((typeof(divisor)) -1) > 0` 為真，所以也會回傳第一個結果 `(RRR) / (__d)` 。

以下為 `x` 與 `divisor` 的各種情況：

| | `divisor` 為 `int` | `divisor` 為 `uint` |
|:---------------------:|:------------------:|:-------------------:|
| `x` 為 `int` 且 `> 0` | `(RRR) / (__d)` | `(RRR) / (__d)` |
| `x` 為 `int` 且 `< 0` | `(SSS) / (__d)` | `(RRR) / (__d)` |
| `x` 為 `uint` | `(RRR) / (__d)` | `(RRR) / (__d)` |

由上表可以知道，只有在 `x` 為 `int` 且 `< 0` 並且 `divisor` 為 `int` 的情況下才會回傳 `(SSS) / (__d)` ，其餘皆會回傳 `(RRR) / (__d)` 。

由題目之例子，需要輸出離答案最接近的整數，因此若在做除法時，若數值為 `(7, 3)` ，算出來為 2.333... ，則必須要四捨五入至 2 ，反之若數值為 `(5, 3)` ，算出來為 1.666... ，則會四捨五入至 2 ，因此我們可以知道其輸出為 2 的範圍為 5 ~ 7 ，若是需要大於 6 的數字除以 3 輸出為 2 ，我們只要將 `RRR` 定義為 `__x ` ，如此便可以直接計算出需要的數值。而若需要小於 6 的數字除以 3 輸出為 2 ，我們可以將 `RRR` 定義為 `__x + __d` ，這樣可以讓數字足以進位一次，但是這會讓四捨五入變成無條件進位，因此我們需要更改增加的數值，將原本的 `__d` 更改成 `__d >> 1` 。如此一來，便可以避免加過多導致進位，又可以讓小數字可以成功進位。因此 `RRR` 的值為 `__x + (__d >> 1)` ，而 `SSS` 便是處理負數的問題，因此處理方式為剛好相反， `SSS` 的數值為 `__x - (__d >> 1)` 。

:::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;
> }
> ```

### 思考與想法
上述的 `fls()` 函式的主要功能為