2022q1 Homework3 (quiz3)

# 2022q1 Homework3 (quiz3) contributed by < [haoyu0970624763](https://github.com/haoyu0970624763) > ## 測驗一 * GENMASK(6, 4) 產生 01110000(8位元) * GENMASK(39, 21) 產生 0x000000FFFFE00000 (64 位元) 從上述兩個例子中我們可以發現 GENMASK(high , low)的功能是把 low ~ high 的位元皆設成 1 GENMASK(6, 4) 就是把從右邊開始數 index為 4-6 區間的 bit 設成 1 (index 從 0 開始數) 了解完 GENMASK 在幹麼之後 , 接著探討應該如何實做 ```c #define GENMASK(h, l) (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) ``` `~0UL` 把 0 的位元全部反轉，也就是生成 0xFFFFFFFFFFFFFFFF 由於((~0UL) >> (LEFT)) 右側有一個 & , 所以推斷 ((~0UL) >> (LEFT)) 是空出 high 左側的位元所以 `LEFT` 應為 ((64-1)-h) 也就是 `63-h` 以GENMASK(39, 21) 來說明的話 , ((~0UL) >> (63-h)) 生成 `0x000000FFFFFFFFFF` ((~0UL) >> (l) << (RIGHT)) 應為空出 low 右側的位元所以 RIGHT 應為 `l` 使最右邊 right 個 bit 空出來為 0 以GENMASK(39, 21) 來說明的話 , ((~0UL) >> (l) << (l)) 生成 `0xFFFFFFFFFE00000` 所以 `0x000000FFFFFFFFFF` & `0xFFFFFFFFFE00000` => `0x000000FFFFE00000` 完整程式如下 ```c #define GENMASK(h, l) \ (((~0UL) >> (63-h)) & ((~0UL) >> l << l) ``` ### linux kernel 中的 GENMASK(h, l) * 在 linux kernel v5.16.12 中的 `isst.h` 中的 GENMASK(h, l) 如下 ```c #define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (sizeof(long) * 8 - 1 - (h)))) ``` **我認為這是考量到並不是每個處理器的 unsigned long 都是 64位元 , 應該考量在不同處理器的情況** * 在 linux kernel v5.16.12 中的 `bits.h` 中也可以發現 GENMASK(h, l) 的 code ```c #define GENMASK(h, l) (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l)) ``` 首先先來看 `GENMASK_INPUT_CHECK(h , l)` ```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 ``` 搭配`BUILD_BUG_ON_ZERO` 來看 `GENMASK_INPUT_CHECK(h , l)` ```c #ifdef __CHECKER__ #define BUILD_BUG_ON_ZERO(e) (0) #else /* __CHECKER__ */ /* * 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)); }))) #endif /* __CHECKER__ */ ``` **簡單來說就是限制 input 中的 h 必須大於 l , 否則會造成 compilation error** GENMASK_INPUT_CHECK(h, l) 必然等於 0 不然會 compile 錯誤也就是說 `GENMASK(h, l)` 等價於 `__GENMASK(h, l)` 接著來看 `__GENMASK(h, l)` ```c #define __GENMASK(h, l) \ (((~UL(0)) - (UL(1) << (l)) + 1) & (~UL(0) >> (BITS_PER_LONG - 1 - (h)))) ``` v5.16.12 中的 `isst.h` 中的程式片段 `(~0UL >> (sizeof(long) * 8 - 1 - (h)))` 完全等價於 `(~UL(0) >> (BITS_PER_LONG - 1 - (h)))` 也就是 **sizeof(long) * 8 = BITS_PER_LONG** **考量到不同處理器對於 long 型別所佔的位元數** 至於另一段表達 `((~UL(0)) - (UL(1) << (l)) + 1))`則是等價於 `((~0UL) << (l))` 想要用從 `((~UL(0)) - (UL(1) << (l)) + 1))` 理解有點難以理解所以我們從 `((~0UL) << (l))` 理解 `((~0UL) << (l))` 可以理解成 Unsigned_max 減掉 $2^0$+$2^1$+...+$2^{h-1}$ 也就是總共減掉 $2^h$-1 而 `((~UL(0)) - (UL(1) << (l)) + 1))` 即 Unsigned_max - $2^h$ -1 **我們可以發現在 linux kernel v5.16.12 中的 `bits.h` 中的 `GENMASK(h, l)` 不僅考量到 input 的限制(h比l大) 且有考量到不同處理器對於 long 所佔的位元數不同** ## 測驗二 ```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?type=view)**描述，對 4 個位元組進行向下對齊** (即 C++ Boost 描述的 align_down) 對 4 個位元組進行向下對齊 => ` v & ~3` 把最後兩個位元清理掉 , 來保證該位址一定為 4 的倍數，做到向下對齊由於 struct fd 中的第一個變數為指向 struct foo 的指標所以 EXP1 為 `(v & ~3)` 將傳進來的位址向下對齊後 , 在轉型成 `(struct foo *)(v & ~3)` 正確 code 如下 ```c= static inline struct fd to_fd(unsigned long v) { return (struct fd){(struct foo *)(v & ~3), v & 3}; } ``` ## 測驗三說明可參照 [Leetcode190 - 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; } ``` 帶入例子思考設 x 的 8bits 為 $abcdefgh$ 這八個英文字母為變數 , 並非 16進制的值最終結果是 $hgfedcba$ 在 $x = (x >> 4) | (x << 4)$ 執行之後 , x 為 $efghabcd$ 而 `(x & 0xCC) >> 2)` 執行結果為 $00ef00ab$ 我們可以推論 $x = ((x & 0xCC) >> 2) | (EXP2)$ 這個結果不會遺失任何的變數 , 所以判斷 `EXP2` 為 `(x&0x33) << 2` 因此這行的執行結果為 $ghefcdab$ 而 `(x & 0xAA) >> 1)` 執行結果為 $0g0e0c0a$ 我們可以推論 $x = ((x & 0xAA) >> 1) | (EXP3)$ 這個結果不會遺失任何的變數 , 並且依據結果判斷 `EXP3` 為 `(x&0x55) << 1` 所以完整程式如下 ```c #include <stdint.h> uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); return x; } ``` ### 延伸問題在 [linux/lib/bitrev.c](https://github.com/torvalds/linux/blob/master/lib/bitrev.c) 中我們可以發現反轉 8 bits 更快的實做方法 , 也就是查表法,因為 8 bit 無號數的範圍在 0-255區間,僅有 256 種可能，可以直接建立查詢表在裡面,用記憶體空間換取快速的處理時間 ```c const u8 byte_rev_table[256] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, }; ``` 有了 8 bits 的反轉 , 就可以用相同的邏輯推敲 16 bits 的反轉或 32 位元的反轉的程式也可以視為把 32位元視為 16位元的反轉兩次的延伸 16 位元視為 8位元反轉兩次的延伸以下為 32位元的反轉 code ```c #include <stdint.h> uint32_t func(uint32_t x) { uint32_t n = x; n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } ``` ## 測驗五先附上題目給的詳解詳情可參照 [Leetcode-29 Divide Two Number](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 > (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; } ``` **15-17 行的部份** $dvs << shift$ 等價於 $dvs*2^{shift}$ 所以 $dvd > (dvs << shift)$ 可視為 $dvd > dvs*2^{shift}$ 又可整理成 $dvd/dvs > 2^{shift}$ 帶例子進去解釋的話設 $dvd=15 , dvs=3$ 用這方法可以求出 $shift=3$ 此時的 $shift$ 表示最大的位移量 , 也就是 $dvs * 2^{shift}$ 會超過 $dvd$ , 因此商的判斷不可能會超越位移 $shift$ 格 **19-25 行的部份** 先判斷 $dvd$ 是否比 $dvs$ 大 , 是的話要繼續運算如果 $dvd < dvs*2^{shift}$ , 則刪減 shift 的值直到 $dvd >= dvs*2^{shift}$ 為止 , 此時結果( 變數 $res$ ) 加上 shift 值這個步驟用意是找出一個最大的 2的冪次方小於 $dvd$ , 商數要加上此 2 的冪次方 , 並且化簡此除法 ### 修改版本修改 6跟11行 , 把乘上 (-1) 換成 ~signal + 1 , 使程式更具一致性上述的 code 在 27-29 行的地方 , 唯一會使結果超過 INT_MAX 的只有在 $dividend$ = INT_MIN 且 $divisor$ = -1 時所以我們特別把這個 case 移到最前面判斷 , 如果是這個 case , 可以直接回傳 INT_MAX , 不需要經過冗長的計算新增部份： 28-33行 , 由於電腦2進位的特性 , 當除數剛好是 $2^{k}$ 的形式時 , 可以不需要透過減法運算等方式 , 直接把被除數往右位移 K 位即為答案判斷是否為 $2^{k}$ 的形式 , 用到上禮拜 [quiz2](https://hackmd.io/evE1-LKqRJCY3LzudBQILA) 中 , Linux kernel 中的 gcd 實做方法的程式片段 ```c= #include <limits.h> int divide(int dividend, int divisor) { /* deal with the only case may overflow */ if (dividend == INT_MIN && divisor == -1) { return INT_MAX; } /* signal variable is to check the operation is plus or minus sign*/ int signal = 1; unsigned int dvd = dividend; /* if dvd is negative , then deal with signal first * then correct the unsigned variable dvd to right value * the way to deal with divisor is same as the dividend * Use ~signal+1 to replace signal *(-1) */ if (dividend < 0) { signal = ~signal + 1; dvd = ~dvd + 1; } unsigned int dvs = divisor; if (divisor < 0) { signal = ~signal + 1; dvs = ~dvs + 1; } /* Use faster way to deal with all of case , * which divisor is the pattern of 2^k */ unsigned int special_case = divisor; int power_of_two = __builtin_ctz(special_case); special_case = special_case >> power_of_two; if (special_case == 1) { return signal * (dvd >> power_of_two); } /* find the maximum value of shift*/ 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; } return res * signal; } ``` ## 測驗七 ```c= int ilog32(uint32_t v) { // if v is zero , bits are all zero , there is nothing can be stored 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; } ``` 程式 4-6 行代表: * 如果 input > 0xFFU , 則表示 input 至少是 0x00000100 ,也就是說需要扣除最前面的 0的話 , 至少會儲存 16個 bits,接著原本的input 可以向右 shift 16個位 , ret 為結果 , 結果+ 16 * 如果 input <＝ 0xFFFFU , 則上述不成立 , m=0 , input 不變 , ret 不變程式 7-9 行代表: * 如果 input > 0xFFU , 則表示現在的 input 至少是 0x00000100 ,也就是說需要扣除最前面的 0的話 , 至少會儲存8個 bits,接著原本的input 可以向右 shift 8個位 , ret 為結果 , 結果+8 * 如果 input <＝ 0xFFU , 則上述不成立 , m=0 , input 不變 , ret 不變 10-12行同樣的邏輯,依此類推 13-15行相同的邏輯可推論 EXP10 is `(v > 0x3) << 1` 16行用相同的邏輯可推敲應為 ```c m = (v > 0x1) << 0; v >>= m; ret |= m; ``` 而這可以直接簡化為 `ret |= v > 1` 所以正確的程式如下 ```c int ilog32(uint32_t v) { // if v is zero , bits are all zero , there is nothing can be stored int ret = v > 0; /* if v is greater than 0xFFFFU , then is must be greater or equal than 0x00010000 * it must store at least sixteen number * if v is not greater than 0xFFFFU , then m=0 , ret doesn't change */ int m = (v > 0xFFFFU) << 4; v >>= m; ret |= m; /* 12-14 code have same logic with code 8-10 */ 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; } ``` ## 測驗八以下為原始提供的 code ```cpp= 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 過於冗長，我們可善用 indirect pointer 改寫 code如下 ```cpp= 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 蠻簡單即可判斷為 `p = &((*p)->left)` 最簡單的形式為 `p = &(*p)->left` EXP12 蠻簡單即可判斷為 `p = &((*p)->right)` 最簡單的形式為 `p = &(*p)->right` 原始程式 27-33 行的意思為如果要刪除的節點沒有左兒子的情況 * 如果要刪除的節點是 root * 直接把 tree 的 root 設成原 root 的右兒子 , 也就是把要刪除節點的右兒子取代要刪除節點的位置使其符合 BST 之特性 * 如果要刪除的節點不是 root * 如果要刪除的節點是其父節點的左子點 , 把要刪除節點的右兒子取代要刪除節點的位置使其符合 BST 之特性 * 如果要刪除的節點是其父節點的右子點 , 把要刪除節點的右兒子取代要刪除節點的位置使其符合 BST 之特性而上述這一段程式我們可以發現其共通點為: 把要刪除節點的右兒子位置取代要刪除節點的位置可對應到改寫的程式 14-15行把要刪除的節點原本指向的位址改成指向,要刪除節點的右兒子的位址原始程式 34-40 行的意思為如果要刪除的節點沒有右兒子的情況 * 如果要刪除的節點是 root * 直接把 tree 的 root 設成原 root 的左兒子 , 也就是把要刪除節點的右兒子取代要刪除節點的位置使其符合 BST 之特性 * 如果要刪除的節點不是 root * 如果要刪除的節點是其父節點的左子點 , 把要刪除節點的左兒子取代要刪除節點的位置使其符合 BST 之特性 * 如果要刪除的節點是其父節點的右子點 , 把要刪除節點的左兒子取代要刪除節點的位置使其符合 BST 之特性而上述這一段程式我們可以發現其共通點為: 把要刪除節點的左兒子位置取代要刪除節點的位置可對應到改寫的程式 16-17行把要刪除的節點原本指向的位址改成指向,要刪除節點的左兒子的位址原始程式 41-53 行的意思為如果要刪除的節點有左兒子也有右兒子的情況 * 一種狀況是取要刪除之節點的左子樹最大值 * 一種狀況是取要刪除之節點的右子樹最小值從 42-57行 , 可以判斷出其是要用右子樹的最小值取代被刪除的節點 * 右子樹最小值恰為被刪除節點的右子樹 , 把右子樹最小值的右子點接到被刪除節點的右子樹 * 如果不是上面的情況 , 則是把右子樹最小值的右子點 , 接到原本右子樹最小值的位置可以發現上面的共通點都是把右子樹最小值的右子點 , 接到原本右子樹最小值的位址可對應到改寫的程式 18-25行並且我們可以判斷出 EXP14= `r = &(*r)->left` 正確 code 如下 ```cpp 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; } ``` ## 測驗九 ```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)) ``` 從上述的 code 可看出尾數介於 1-15 的都需要進行 round up 至 16 , 我們以下僅針對尾數進行討論 (x) + MAX_ALIGNMENT 使得尾數 1-15　變成尾數 17-31 , 而原本尾數是 1 的應該調整成尾數是 16 , 所以判斷 `MMM 應為 1` 所以 ((x) + MAX_ALIGNMENT - 1) 把尾數調整成 16-30 而調整後 16-30 區間我們應該將其都調整為 16 如果是 32 位元可藉由 `&(0xFFFFFFF0)` 可以達成也就是 & ~(15) , 所以 NNN= `MAX_ALIGNMENT-1` 正確的 code 如下 ```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)) ``` ## 測驗十如果看不懂 typeof 可以參照 [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick?type=view#%E5%96%84%E7%94%A8-GNU-extension-%E7%9A%84-typeof) ```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)); \ }) ``` 考量到巨集無法判斷 input 的 type , 所以我們必須檢查 input 的型別整數會有兩種型別 * 無號數 * 有號數無號數 / 無號數 => 無號數無號數 / 有號數 => 無號數有號數 / 無號數 => 無號數有號數 / 有號數 => 有號數 `(typeof(x)) - 1) > 0 ` 是用來檢查此型別是有號數還是無號數若是有任一個 input 為無號數 , 則整個除法最後的結果視為無號數要讓 `(((typeof(x)) - 1) > 0 || ((typeof(divisor)) - 1) > 0 || \ (((__x) > 0) == ((__d) > 0))) ` 這個判斷式為真, 以下兩種情況任一為真即可 * 有任一個 input 為無號數 * x 為有號數且 y 為有號數且兩者皆大於 0 如果是第二種情況 , 其實也可把 x , y 視為無號數 , 因為以正數來說 , 有號跟無號沒有差異因此 , `((RRR) / (__d))` 即為 2 正數之間的除法如果 a / b , 後面的小數大於 0.5 則要進位 , 否則不須進位 C 的除法是無條件捨去的形式 , 所以我們可以概念式的將最後的結果先 + 上 0.5 , 如果原本後面的小數 > 0.5 則會進位 , 原本後面的小數 < 0.5 即使 + 0.5 也是會被捨棄而上述的方式我們可以透過 $(a+(b>>1)) / b$ 所以 RRR 為 `(__x) + ((__d) >> 1)` `(((typeof(x)) - 1) > 0 || ((typeof(divisor)) - 1) > 0 || \ (((__x) > 0) == ((__d) > 0))) ` 這個判斷式為假的情況只會有一個 , 即 x 跟 d 皆有號數 , 且 x 為負數 (d為負數未定義) 跟上面同一個邏輯 , 不過負號的進位是向下進位 , 所以要概念式的將最後的結果先 - 0.5 所以 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))) \ ? (((__x) + ((__d) >> 1)) / (__d)) \ : (((__x) - ((__d) >> 1)) / (__d)); \ }) ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.