# 2022q1 Homework3 (quiz3)
contributed by <```DokiDokiPB```>
> [2022q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)
### 測驗 ```1```
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
取 ```LEFT``` 為 ```63 - h``` (題目假設為 64 位元，取 64 - 1 = 63)
取 ```RIGHT``` 為 ```l```
利用在測驗題敘述中的例子作說明，有 8 位元：```GENMASK(6, 4)``` 產生 $0111 \space 0000_2$
1. ```~0UL``` 產生 $1111 \space 1111_2$
2. ```(~0UL) >> (8 - 6 + 1)``` 產生 $0111 \space 1111_2$
3. ```(~0UL) >> (l)``` 產生 $0000 \space 1111_2$
4. ``` ... << (RIGHT)``` 產生 $1111 \space 0000_2$
5. 最後取 ```&```
第 2 步驟中，目的是產生最高位有 ```7 - h``` 個零，而第 4 步產生最低位有 ```l``` 個零。
#### 延伸問題：比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
> - 延伸問題的內容跟如何閱讀是參考自 [hsuedw 的筆記](https://hackmd.io/@hsuedw/linux2022-quiz3#%E5%BB%B6%E4%BC%B8%E5%95%8F%E9%A1%8C-2-%E6%AF%94%E8%BC%83-Linux-%E6%A0%B8%E5%BF%83-GENMASK-%EF%BC%8C%E9%97%A1%E8%BF%B0%E5%85%B6%E9%A1%8D%E5%A4%96%E7%9A%84%E8%80%83%E9%87%8F)
> - [The Linux Kernel Archives](https://www.kernel.org/) 下載 Linux 原始程式碼，以下程式碼使用 Linux-5.17.1 版本
```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
#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))
```
與測驗題中的差異在於，使用 ```GENMASK_INPUT_CHECK(h, l)``` 在編譯時期檢查是否輸入錯誤的參數，例如 ```GENMASK(4, 6)```。
##### ```BUILD_BUG_ON_ZERO```
實作於 ```include/linux/build_bug.h```
```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)); })))
```
根據註釋，若參數輸入 ```e``` 為 ```0```，巨集將會擴展為 ```struct { int: 0; }```，屬於合法的程式碼。 但若輸入的數字為非零，將會被擴展為 ```struct { int : -1; }```，無法通過編譯。
##### ```__builtin_choose_expr(const_exp, exp1, exp2)```
為 GCC 的 built-in function
> You can use the built-in function *builtinchooseexpr* to evaluate code depending on the value of a constant expression.
> This built-in function returns *exp1* if *constexp*, 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.
> 來源：[Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
根據註釋，是根據 *const_exp* 決定輸出哪個表示式，效果類似於 C language 的 "? :" 運算子。
##### ```__is_constexpr```
位於 ```include/linux/const.h``` 的巨集。
```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)))
```
根據註釋，用於判斷輸入的參數是否為 constant expression，在執行階段前被計算出來的表示式。
> Constant Expression:
> A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.
>
> 來源 C99 Standard
#### 延伸問題：舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例
:::warning
這裡觀察局部的程式碼的實作，但是尚未有想法能夠解說此應用案例
:::
透過搜尋字串 ```include <linux/bitfield.h>``` 查詢到檔案 [```arch/arm64/kvm/hyp/pgtable.c``` ](https://github.com/torvalds/linux/blob/master/arch/arm64/kvm/hyp/pgtable.c) ，擷取部分的程式碼作為延伸問題的項目。
```pgtable.c``` 使用 ```bitfield.h``` 中的 ```FIELD_PREP```，以下列出部分的程式碼實作。
##### ```include/linux/bitfield.h```
```c
#define __bf_shf(x) (__builtin_ffsll(x) - 1)
/**
* FIELD_PREP() - prepare a bitfield element
* @_mask: shifted mask defining the field's length and position
* @_val: value to put in the field
*
* FIELD_PREP() masks and shifts up the value. The result should
* be combined with other fields of the bitfield using logical OR.
*/
#define FIELD_PREP(_mask, _val) \
({ \
__BF_FIELD_CHECK(_mask, 0ULL, _val, "FIELD_PREP: "); \
((typeof(_mask))(_val) << __bf_shf(_mask)) & (_mask); \
})
```
```__builtin_ffsll(x)``` 與 ```int __builtin_ffs (int x)``` 類似，差異在於使用 ```long long```
> Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
> 來源：[Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
```FIELD_PREP(_mask, _val)``` 將輸入的數值與 ```_mask``` 對齊，擁有一樣的 ```ffs``` 數值。
##### [```arch/arm64/kvm/hyp/pgtable.c``` ](https://github.com/torvalds/linux/blob/master/arch/arm64/kvm/hyp/pgtable.c)
```c=
#define KVM_PTE_LEAF_ATTR_LO_S1_ATTRIDX GENMASK(4, 2)
#define KVM_PTE_LEAF_ATTR_LO_S1_AP GENMASK(7, 6)
#define KVM_PTE_LEAF_ATTR_LO_S1_AP_RO 3
#define KVM_PTE_LEAF_ATTR_LO_S1_AP_RW 1
#define KVM_PTE_LEAF_ATTR_LO_S1_SH GENMASK(9, 8)
#define KVM_PTE_LEAF_ATTR_LO_S1_SH_IS 3
#define KVM_PTE_LEAF_ATTR_LO_S1_AF BIT(10)
...
enum kvm_pgtable_prot {
KVM_PGTABLE_PROT_X = BIT(0),
KVM_PGTABLE_PROT_W = BIT(1),
KVM_PGTABLE_PROT_R = BIT(2),
KVM_PGTABLE_PROT_DEVICE = BIT(3),
KVM_PGTABLE_PROT_SW0 = BIT(55),
KVM_PGTABLE_PROT_SW1 = BIT(56),
KVM_PGTABLE_PROT_SW2 = BIT(57),
KVM_PGTABLE_PROT_SW3 = BIT(58),
};
...
static int hyp_set_prot_attr(enum kvm_pgtable_prot prot, kvm_pte_t *ptep)
{
bool device = prot & KVM_PGTABLE_PROT_DEVICE;
u32 mtype = device ? MT_DEVICE_nGnRE : MT_NORMAL;
kvm_pte_t attr = FIELD_PREP(KVM_PTE_LEAF_ATTR_LO_S1_ATTRIDX, mtype);
u32 sh = KVM_PTE_LEAF_ATTR_LO_S1_SH_IS;
u32 ap = (prot & KVM_PGTABLE_PROT_W) ? KVM_PTE_LEAF_ATTR_LO_S1_AP_RW :
KVM_PTE_LEAF_ATTR_LO_S1_AP_RO;
if (!(prot & KVM_PGTABLE_PROT_R))
return -EINVAL;
if (prot & KVM_PGTABLE_PROT_X) {
if (prot & KVM_PGTABLE_PROT_W)
return -EINVAL;
if (device)
return -EINVAL;
} else {
attr |= KVM_PTE_LEAF_ATTR_HI_S1_XN;
}
attr |= FIELD_PREP(KVM_PTE_LEAF_ATTR_LO_S1_AP, ap);
attr |= FIELD_PREP(KVM_PTE_LEAF_ATTR_LO_S1_SH, sh);
attr |= KVM_PTE_LEAF_ATTR_LO_S1_AF;
attr |= prot & KVM_PTE_LEAF_ATTR_HI_SW;
*ptep = attr;
return 0;
}
```
在第 48 至 51 行中，使用```FIELD_PREP```, ```KVM_PTE_LEAF_ATTR_LO_S1_AP``` = ```GENMASK(7, 6)``` ，設定數值。
---
### 測驗 ```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};
}
```
取```EXP3``` 為 ```v & ~3UL```
其中 ```~3UL``` 表示 0xFFFFFFFC，```v & ~3UL``` 將最低的兩個位元設為零
位址 ```unsigned long v``` 可能為某個 2 的冪，並且透過 ```v & 3``` 可以得知最低的兩個位元用於紀錄 FOO_FLAGS。最終可以推導出 ```unsigned long v``` 為 4 的倍數
> data 的 address 可以公平的被 1, 2, 4, 8,這些數字整除，從這些數字可以發現他們都是 2 的 N 次方 (N為從 0 開始的整數)。換句話說，這些 data object 可以用 1, 2, 4, 8 byte 去 alignment
> 節錄自〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性 data alignment](https://hackmd.io/@sysprog/c-memory#data-alignment)〉
#### 延伸問題：在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
> [The Linux Kernel Archives](https://www.kernel.org/) 下載 Linux 原始程式碼，以下程式碼使用 Linux-5.17.1 版本
在 Linux Source Code 搜尋 ```align_down``` ，檔案範圍限定在 fs 資料夾，可以得到 ```fs/btrfs/inode.c```
> Btrfs
> Btrfs is a computer storage format that combines a file system based on the copy-on-write (COW) principle with a logical volume manager.
> 來源： [Wikipedia Btrfs](https://en.wikipedia.org/wiki/Btrfs)
---
### 測驗 ```3```
```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;
}
```
取 ```EXP2``` 為 ```(x & 0x33) << 2``` ($0x33 = 0b00110011$)
取 ```EXP3``` 為 ```(x & 0x55) << 1``` ($0x55 = 0b01010101$)
透過一個簡單的例子解釋：
例如 $ABCD \rightarrow DCBA$
1. AB 與 CD 對調位置，獲得 $CD \space AB$
2. C 與 D 對調位置，獲得 $DC$；B 與 A 對調位置，獲得 $BA$；
3. 最終獲得 $DCBA$
#### 延伸問題
ethernet 相關可以找到程式碼
---
### 測驗 ```4```
```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__})))
```
取 ```EXP4``` 為 ```++_foreach_i```
取 ```EXP5``` 為 ```++_foreach_i```
##### 第一個巨集 ```#define foreach_int(i, ...)```
透過 vscode 編輯器提供的巨集擴展，例如以下程式碼：
```c
foreach_int(i, 1, 2, 3, 4, 5, 6) { printf("%d ", i); }
```
擴展為：
```c=
for (unsigned _foreach_i = (((i) = ((int[]){1, 2, 3, 4, 5, 6})[0]), 0);
_foreach_i < sizeof((int[]){1, 2, 3, 4, 5, 6}) / sizeof(int);
(i) = ((int[]){1, 2, 3, 4, 5, 6, 0})[++_foreach_i]) {
printf("%d ", i);
}
```
```_foreach_i``` 在此 macro 中，數值會依序為 ```0``` 至 ```5```，```i``` 則為 ```1``` 至 ```5```
##### 第二個巨集 ```#define foreach_int(i, ...)```
透過 vscode 編輯器提供的巨集擴展，例如以下程式碼：
```c
char *pp;
foreach_ptr(pp, "Hello", "World"){}
```
擴展為：
```c
for (unsigned _foreach_i = (((pp) = (void *)((typeof(pp)[]){"Hello", "World"})[0]), 0);
(pp);
(pp) = (void *)((typeof(pp)[]){"Hello", "World", NULL})[++_foreach_i], ...) {
}
```
```pp``` 的數值依序為```{"Hello", "World", NULL}```，當 ```pp``` 為 ```NULL```，即離開這個迴圈
#### 延伸問題
stdarg
---
### 測驗 ```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;
}
```
取 ```EXP6``` 為 ```dvs << shift```
取 ```EXP7``` 為 ```dvd -= dvs << shift```
根據 [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，輸入 8.325 會捨入至 8、輸入 -2.735 會捨入至 -2，屬於無條件捨去小數點。1並且輸出結果為商數，需要包含正負號
在此測驗題的程式碼中，第 4 ~ 15 行處理正負問題，並在最後輸出結果時處理。
第 17 ~ 27 中，根據直除法計算方式，先從高位數字開始算起，往低位減去除數。
示範以上程式碼過程：
```
dividend = 97
divisor = 2
97 - 64 = 33 // divisor * 2^5
33 - 32 = 1 // divisor * 2^4
1 < 2 // break loop
輸出商數： 48 = 0b00110000
```
<!-- #### 延伸問題：在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論 -->
<!--
### 測驗 ```6```
2:16:14
spare data structure
memory Linux compaction LWN.net
-->
---
### 測驗 ```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;
}
```
取 ```EXP10``` 為 ```(v > 0x3) << 1```
取 ```EXP11``` 為 ```ret += (v >> 1);```
這測驗題可以將 32 減去 ```__builtin_clz```，即可得到相同輸出。
```v``` 為 ```uint_32_t```，因此有 32 bits，每次步驟皆為檢查左半部：
- 在第 3、4、5 行中，檢查 ```v[31:16]```：
如果 ```v > 0xFFFFU```，表示在 ```v[31:16]``` 至少有一位元為 1。因此此時 ```ret |= m``` 上記錄 16，表示需要 16 個 bits。
- 在第 6、7、8 行中，檢查 ```v[31:24]```：因為在第 5 行中已經位移，因此計算變成 ```v > 0xFFU```
- 同理檢查 ```v[31:28]```、```v[31:30]```
### 測驗 ```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;
}
```
取 ```EXP12``` 為 ...
取 ```EXP13``` 為 ...
取 ```EXP14``` 為 ...
#### 延伸問題：以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
#### 延伸問題：研讀 [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))
```
取 ```MMM``` 為 1
取 ```NNN``` 為 ```MAX_ALIGNMENT - 1```
> 答案參考自 [Github gist zerojiu/MacroMemory.cxx](https://gist.github.com/zerojiu/5673c6c1cbb21408100381b6cfa07fc5)
數學式為：$\lceil x/align \rceil * align$：
若 ```x``` 為 ```0```，則對齊後的結果為 ```0```
若 ```x``` 為 ```1 ~ 16```，則對齊後的結果為 ```16```
若 ```x``` 為 ```17 ~ 32```，則對齊後的結果為 ```32```
##### 寫出 ```ROUND_DOWN``` 巨集
數學式為 $\lfloor x/align \rfloor * align$
若 ```x``` 為 ```0 ~ 15```，則對齊後的結果為 ```0```
若 ```x``` 為 ```16 ~ 31```，則對齊後的結果為 ```16```
若 ```x``` 為 ```32 ~ 47```，則對齊後的結果為 ```32```
無條件捨去 ```0xF``` 的位元數，因此取
```c
#define MAX_ALIGNMENT 16
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
((x) & ~(MAX_ALIGNMENT - 1))
```
#### 延伸問題：在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
在 [/include/linux/align.h](https://github.com/torvalds/linux/blob/a48b0872e69428d3d02994dcfad3519f01def7fa/include/linux/align.h#L8) 具類似的程式碼
```c
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask) __ALIGN_KERNEL_MASK((x), (mask))
```
來自 /includeu/api/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))
```
:::warning
閱讀 Windows APT Warfare 的 PE Header 之中也有對齊的程式碼，我想 ELF format 有相關的程式碼可以參考
:::
---
### 測驗 ```10```
考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值：
其中 ```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))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
取 ```RRR``` 為 ```((__x) + ((__d) >> 1))```
取 ```SSS``` 為 ```((__x) - ((__d) >> 1))```
在一般數學計算中， $\lfloor x / divisor \rfloor$ 屬於無條件捨去小數部分，而 $\lfloor \frac{x + divisor/2 }{divisor} \rfloor$ 屬於四捨五入。
##### 參考的執行結果，```x```、```divisor```為正數：
DIVIDE_ROUND_CLOSEST(x, divisor)，取 ```x``` 為 ```0 ~ 16```， ```divisor``` 為 ```3```
```
DIVIDE_ROUND_CLOSEST(x, divisor)
00 0
01 0
02 1
03 1
04 1
05 2
06 2
07 2
08 3
09 3
10 3
11 4
12 4
13 4
14 5
15 5
16 5
```
測驗題的要求為，被除數捨入至最近的整數數字，在上述只考慮正數的情況中
以 ``` 7 / 3 = 2.3333... ``` 為例，因為 ``` 2.333 < 2.5```，因此捨去 0.333， ```DIVIDE_ROUND_CLOSEST(7, 3)``` 的輸出為 ```2```
以 ``` 8 / 3 = 2.6666... ``` 為例，因為 ``` 2.666 > 2.5```，因此進位，```DIVIDE_ROUND_CLOSEST(8, 3)``` 的輸出為 ```3```
因此取 ```RRR``` 為 ```((__x) + ((__d) >> 1))```
##### 參考的執行結果，```x```為負數、```divisor```為負正數：
DIVIDE_ROUND_CLOSEST(x, divisor)，取 ```x``` 為 ```0 ~ 16```， ```divisor``` 為 ```3```
```
00 0
-01 0
-02 -1
-03 -1
-04 -1
-05 -2
-06 -2
-07 -2
-08 -3
-09 -3
-10 -3
-11 -4
-12 -4
-13 -4
-14 -5
-15 -5
-16 -5
```
以 ``` -7 / 3 = -2.3333... ``` 為例，因為 ``` -2.333 > -2.5```，因此捨去 0.333， ```DIVIDE_ROUND_CLOSEST(7, 3)``` 的輸出為 ```2```
以 ``` -8 / 3 = 2.6666... ``` 為例，因為 ``` -2.666 < -2.5```，因此進位，```DIVIDE_ROUND_CLOSEST(8, 3)``` 的輸出為 ```3```
因此取 ```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))``` ($\lfloor sqrt(x) \rfloor$)
-->
Sign in with Wallet
Connect another wallet