owned this note
owned this note
Published
Linked with GitHub
---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `hsuedw` >
* [作業需求](https://hackmd.io/@sysprog/BJJMuNRlq)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
* [作業繳交區](https://hackmd.io/@sysprog/linux2022-homework3)
* Due Date: Mar 21, 2022
---
## 測驗 1
### 題目
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:
* `GENMASK(6, 4)` 產生 011100002
* `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
LEFT = ?
RIGHT = ?
### 作答
* LEFT = `63 - h`
* RIGHT = `l`
### 延伸問題 1. 解釋上述程式碼運作原理
* 為了說明方便，將程式碼補齊後，還原如下:
```c=
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))
```
* 以第 2 行的 `&` (bitwise and operator) 為中心，分為左右兩部分討論。以 `GENMASK(39, 21)` 為例進行討論。
* 先討論右半部 `((~0UL) >> (l) << (l))`
* 因為 `bit 0` 到 `bit l - 1` (`l` 等於 21) 須為 0。所以，必須左移 `l` bits，使得 `bit 0` 到 `bit l - 1` 皆為 0。
* 右半部得到的 bit mask 為 0xffffffffffe00000。
* 接著討論左半部 `((~0UL) >> (64 - h - 1))`
* 最後的結果 bit 63 到 bit 40 共 24 個 bit 須全部為 0。
* 因為已知 bit mask 寬度為 64 bit，所以 MSB 為 bit 63。須左移 `63 - h` 個 bit。
* 因為 `>>` 操作的是無號數 (unsigned integer)，所以每向右移一個 bit，就會在 most significant bit 補一個 0。
* [C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 6.5.7 Bitwise shift operators
> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2^. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
* [Re: right shift of signed type](https://gcc.gnu.org/legacy-ml/gcc/2000-04/msg00152.html)
> An arithmetic left shift is equivalent to a logical left shift
> (as far as GCC is concerned).
>
> For right shifts, if the type is signed, then we use an arithmetic shift;
> if the type is unsigned then we use a logical.
* 位移 (shift) 操作的兩種位移的方式:
* Arithmetic shift (算數位移)
* Right shift 時，空出的 bit 填 MSB
* Left shift 時，空出的 bit 填 0
* Logical shift (邏輯位移)
* Right 與 Left shift 時，空出的 bit 皆填 0
* 參考資料:
[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E5%B8%B8%E6%95%B8%E6%99%82%E9%96%93%E5%AF%A6%E4%BD%9C)
### 延伸問題 2. 比較 Linux 核心 GENMASK ，闡述其額外的考量
`GENMASK(h, l)` 巨集基本上要在 `h >= l` 的前提下才合理。否則，會產生全部都是 0 的 bit mask。Linux 核心中實作的 `GENMASK` 使用 `BUILD_BUG_ON_ZERO` 巨集與 `__builtin_choose_expr` GCC built-in function 檢查 `h` 與 `l` 是否合理。若發現 `l > h` 則強制編譯器發生編譯錯誤。
`GENMASK` 巨集的實作出現在 [include/linux/bits.h](https://github.com/torvalds/linux/blob/master/include/linux/bits.h)。相關程式碼節錄如下。
```c
#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
* BUILD_BUG_ON_ZERO is not available in h files included from asm files,
* disable the input check if that is the case.
*/
#define GENMASK_INPUT_CHECK(h, l) 0
#endif
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
(~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
```
* `BUILD_BUG_ON_ZERO` 實作於 [include/linux/build_bug.h](https://github.com/torvalds/linux/blob/master/include/linux/build_bug.h)。若 `e` 為非零值，則強制編譯器產生編譯錯誤。基本上就是利用 bit-field 的寬度為負值強制使編譯器發生錯誤。
```c
/*
* Force a compilation error if condition is true, but also produce a
* result (of value 0 and type int), so the expression can be used
* e.g. in a structure initializer (or where-ever else comma expressions
* aren't permitted).
*/
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
```
[C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 6.7.2.1 Structure and union specifiers
> The expression that specifies the width of a bit-field shall be an integer constant expression with a nonnegative value that does not exceed the width of an object of the type that would be specified were the colon and expression omitted. If the value is zero, the declaration shall have no declarator.
* `__builtin_choose_expr(const_exp, exp1, exp2)` 是 GCC 的 built-in function。若 `const_exp` 為 true，則回傳 `exp1` 的計算結果(型別與 `exp1` 一致)。否則，回傳 `exp2` 的計算結果(型別與 `exp2` 一致)。
[Built-in Function: type __builtin_choose_expr (const_exp, exp1, exp2)](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
>You can use the built-in function __builtin_choose_expr to evaluate code depending on the value of a constant expression. This built-in function returns exp1 if const_exp, which is an integer constant expression, is nonzero. Otherwise it returns exp2.
>
>This built-in function is analogous to the ‘? :’ operator in C, except that the expression returned has its type unaltered by promotion rules. Also, the built-in function does not evaluate the expression that is not chosen. For example, if const_exp evaluates to true, exp2 is not evaluated even if it has side effects.
>
>This built-in function can return an lvalue if the chosen argument is an lvalue.
>
>If exp1 is returned, the return type is the same as exp1’s type. Similarly, if exp2 is returned, its return type is the same as exp2.
[__is_constexpr](https://github.com/torvalds/linux/blob/master/include/linux/const.h) 為實作在 `include/linux/const.h` 中的巨集。主要是用來檢查輸入參數是否為 constant expression。
```c
/*
* This returns a constant expression while determining if an argument is
* a constant expression, most importantly without evaluating the argument.
* Glory to Martin Uecker <Martin.Uecker@med.uni-goettingen.de>
*/
#define __is_constexpr(x) \
(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
```
[C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 6.6 Constant expressions
> A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.
* 參考資料:
[bit-field](https://hackmd.io/MxZeJGYUR9-j67lx9N6qRg?view)
### 延伸問題 3. 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
* working
---
## 測驗 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 的定義。
請補完，使其行為符合預期。作答規範:
1. `EXP1` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP1` 不得使用 `%` (modulo) 運算子
3. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1`
### 作答
* `EXP1` = `(struct foo *)(v & ~3)`
### 延伸問題 1. 解釋上述程式碼運作原理
根據題意，要將記憶體位址 `v` 對齊到小於或等於 `v` 且能夠被 4 整除的位址上([align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。
> A value at or before value that is a multiple of alignment.
若以二進位表示一個數值，且此數值會被 4 整除，則其 bit 0 與 bit 1 皆為 0。所以，基本上，可實作為 `v & ~3`。
不過，因為 `to_fd()` 是回傳一個 `struct fd` 型態的 object。所以，`v` 向下對齊到可被 4 整除的位址後，須強制轉型為指向 `struct foo` object 的指標。所以，`EXP1` 應寫為 `(struct foo *)(v & ~3)`
### 延伸問題 2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
---
## 測驗 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;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP2` 和 `EXP3` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1``:w
### 作答
* `EXP2` = `(x & 0x33) << 2`
* `EXP3` = `(x & 0x55) << 1`
### 延伸問題 1. 解釋上述程式碼運作原理
* 運作原理就是不斷地對這 8 個位元交錯地地分為兩組，然後左右兩半對調。直到無法再分組為止。
* 以本題對 8 位元無號數做逐一位元反轉為例，如下圖所示。
* 參考資料:
[你所不知道的 C 語言：數值系統篇 省去迴圈](https://hackmd.io/@sysprog/c-numerics#%E7%9C%81%E5%8E%BB%E8%BF%B4%E5%9C%88)
[Reverse integer bitwise without using loop](https://stackoverflow.com/questions/21511533/reverse-integer-bitwise-without-using-loop)
### 延伸問題 2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
* working
---
## 測驗 4
### 題目
延伸 [〈你所不知道的 C 語言：前置處理器應用篇〉](https://hackmd.io/@sysprog/c-preprocessor)，我們嘗試將 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__})))
```
請補完，使其行為符合預期。作答規範:
1. `EXP4` 和 `EXP5` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 ( 和 ))
### 作答
* `EXP4` = `++_foreach_i`
* `EXP5` = `++_foreach_i`
:::spoiler 完整程式碼
```c
#include <stdio.h>
#include <stdarg.h>
#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})[++_foreach_i])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[++_foreach_i], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
int main()
{
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);
}
return 0;
}
```
:::
### 延伸問題 1. 解釋上述程式碼運作原理
`foreach_int` 的說明如下:
* `__VA_ARGS__` 是屬於前置處理器 (preporcessor) 的功能。主要是用來實作不確定個數的參數。以 `foreach_int` 為例，經前置處理器展開後，程式碼如下所示。
> [C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 6.10.3 Macro replacement
> The identifier `__VA_ARGS__` shall occur only in the replacement-list of a function-like
> macro that uses the ellipsis notation in the parameters.
```c
int i;
for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) {
printf("i is %i\n", i);
}
```
* `(int[]){0, -1, 100, 0, -99}` 表示一個長度為 5 的整數陣列，其各元素值分別為 0, -1, 100, 0, -99。
* `((int[]){0, -1, 100, 0, -99})[0])` 就是讀取該整數陣列索引值為 0 的那個元素，也就是第一個 0。
* `((i) = ((int[]){0, -1, 100, 0, -99})[0])` 就是將整數陣列索引值為 0 的那個元素的值指派給變數 `i`。所以，到目前為止，變數 `i` 的值為 0。
* 到目前為止 `unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0)` 這段程式碼可以概念上的看作為 `unsigned _foreach_i = (0, 0)`。第一個 0 是因為變數 `i` 被指派為 0 (assignment expression)。第二個 0 是題目程式碼中原本的數字常數。基本上，這個看其來很複雜的程式碼就是做兩件事。
* 第一，把整數陣列的第一個元素值指派給變數 `i`，所以變數 `i` 的值為 0。
* 第二，把變數 `_foreach_i` 初始化為 0 (就是 `unsigned _foreach_i = (0, 0)` 裡的第二個 0)。這與 `,` 和 `=` 兩個運算子的優先順序與 `,` 運算子的結合性(associativity)有關。
> [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence)
> [Difference between "int i=1,2,3" and "int i=(1,2,3)" - variable declaration with comma operator [duplicate]](https://stackoverflow.com/questions/17251584/difference-between-int-i-1-2-3-and-int-i-1-2-3-variable-declaration-with)
> [C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf), 6.5.16 Assignment operators
> An assignment operator stores a value in the object designated by the left operand. An
> assignment expression has the value of the left operand after the assignment, but is not
> an lvalue. The type of an assignment expression is the type of the left operand unless the
> left operand has qualified type, in which case it is the unqualified version of the type of
> the left operand. The side effect of updating the stored value of the left operand shall
> occur between the previous and the next sequence point.
* 接下來，執行 `printf()`。因為變數 `i` 已經被指派為整數陣列的第一個元素值，所以會印出 `i is 0`。
* 在 `for` 迴圈進入下一回合的迭代之前，會先檢查變數 `_foreach_i` 的值是否小於整數陣列的長度。
* 若變數 `_foreach_i` 的值小於整數陣列的長度，則會執行 `(i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]`。因為此時變數 `_foreach_i` 為 0，也就是指向整數陣列的第一個元素，所以要用 prefix increment operator 讓變數 `_foreach_i` 先遞增 1，也就是指向第二個元素。然後再將整數陣列的第二個元素值指派給變數 `i`。所以，變數 `i` 就會是 -1。然後，又再一次執行 `printf()` 把 `i is -1` 印出來。
* 以此類推，直到把整個整數陣列的所有元素都走訪一遍為止。
`foreach_ptr` 的實作手法與 `foreach_int` 如出一轍。
### 延伸問題 2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
---
## 測驗 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;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP6` 和 `EXP7` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 ( 和 ))
### 作答
* `EXP6` = `dvs << shift`
* `EXP7` = `dvd -= dvs << shift`
### 延伸問題 1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
為了說明方便，將程式碼補齊後，如下:
```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 > (dvs << shift))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
dvd -= dvs << shift;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
* 第 4~15 行在處裡正負號的問題。若被除數(`dividend`)與除數(`divisor`)間，一為正，另一為負。則最後的答案為負。所以變數 `signal` 會被指派為 `-1`。且變數 `dvd` 會被指派為變數 `dividend` 的絕對值，變數 `dvs` 會被指派為變數 `divisor` 的絕對值。接下來就以 `dvd` 與 `dvs` 做除法運算。
* 第 17~27 行就是在執行除法運算。當程式執行到第 28 行時，變數 `res` 的值就是除法運算中的商數，變數 `dvd` 的值就是餘數。
* 第 29~30 行。若最後的答案為正，且變數 `res` (型態為 `unsigned int`)的值大於或等於有號整數的最大值(`INT_MAX`)，則回傳 `INT_MAX`。
* 第 31 行，回傳最後結果。
### 延伸問題 2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論
---
## 測驗 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;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP8` 和 `EXP9` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP8` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP9` 為包含 `list_` 開頭巨集的單一敘述
### 作答
* `EXP8` = `pn->p1 == p1`
* `EXP9` = `list_add(&pn->link, &heads[hash])`
### 延伸問題 1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
### 延伸問題 2. 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
---
## 測驗 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. `EXP10` 和 `EXP11` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP11` 不該出現小括號 (即 ( 和 ))
3. `EXP10` 和 `EXP11` 皆包含 > 運算子
### 作答
* `EXP10`: `(v > 0x3) << 1`
* `EXP11`: `ret += v > 1`
### 延伸問題 1. 解釋上述程式碼運作原理
* 基本上就是要找到在二進位表示法中，最前面那個為 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 = (v > 0x3) << 1;
v >>= m;
ret |= m;
ret += v > 1;
return ret;
}
```
* 整個演算法就是在算 $\lfloor\log_{2}2^x\rfloor = \log_{2}2^{ret} = ret$
* 觀察一下程式碼，不難發現有個規則存在。第 4~6 行一組。第 7~9 行一組。第 10~12 行一組。第 13~15 行一組。
* 先說明第 4~6 行。假設 `v` 大於 `0xFFFFU` 表示第一個為 1 的位元落在 bit 31~16 之間。否則，落在 bit 15~0 之。
* 如果 `v > 0xFFFFU` 成立，將 2^4^ 指派給 `m` ，也就是 `m` 的值是 16。接著 `v` 往左位移 16 個位元(第 5 行)。也就是第一個為 1 的位元往左位移 16 個位元。然後把 `m` 累加到 `ret` 中。
* 如果 `v > 0xFFFFU` 不成立，將 0 指派給 `m`。 `v` 與 `ret` 的值維持不變。
* 其餘的部分以此類推就可以知道 `EXP10` 應該實作為 `(v > 0x3) << 1`。
* 事實上，第 16 行是下面三行程式碼的簡化。若把第 16 行還原成下列三行，不難發現，與前面的規則一致。
```c
m = (v > 0x1) << 0;
v >>= m;
ret += m;
```
<!-- * 為什麼可以簡化? 當程式執行到第 16 行的時候， `v` 最多已經歷過右移 30 個位元。此時 `v` 的值可能是 0~10~，1~10~，2~10~ 或 3~10~ -->
### 延伸問題 2. 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
### 延伸問題 3. 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
### 延伸問題 4. 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作
---
## 測驗 8
### 題目
考慮以下 C++ 二元搜尋樹的程式:
:::spoiler 原本程式碼
```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;
}
```
請補完，使其行為符合預期。作答規範:
`EXP12`, `EXP13` 和 `EXP14` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息，並善用 indirect pointer 的技巧來撰寫
`EXP12`, `EXP13` 和 `EXP14` 皆不該出現 ;
### 作答
* `EXP12`: `p = &(*p)->left`
* `EXP13`: `p = &(*p)->right`
* `EXP14`: `&(*r)->left`
### 延伸問題 1. 解釋上述程式碼運作原理
* C 語言的指標就是一個變數。這個變數的值是另一個 object 的記憶體位址。而指標的指標還是一個變數，這個變數的值是另一個指標的記憶體位址。
* 二元搜尋樹是一種二元樹，其左子樹中所有節點的值必小於根結點的值，其右子樹所有節點的值必大於根節點的值。且左右子樹也都是二元搜尋樹。
> [Binary tree](https://en.wikipedia.org/wiki/Binary_tree)
> [Binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree)
* 為了說明方便，將程式碼補齊後，如下所示:
```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;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
p = &(*p)->left;
else
p = &(*p)->right;
}
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 = &(*r)->left;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
* `remove_data()` 的作用是要將 `t` 所指向的二元搜尋樹中，具有與變數 `d` 的值相同的節點刪除。
* 首先就是要嘗試在題目給的二元搜尋樹中尋找具有與變數 `d` 的值相同的節點，第 15~21 行就是在做這件事。根據二元搜尋樹的定義，當要尋找的目標值小於當前節點的值時，就要往左子樹移動。反之，往右子樹移動。如下圖所示，用指標的指標 `p` 走訪二元搜尋樹。
* 當程式執行到第 22 行時，只有兩種狀況。第一種就是在二元搜尋樹中找到要刪除的節點，也就是說 `*p` 不為 `NULL`。第二種就是想要刪除的節點不在二元搜尋樹中，也就是說 `*p` 為 `NULL`。
* 若是第一種狀況，則程式繼續往下執行，將節點刪除。否則，在第 24 行返回，並結束 `remove_data()` 的工作。
* 我們接著第一種狀況繼續說明。此時，如下圖所示。指標 `q` 指向即將被刪除的節點。指標 `p` 指向父節點中指向即將被刪除的節點的指標。
* 第 26~38 行。
* 若 `q` 所指向之節點(也就是即將被刪除的節點)的左子樹為空，則 `p` 指向該節點的右子樹(此右子樹可能為空，也可能不為空)。然後刪除 `q` 所指向之節點。
* 若 `q` 所指向之節點(也就是即將被刪除的節點)的右子樹為空，則 `p` 指向該節點的左子樹。然後刪除 `q` 所指向之節點。
* 若 `q` 所指向之節點(也就是即將被刪除的節點)的左右子樹皆不為空，則先找到指標 `q` 所指節點的 inorder successor，再將 inorder successor 的資料指派給指標 `q` 所指的節點。因為二元搜尋樹的 inorder traversal 的結果就是由小到大的排列結果，所以用 inorder success 的值取代指標 `q` 所指的節點 (就是即將被刪除的節點) 的資料，再將 inorder successor 刪除，可保持二元收尋樹的特性。刪除流程如下圖所示。
### 延伸問題 2. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
### 延伸問題 3. 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
---
## 測驗 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))
```
作用是向上對齊 (roundup)，請補完程式碼，使其行為符合預期。作答規範:
* `MMM` 是常數
* `NNN` 是表示式
* `MMM` 和 `NNN` 皆不得出現小括號 (即 ( 和 ))
* 符合作業一的排版和程式碼風格規範
* 以符合 C99 的最精簡形式撰寫
### 作答
* `MMM`: `1`
* `NNN`: `MAX_ALIGNMENT - 1`
### 延伸問題 1. 解釋上述程式碼運作原理，並撰寫出對應 `ROUND_DOWN` 巨集
* 這一題意思是要把輸入 `x` 的向上調整到 16 的整數倍。
* 如果 x 的值為 1~16，則調整為 16。
* 如果 x 的值為 17~32，則調整為 32。
* 如果 x 的值為 33~48，則調整為 48。
* 為了說明方便，將程式碼補齊。如下所示。
```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 - 1) & ~(MAX_ALIGNMENT - 1))
```
* `x` 向上對齊為 16 的倍數後，必大於或等於 `x` 目前的值。所以，對 `x` 加上 15 後，再與 ~15 做 bitwise AND，把 bit 0~3 清為 0。
* 以 `x` 的值介於 1~16 為例，`x` 加上 `MAX_ALIGNMENT - 1` (即 15)之後，就會介於 16~31 之間。然後再與 `~(MAX_ALIGNMENT - 1)` (即 ~15)做 bitwise AND 就可保留 bit 4 的 1，並且把 bit 0~3 清為 0。
* 所以 `MMM` 與 `NNN` 分別實作為 `1` 與 `MAX_ALIGNMENT - 1`。
### 延伸問題 2. 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
---
## 測驗 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`
作答規範:
* 符合作[業一](https://hackmd.io/@sysprog/linux2022-lab0)的排版和程式碼風格規範
* `RRR` 和 `SSS` 為表示式，且都包含 `(__x)` 和 `(__d)` (注意小括號)
* `RRR` 和 `SSS` 限用 `+`, `-`, `>>`, `<<` 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
* 變數在 `RRR` 和 `SSS` 出現的順序 (從左到右)，必定是 `__x` 先於 `__d`
* 請補完程式碼，使其行為符合預期。
### 作答
* `RRR` = `(__x) + ((__d) >> 1)`
* `SSS` = `(__x) - ((__d) >> 1)`
### 延伸問題 1. 解釋上述程式碼運作原理
就我的理解，這一題應該是要求 `x` 除以 `divisor` 後，取四捨五入。為了說明方便，將成碼補齊後，如下所示。
```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))) \
? (((__x) + ((__d) >> 1)) / (__d)) \
: (((__x) - ((__d) >> 1)) / (__d)); \
})
```
以變數 `x` 為例，第 5 行的 `((typeof(x)) -1) > 0` 判斷式作用檢查 `x` 是否為無號數。若 `x` 為無號數，則判斷式成立。反之，若 `x` 是否為有號數，則判斷式不成立。同樣的想法可套用在 `((typeof(divisor)) -1) > 0` 上。
> 參考資料:
> [6.7 Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
> [你所不知道的C語言：技巧篇, 善用 GNU extension 的 typeof](https://hackmd.io/@sysprog/c-trick#%E5%96%84%E7%94%A8-GNU-extension-%E7%9A%84-typeof)
> [解讀計算機編碼](https://hackmd.io/@sysprog/rylUqXLsm)
第 6 行。`(((__x) > 0) == ((__d) > 0))` 的功用是在判斷是否同時為正整數，同時為負整數，或者同時為 0。也就是執行除法運算後，結果是否大於或等於 0。若是，則判斷式成立。否則，判斷式不成立。
綜合以上所述，當下列兩個條件同時成立時，就會執行第 8 行的運算式。否則，執行第 7 行的運算式。
* `x` 與 `divisor` 同時為有號數。
* `x` 與 `divisor` 一為正整數，另一為負整數，或者不同時為 0。
C99 standard 對整數除法的描述如下。所以，C 語言的除只取商數，小數部分則是無條件捨去。
> 6.5.5 Multiplicative operators
> The result of the / operator is the quotient from the division of the first operand by the
> second; the result of the % operator is the remainder. In both operations, if the value of
> the second operand is zero, the behavior is undefined.
> When integers are divided, the result of the / operator is the algebraic quotient with any
> fractional part discarded.^88)^ If the quotient a/b is representable, the expression
> (a/b)*b + a%b shall equal a.
>
> 88\) This is often called ‘‘truncation toward zero’’
先假設 `x` 與 `divisor` 不同時為有號數，或者執行除法算後結果大於或等於 0。兩數相除，
* 假設小數部分大於或等於 0.5。則在相除之前，先讓 `x` 加上 `divisor / 2` 再與 `divisor` 相除。就可以達到五入的效果。
* 假設小數部分小於 0.5。則在相除之前，先讓 `x` 加上 `divisor / 2` 再與 `divisor` 相除。就可以達到四捨的效果。也就是在 `x` 加上 `divisor / 2` 前，效果一樣。
* 所以 `RRR` 應寫為 `(__x) + ((__d) >> 1)`。
反之，`x` 與 `divisor` 同時為有號數，且執行除法算後結果小於 0。則 `SSS` 應寫為 `(__x) - ((__d) >> 1)`。
### 延伸問題 2. 在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合
[include/linux/math.h](https://github.com/torvalds/linux/blob/master/include/linux/math.h)
---
## 測驗 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))`
作答規範:
* 符合作業一的排版和程式碼風格規範
* `XXX`, `YYY` 和 `ZZZ` 都是敘述，不得呼叫任何函式，且不包含 ; 字元
* 只能使用 `=`, `+=`, `-=`, `>>=`, `<<=` 等運算子，且不得出現小括號 (即 ( 和 ))
* 以符合 C99 的最精簡形式撰寫
### 作答
* `XXX` = `y >>= 1`
* `YYY` = `x -= b`
* `ZZZ` = `m >>= 2`
### 延伸問題 1. 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
為了說明方便，將程式碼補齊後，還原如下。
```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;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
第 1~28 行。 `fls()` 的功用是在計算其輸入參數 `word` 在二進位表示法中，最高位個為 1 的位元的位置。
> fls(010011010010~2~) = 10~10~
參考資料
* [wiki, Digit-by-digit algorithm](https://en.wikipedia.org/wiki/Integer_square_root#Digit-by-digit_algorithm)
* [wiki, Digit-by-digit algorithm](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation)
* 以下是 [kdnvt](https://hackmd.io/Q0ZdueYVR2KGa_QL8wMRIw?view#%E6%B8%AC%E9%A9%97-11) 同學的解釋。
> [直式開方法](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation)
>
> 雖然教授問答的時候是從二進位的角度去想，但我第一次看到類似的原理其實是從十進位的直式開方法。不過直式開方法所有進位都適用，所以從十進位的想法轉成二進位也沒有很難。
> 直式開方法是把要開方的數拆成二的冪相加（如果是十進位就是十的冪），就可以拆成以下的形式：
>
> $x = (000b_0b_1b_2\cdots b_{n-1}b_{n})^2$
>
> 上面的 $000b_0b_1b_2\cdots b_{n-1}b_{n}$ 為 bits pattern 。
> $b_0$ 為最高位的 1 ，
> 寫成數學式如下：
>
> $x = (2^{n}b_0+2^{n-1}b_1+\cdots+2^1b_{n-1}+2^0b_{n})^2$
>
> $a_i = 2^{n-i}b_i$
>
>
> $\begin{aligned}x
> &=(a_0+a_1+\cdots+a_{n-1}+a_{n})^2 \\
> &= a_0^{2}+2a_0a_1 + a_1^2 + 2(a_0+a_1)a_2 + a_2^2 + \cdots + a_n-1^2 + 2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)a_n + a_n^2 \\
> &=a_0^2 + (2a_0+a_1)a_1 + [2(a_0+a_1)+a_2]a_2 + \cdots + [2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)+a_n]a_n \end{aligned}$
>
> 最後的形式為 $[2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)+a_n]a_n$ 的相加，而這每一項其實就是程式中每一輪迴圈
> ```
> if (x >= b) {
> x -= b;
> y += m;
> }
> ```
> 要判斷並可能減掉的 `b` 。
>
> 以下大致講解原理：
> 迴圈從 0 開始。
> $y_i$ 為每個第 $i$ 個迴圈一開始的 `y` 值。
> $m_i$ 為每個第 $i$ 個迴圈一開始的 `m` 值。
> $l_i$ 為 $\sqrt m_i$ 。
>
> $y_0 = 0$
>
> $m_i = l_i^2$
>
> $l_i = 2^{n-i}$
>
> 因為確定 $a_0$ 是最高位不為零，所以 $a_0 = l_0$
>
> $y_1 = m_0 = l_0^2 = a_0^2 = l_0a_0$
>
> 而每經過一輪 $m$ 會右移兩位，他的平方根 $l$ 就等於右移一位：
> $m_i = m_{i+1}\times4$
> $l_i = l_{i+1}\times2$
>
> $y_1 = l_0a_0$
> $y_1 = 2l_1a_0$
> $y_1+m_1 = 2l_1a_0 + l_1^2 = (2a_0+l_1)l_1$
> 如果此時 $y_1+m_1$ 的結果小於當前的 $x$ ，代表 $x$ 的展開式中 $(2a_0+a_1)a_1$ 這項不為零，也就是 $a_1 = 2^{n-1} = l_1$ 。將 $y_1$ 右移一位後加上 $m_1$ ，就會變成
> $y_2 = \dfrac{y_1}{2} + m_1 = l_1a_0 + l_1^2 = l_1(a_0+a_1) = 2\times l_2(a_0+a_1)$
>
> 而如果此時 $y_1+m_1$ 的結果大於當前的 x ，代表 $x$ 的展開式中 $(2a_0+a_1)a_1$ 這項等於零，也就是 $a_1 = 0$ 。將 $y_1$ 右移一位後就會變成
> $y_2 = \dfrac{y_1}{2} = l_1a_0 = l_1(a_0+a_1) = 2\times l_2(a_0+a_1)$
>
> 照同樣的原理推下去可以發現， $y_j$ 其實就等於 $2\left(\sum\limits_{i = 0}^{j-1}{a_i}\right)l_j$ 。因為不是所有的 $l_j 都會等於 a_j$ ，所以我用另一個變數 $z_j = 2\left(\sum\limits_{i = 0}^{j-1}{a_i}\right)a_j$ 來表達原式中的部份，$z_j = \dfrac{y_ja_j}{l_j}$ ，如果 $a_j = l_j$ 也就是 $a_j \neq 0$ ，則 $z_j$ 會等於 $y_j$ 而且下圖的 $a_i^2$ 會等於 $m_i$ ：
>
> $\underbrace{a_0^2}_{z_0+a_0^2} + \underbrace{(2a_0+a_1)a_1}_{z_1+a_1^2} + \underbrace{[2(a_0+a_1)+a_2]a_2}_{z_2+a_2^2} + \cdots + \underbrace{[2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)+a_n]a_n}_{z_n+a_n^2}$
>
> $z_i+a_i^2 = \left\{
> \begin{array}{r}
> 0 , & \text{if }a_i=0 \\
> y_i + m_i , & \text{if } a_i=l_i
> \end{array}
> \right.$
>
> 每一輪迴圈就是判斷 $x$ 有沒有 $z_i+a_i^2$ 並更新 $y_i$，
>
> 到了最後的 $y_n = 2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)l_n = 2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)2^0 = 2\left(\sum\limits_{i = 0}^{n-1}{a_i}\right)$ ， $y_n$ 會先往右移變成 $\sum\limits_{i = 0}^{n-1}{a_i}$ ，在加上最後的 $a_n$ ，變成 $\sum\limits_{i = 0}^{n}{a_i}$ ，就是我們要求的平方根。
>
### 延伸問題 2. 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景
[lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/master/lib/math/int_sqrt.c)
[arch/xtensa/include/asm/bitops.h](https://elixir.bootlin.com/linux/v5.13.19/source/arch/xtensa/include/asm/bitops.h#L75)
---
Google Drive
Gist
Clipboard
Sign in with Wallet
