---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `YiChainLin` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz2)
實驗的 gcc 編譯器版本
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
```
## 測驗1
* 兩數平均數，直觀的作法為直接對兩數相加並除以二
* 考慮相加的兩數在 32 位元無號整數，範圍: 0 ~ 4294967295 ，設定兩數分別為 3000000000
```c
#include <stdio.h>
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
int main(){
uint32_t a = 3000000000;
uint32_t b = 3000000000;
uint32_t sum = average(a, b);
printf("%d\n", sum);
return 0;
}
```
得出的結果為:
```
852516352
```
* 這是可預期的結果，在 `a + b` 的時候造成了 `overflow` 的結果，因此 `a + b` 的值為 `6000000000 - 4294967295 = 1705032705` ，除二後得到 `852516352` 的結果
* 避免 `overflow` 的方式
1. 若我們已知 a, b 數值的大小，可用下方程式避免 `overflow` :
透過較高的數值減去較低的數值可避免
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
2. 透過 bitwise 方式避免 `overflow` 方式
參考 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
* 將兩數個別透過位移運算子( Shift operator )，將二進制數值進行右移或左移
:::info
以 7~10~ = 0111~2~ 為例:
左移 : 0111~2~ << 1 = 1110~2~ = 14~10~
將位元向左移，並在右邊補0，在10進制中等價為乘2
右移 : 0111~2~ >> 1 = 0011~2~ = 3~10~
將位元向右移，並在左邊補0，在10進制中等價為除2
:::
* 因此計算兩數平均為將個別數值進行右移，但是右移的過程會將最右一個位元忽略刪除，所以要先確認兩數在最後一個位元在相加時是否有進位的可能
* 檢查方式將兩數使用 `&` 運算子確認 `a & b` 是否進位，若有進位則為 1 若無則 0
* 最後在與 1 再進行 `&` 運算，若有進位表示在移位時，進位的值不可忽略，要補 1 回去
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
:::success
EXP1 = a & b & 1
:::
以下使用 4 位元的數值進行平均數的舉例
a = 10~10~ = 1010~2~ ， b = 6~10~ = 0110~2~
```
a >> 1 = 0101
b >> 1 = 0011
(a >> 1) + (b >> 1) + (a & b & 1) = 1000 + 0000 = 1000
二進位 二進位
0101 1010
+ 0011 0110
........ & 0001
1000 ........
0000
```
得到的結果為 1000~2~ = 8~10~
3. 透過 bitwise 方式避免 `overflow` 另一種方式
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
:::success
EXP2 = a & b
EXP3 = a ^ b
:::
使用 `XOR` 邏輯運算子可計算出兩數相加的結果，但不進位，所以進位的部分要透過 `AND` 運算子計算在配合右移，因此先思考兩數的相加為:
```
(a ^ b) /*相加但不進位*/
((a & b) << 1) /*計算進位*/
a + b = ((a & b) << 1) + (a ^ b)
因此兩數平均為:
(a + b) >> 1 = (((a & b) << 1) + (a ^ b)) >> 1 (分配律)
= (a & b) + ((a ^ b) >> 1)
```
以下使用 4 位元的數值進行平均數的舉例
a = 10~10~ = 1010~2~ ， b = 6~10~ = 0110~2~
```
a & b = 0011
a ^ b = 1100
(a ^ b) >> 1 = 0110
(a & b) + ((a ^ b) >> 1) = 0010 + 0110 = 1000
二進位 二進位
1010 1010
& 0110 ^ 0110
........ ........
0010 1100
>>1
........
0110
```
得到的結果也為 1000~2~ = 8~10~
## 測驗2
改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
相關對於 `XOR` 運算子讀物: [That XOR Trick](https://florian.github.io/xor-trick/)
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
* 思考方式:
* 利用 `XOR` 運算子 Toggle (切換)特性
* 重複使用 `XOR` 會抵消，舉例來說， `a ^ a ^ b` (交換律)-> `b ^ a ^ a` 為 b 對 a 做了兩次的切換結果會得到 b 自己
* 觀察題目使用 a 做 `XOR` 運算得出 a 或 b
* 要得出 a : a ^ 0 = a
* 要得出 b : a ^ a ^ b = b
* 所以在 `EXP4` 中為 `a ^ b`
* `EXP5` 要能在 `a ^ b` 中得到 0 或 `a ^ b` 的結果
* 利用 1 或 0 的遮罩方式選擇( 1 的遮罩為 1111...，在十進位數值為 -1 )
* `a ^ b` & -1 = `a ^ b`
* `a ^ b` & 0 = `a ^ b`
* 而 -1 或 0 可透過判別式取得 1 或 0 的結果，因此要加上 `-` 將 1 轉 -1
:::success
如何得到 111... 的二進制數值遮罩，在看到題目的引數值為 uint_32 也就是32 位元的無號整數，因此思考到關係運算子( [relational-expression](https://en.wikipedia.org/wiki/Relational_operator)，>、<...) 出來的值為是否為有號或無號的整數
參考[ISO/IEC 9899:1999](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 規格書的 6.5.8 中的第 6 點
>6. Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int.
指出關係運算子得出來 1 或 0 型態為 int ，為有號的整數
所以在題目中的 `a < b` 判別式中得出的 1 或 0 為有號的整數，而在 -1 的二進位表示方式為 111111............ 為 1 的遮罩方式
:::
* 程式運作
以下使用 4 位元的數值進行平均數的舉例
a = 10~10~ = 1010~2~ ， b = 6~10~ = 0110~2~
```
a ^ b = 1010 ^ 0110 = 1100
若 a < b ( ~(a < b) = 1): 若 a > b( ~(a < b) = 0):
二進位 二進位
1100 1100
& 1111 & 0000
........ ........
1100 0000
分別對 a 進行 XOR 運算:
二進位 二進位
1010 1010
^ 1100 ^ 0000
........ ........
0110 <--得到 b 1010 <--得到 a
```
:::success
EXP4 = a ^ b
EXP5 = a < b
:::
* 反過來說，將也可以將題目改寫成使用 b 進行 `XOR` 運算得出較大的值
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return b ^ ((a ^ b) & -(a > b));
}
```
* 延伸問題:針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
不管是在無號數或是有號數，在 `a > b` 中的敘述中就能判斷出兩數的大小，所以在此函式即能判斷出兩數的最大值，因此修改引數的宣告
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
return b ^ ((a ^ b) & -(a > b));
}
```
## 測驗3
考慮以下 64 位元 GCD ([greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), 最大公因數) 求值函式:
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
改寫為以下等價實作:
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (COND);
return RET;
}
```
:::success
COND = v
RET = u << shift
:::
根據 GCD 演算法:
1. If both x and y are 0, $gcd(0,0) = 0$
2. $gcd(x,0) = x$ and $gcd(y,0) = y$ because everything divides $0$.
以下程式碼針對上述兩個條件進行判別:
若其中數值為 0 的情況下，會透過 `OR` 運算子得到另一個非 0 數值
若兩數皆為 0 則也會返回 0 的數值
```c
if (!u || !v) return u | v;
```
3. If x and y are both even, $gcd(x,y) = 2 * gcd({x\over 2},{y\over 2})$ because $2$ is a common divisor. Multiplication with $2$ can be done with bitwise shift operator.
計算兩數擁有共同公因數 2 的數量，在最後輸出的時候，可以透過 shift 的方式簡化計算，直到兩數其中一數不為 2 的倍數(奇數)
```c
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
再來為非偶數的輾轉相除法( GCD )過程
1. 首先先將兩數確保為奇數(因為已經判斷過2的倍數的數量了)，透過 `while` 迴圈消除
```c
while (!(u & 1))
u /= 2;
while (!(v & 1))
v /= 2;
```
* 在傳統的輾轉中，透過兩數不斷的相減取餘數相減的方式，直到其中一邊為 0 ，則另一邊的餘數為最大公因數，以圖中的示例來說最大公因數為 $10 - 8 = 2$
* 程式的執行方式相似:
2. 固定 u 數為較大值(被除數)，v 數為取餘數後的結果，若 v 數較大則進行調整，由 t 進算兩數取餘數的結果 $u$ mod $v$ = $t$ ，u 透過 v 回歸最大值，v 成為新的除數 t，直到餘數為 0 的時候，
* 因此當 v 為餘數 = 0的時候停止 while 迴圈，所以 `COND = v`
```c
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
```
3. 此時的 u (被除數) 即為最大公因數，但是不包含 $2$ 的倍數，因此返回值不為 u，應為 u * (因數 2 的數量)，而數量由 `shift` 變數紀錄
* 因此 `RET = u << shift`
* 延伸問題:在 `x86_64` 上透過 `__builtin_ctz` 改寫 `GCD`，分析對效能的提升
* 可以得知 `__builtin_ctz` 函式用於找出最低位的 1 後面有多少 0 的個數
>Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. [gcc 文件說明](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
* 舉例說明:
```c
int a = 8; /* 0100 */
__builtin_ctz(a) /* 2 ,最低位的 1 後面有兩個 0 */
```
* 運用函式可改寫在尋找 2 的因數
* 改善的部分在於:
* 不以 for 迴圈找尋兩數的 2 的因數的數量，改用 if-else 敘述找出
* 自訂兩變數在用於找出 u 、 v 兩變數 2 的因數數量，並 shift 該個數次數
* 在 do-while 迴圈中，每次皆會更新 v 可能在每一輪餘數中 2 倍數的可能性，將其維持在奇數
* 改寫為下列
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int u_ctz = __builtin_ctz(u);
int v_ctz = __builtin_ctz(v);
int shift = u_ctz < v_ctz ? u_ctz : v_ctz;
u >>= u_ctz;
v >>= v_ctz;
do {
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
* 改寫後使用 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 工具進行分析，分別執行 5 次
* 尚未改寫程式的運行表現
```shell
Performance counter stats for './quiz_w2_3.out' (5 runs):
5,082 cache-misses # 10.399 % of all cache refs ( +- 63.07% )
48,873 cache-references ( +- 3.38% )
819,973 instructions # 0.93 insn per cycle ( +- 0.77% )
879,293 cycles ( +- 3.48% )
0.0005822 +- 0.0000363 seconds time elapsed ( +- 6.24% )
```
* 使用 `__builtin_ctz` 改寫後的程式運行表現
```shell
Performance counter stats for './quiz_w2_3_v2.out' (5 runs):
4,217 cache-misses # 8.505 % of all cache refs ( +- 69.49% )
49,581 cache-references ( +- 1.48% )
814,529 instructions # 0.92 insn per cycle ( +- 0.42% )
885,792 cycles ( +- 3.32% )
0.0004346 +- 0.0000208 seconds time elapsed ( +- 4.78% )
```
* 測試的結果可以看到，在減少了 for 迴圈的使用下，運行的時間提升了約有 30% 的速度(可見 for 迴圈增加了不少運行時間)，並且也減少了在 `cache-misses` 的發生，整體而言使用 `__builtin_ctz` 改寫後程式的運行有較好的改善
## 測驗4
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼:
```c
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
用以改寫的程式碼如下:
```c=
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
>其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 000101b，那 t 就會變成 000001b，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。
:::success
EXP6 = bitset & -bitset
:::
參考這篇文章 : [Find the lowest set bit](https://stackoverflow.com/questions/12247186/find-the-lowest-set-bit)
* 本題要找出數值 bitset 中的最低位元，可透過 2 補數( [two's complement](https://en.wikipedia.org/wiki/Two%27s_complement) )的方式查找
* 以下以用 8 位元的數值做示例
bitset = 01011100~2~
```
bitset = 01011100
-bitset = 10100011 + 00000001 /* 2's complement */
=10100100
01011100 <- bitset
& 10100100 <- -bitset
...........
00000100 <- 最低位元
```
* 透過二補數與原數做 `AND` 運算，找出最低位元的數值
## 測驗5
以下是 [LeetCode 166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作:
```c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
struct rem_node {
int key;
int index;
struct list_head link;
};
static int find(struct list_head *heads, int size, int key)
{
struct rem_node *node;
int hash = key % size;
list_for_each_entry (node, &heads[hash], link) {
if (key == node->key)
return node->index;
}
return -1;
}
char *fractionToDecimal(int numerator, int denominator)
{
int size = 1024;
char *result = malloc(size);
char *p = result;
if (denominator == 0) {
result[0] = '\0';
return result;
}
if (numerator == 0) {
result[0] = '0';
result[1] = '\0';
return result;
}
/* using long long type make sure there has no integer overflow */
long long n = numerator;
long long d = denominator;
/* deal with negtive cases */
if (n < 0)
n = -n;
if (d < 0)
d = -d;
bool sign = (float) numerator / denominator >= 0;
if (!sign)
*p++ = '-';
long long remainder = n % d;
long long division = n / d;
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
if (remainder == 0)
return result;
p = result + strlen(result);
*p++ = '.';
/* Using a map to record all of reminders and their position.
* if the reminder appeared before, which means the repeated loop begin,
*/
char *decimal = malloc(size);
memset(decimal, 0, size);
char *q = decimal;
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
for (int i = 0; remainder; i++) {
int pos = find(heads, size, remainder);
if (pos >= 0) {
while (PPP > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
}
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
MMM(&node->link, EEE);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
```
* 題目主要功能為浮點數的運算方法，也考慮到無限循環小數的運算
* 透過指標、 `hash table` 、 `linked list` 的實作進行
使用 Leecode 中的例子進行 trace: (預期結果 "0.(012)")
```c
int numerator = 4, int denominator = 333;
```
1. 整數的運算，主要存取 `n/d` 所產生的整數值， `4 / 333 = 0` ，透過`sprintf` 函數寫入整數值在 `p` 中，最後透過移位加入 `.` 字元(小數點)
>#include <stdio.h>
int sprintf(char * restrict s,const char * restrict format, ...);
>Description:
>The sprintf function is equivalent to fprintf, except that the output is written into
an array (specified by the argument s) rather than to a stream.
```c
char *p = result;
long long remainder = n % d;
long long division = n / d;
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
p = result + strlen(result);
*p++ = '.';
```
2. 建立空的 `hash table` ，主要用於儲存計算的結果，與循環小數的查找
```c
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
```
```graphviz
digraph graphname {
rankdir = LR;
splines = false;
node[shape = "record"]
ht[label = "Hash table|<m1>head[0]|<m2>head[1]|<m3>head[2]|...|<mn_1>head[1331-1]|<mn>head[1332]"]
}
```
3. 浮點數的運算，建立每一次小數運算值的資料 `struct rem_node *node`
* `key` 為每一輪小數除法的餘數值([模除](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4))
* `index` 為紀錄整個 `for` 迴圈的輪次
* `link` 為 `struct list_head` 結構用於資料的指標連接
```graphviz
digraph graphname {
rankdir = LR;
splines = false;
node[shape = "record"]
new_node[label = "node|key|index|link"]
}
```
* 所以範例 `4 / 333` 中的第一位小數為 `0` ， `remainder` 為 `40` 在 `for` 迴圈的 `i = 0` 的輪次，也就是 `key = 40 index = 0` ，將結果加入到 `hash table` 中
```graphviz
digraph graphname {
rankdir = LR;
splines = false;
node[shape = "record"]
new_node[label = "node|key = 40|index = 0|<l>link"]
ht[label = "Hash table|<m1>head[0]|<m2>head[1]|...|<m41>head[40]|...|<mn_1>head[1331-1]|<mn>head[1332]"]
ht:m41 -> new_node:l
}
```
:::success
MMM = list_add 為加入 `hash table` 的巨集
EEE = &head[remainder % size] 加入的位置在對應模除的位置
(EEE 參考 [laneser(quiz2)同學的開發紀錄](https://hackmd.io/@laneser/linux2022-quiz2))
:::
* 最後將該輪次的商數，也就是 `(remainder * 10) / d` 加入在 `q` 中，但是 `q` 的型態為 `char *` 需要將算出來的商數轉換成字元型態才能加入
* ***注意到後面有*** `+ '0'` 的一個敘述，這是一個將整數轉字元的技巧，觀察其 [ASCII 碼](https://zh.wikipedia.org/wiki/ASCII)就會發現在 `48~57` 區間的顯示字元為 `'0'~'9'` ， 而 `'0'` 所代表的值為 `48`
* `remainder = (remainder * 10) % d;` 更新下一輪的餘數值進行運算，如果 = 0 則表示已除盡
* `q` 每一輪會存取該輪的除法的商值， 以 `4 / 333` 來說經過 3 輪存下了 `0` 、 `1` 、 `2`
```c
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
MMM(&node->link, EEE);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
```
* 因此經過了 `4 / 333` 經過四輪後得到像這樣的 `hash table` :
```graphviz
digraph graphname {
rankdir = LR;
splines = false;
node[shape = "record"]
new_node0[label = "node|key = 4|index = 3|<l>link"]
new_node1[label = "node|key = 67|index = 2|<l>link"]
new_node2[label = "node|key = 40|index = 1|<l>link"]
new_node3[label = "node|key = 4|index = 0|<l>link"]
ht[label = "Hash table|<m1>head[0]|<m2>head[1]|...|<m5>head[4]|...|<m41>head[40]|...|<m68>head[67]|...|<mn>head[1332]"]
ht:m41 -> new_node2:l
ht:m68 -> new_node1:l
ht:m5 -> new_node0:l -> new_node3:l
}
```
* 由於此範例會有循環小數的產生，觀察 `find` 函數，利用 `hash table` 找尋是否會有餘數相同的情況，也就是在 `hash table` 在任意 `head[i]` 中找到有相同 `key` (相同餘數)
* 所以範例中在 `head[4]` 中透過 `list_for_each_entry` 走訪可以得到會有相同的 `key` 發生，因此返回當前的 `index` 值，"返回第一次 `key` 的 `index` 值"，範例中返回 `index = 0`
* ***返回 `index` 值意義在於不重複的循環小數值的數量***，例如:可能會有結果為 `"0.23(45)"` 其中 `2` 、 `3` 不為循環小數，此時在 `find` 的函數值會返回 2
```c
static int find(struct list_head *heads, int size, int key)
{
struct rem_node *node;
int hash = key % size;
list_for_each_entry (node, &heads[hash], link) {
if (key == node->key)
return node->index;
}
return -1;
}
```
* `list_for_each_entry` 對一個 `linked list` 的中，對每一個成員的起始位址進行訪查，所以能得到結構內部的資料
```c
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
```
* 解析循環小數的填入方式:
* 透過 `find` 函數找出不重複的循環小數值的數量，在 3~4 行中進入 `while` 迴圈要填入未循環的小數(商)值
* 加入 '(' 表示循環小數的開始
* 依序填入循環小數的值 (從 `q = decimal` )
* 加入 ')' 表示循環小數的結束
* 最後加入結尾符 `'\0'`
* 以 `4 / 333 ` 的範例中得出的結果為 `"0.(012)"`
:::success
PPP = pos-- 為每一次填入未循環小數就會遞減已填入的數量
:::
```c=
int pos = find(heads, size, remainder);
if (pos >= 0) {
while (PPP > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
}
```
* 延伸問題:指出程式碼不足，並予以改進
* 改寫程式碼
```c
bool sign = (float) numerator / denominator >= 0; /* origin */
bool sign = numerator < 0 ^ denominator < 0 /* improved */
```
* 看到程式碼中使用 `malloc` 配置記憶體，但是卻沒有釋放，因此需要釋放掉整個 `hash table` 所佔的記憶體空間(包含 `head` 與 `node`)
* 所以在計算 while 迴圈中的循環小數的 return 敘述前與程式最後的 return 前加入釋放記憶體的自定義函數
* 利用 `list_for_each_safe` 走訪每一個 heads 中所連結的 node 資料，並將其釋放
* 由於要進行記憶體釋放，所以透過 `cur` 可以記住走訪點的下一個位置，避免發生錯誤，在走訪的過程中較安全(也因此有 safe 敘述)
```c
void free_ht(struct list_head *heads, int size)
{
struct rem_node *node, *cur;
list_for_each_safe (node, cur, heads) {
free(node);
}
free(heads);
}
```
* `list_for_each_safe` 函式，[參考 list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
```c
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; \
!list_is_head(pos, (head)); \
pos = n, n = pos->next)
```
* 在兩個 `return result;` 前加入釋放記憶體的函式
```c
free_ht(heads, size);
return result;
```
## 測驗6
[`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 GNU extension，以下是其可能的實作方式:
```c
/*
* ALIGNOF - get the alignment of a type
* @t: the type to test
*
* This returns a safe alignment for the given type.
*/
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)
```
請補完上述程式碼，使得功能與 [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 等價。
* 程式的目的，傳回變數型態的佔用 `byte` 長度，透過記憶體對齊的方式
* 舉例:
```c
printf("%ld", ALIGNOF(short)); /* 2 */
printf("%ld", ALIGNOF(int)); /* 4 */
```
* 查找的方式(以 int 示例):
* 為了記憶體對齊，所以 char 的宣告長度會與 int 一樣，如下圖
* 在 struct 定義中順序為先宣告 char 再宣告 int
* 由於 int 占了 4 bytes， char 占 1 byte，分配的方式如下圖
* `&((struct { char c; t _h; } *)0)->M)` 在這個敘述中目的要取得 `t` 的記憶體位置，因此 `M` 為 `struct` 結構中 `t` 型態的便數成員，所以 `M = _h`
* 得到了 int 的宣告的起始位置再扣掉 char 的起始位置，也就是單一變數型態的宣告長度，所以 `X = 0` 表示該結構的起始位置(也就是 char 的位置)，計算後就可以得到引數的占用記憶體長度
:::success
M = _h
X = 0
:::
```graphviz
digraph graphname {
rankdir = LR;
node[shape = "record"]
alignment[label = "{char||||int(起始)|int|int|int}", width = 7]
}
```
* 延伸問題:在 Linux 核心原始程式碼中找出 `__alignof__` 的使用案例 2 則，並針對其場景進行解說
* 在 [kernal.h](https://github.com/torvalds/linux/blob/master/include/linux/kernel.h) 中找到兩個函式使用到 `__alignof__`
* 觀察兩個函式會發現主要兩個引數的型態，分別為 `unsigned int` 與 `unsigned long` ，第二個函式分別為 `unsigned int` 與 `long` 主要是將 `unsigned int` 轉換成 `long` 的型態變換
* `if-else` 判斷系統的 `long` 與 `long long` 分配的記憶體長度，進而選擇要對哪一種的型態進行記憶體對齊
* 參考至[Data Model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)，舉例來說如果在 `LP64 model` 下執行，因為 `long` 與 `long long` 都是 `64-bits` 所以會執行 if 的敘述使 `32-bits` 的 `int` 與 `long long` 轉換，並記憶體對齊
* 若是在 `LLP64 model` 則 `long` 與 `long long` 分別為 `32-bits` 與 `64-bits` ，此時會執行 else 敘述，使 `32-bits` 的 `int` 與 `long` 轉換，並記憶體對齊
* 引數中的 `const char *s` 用途與題目的 `char c` 一樣，編譯器會挑選占用較大的記憶體型態進行分配
```c
static inline int __must_check kstrtoul(const char *s, unsigned int base, unsigned long *res)
{
/*
* We want to shortcut function call, but
* __builtin_types_compatible_p(unsigned long, unsigned long long) = 0.
*/
if (sizeof(unsigned long) == sizeof(unsigned long long) &&
__alignof__(unsigned long) == __alignof__(unsigned long long))
return kstrtoull(s, base, (unsigned long long *)res);
else
return _kstrtoul(s, base, res);
}
static inline int __must_check kstrtol(const char *s, unsigned int base, long *res)
{
/*
* We want to shortcut function call, but
* __builtin_types_compatible_p(long, long long) = 0.
*/
if (sizeof(long) == sizeof(long long) &&
__alignof__(long) == __alignof__(long long))
return kstrtoll(s, base, (long long *)res);
else
return _kstrtol(s, base, res);
}
```
## 測驗7
考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3 的倍數，印出 “Fizz”
* 如果是 5 的倍數，印出 “Buzz”
* 如果是 15 的倍數，印出 “FizzBuzz”
* 如果都不是，就印出數字本身
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c):
* 首先先分析 `is_divisible` 函數，功能為判斷是否為被整數 n 整除
* 以本題的 M3 為例創造一個 64 位元的 111..11 遮罩
示例一個整數 6 與 5 判斷，可發現值會有很大的差異
```
6:
6 * ((0xFFFFFFFFFFFFFFFF) / 3 + 1) = 4
5:
5 * ((0xFFFFFFFFFFFFFFFF) / 3 + 1) = -6148914691236517202
```
* 原因是如果是 3 的倍數的話乘回去，會剛好因為 overflow 的特性，所以 6 = 3 * 2 也就是整個補數系統會轉兩圈，所得出來的值為 6 - 2(補了2次的111..11遮罩到 0) = 4
* 因此可以判斷出數值使否能被該數的遮罩技巧整除，能剛好達到意外的效果檢測
```c
static inline bool is_divisible(uint32_t n, uint64_t M)
{
return n * M <= M - 1;
}
static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;
```
* 在 `length` 中要決定字串的長度，最多為 8 ，所以要讓 `length` 達到 8 的可能為 2 shift 2 次，也就是若 `div3` 與 `div5` 都返回 `bool` 的 1 就可以決定要顯示多少長度的字串，分別為 2 (印出數字本身) 、 4 (Fizz 或 buzz) 、 8 (Fizzbuzz)
:::success
兩者個結果可交換，不管是否為 3 或 5 的倍數，都透過 `is_divisible` 函式判斷是否要 shift
KK1 = div3
KK2 = div5
:::
* 再來就是決定要印出的位置
* 可以看到 `8 >> div5` 若 `div5 = 1` 則會等於 4 會從 [4] 的位置開始印，若 `div5 = 0` 則會從 [8] 的位置開始印 "%u" 也就是原始數字
* 所以要從第 [0] 的位置開始印的話，必須把 8 透過 shift ， 變成 0，所以 8 要至少要 shift 4 次，才能將 8 變成 0
* KK3 要能等於 4 由 div3 決定，也就是 `div3 = 1` 可透過左移 2 位得到 4
:::success
KK3 = div3 << 2
:::
```c=
int main(int argc, char **argv)
{
for (size_t i = 1; i <= 100; i++) {
uint8_t div3 = is_divisible(i, M3);
uint8_t div5 = is_divisible(i, M5);
unsigned int length = (2 << KK1) << KK2;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
:::info
在下列程式碼中第 9 行考慮到字串的位置 F 的位置是 [0] 、B的位置是 [4]、%的位置是 [8]，要印出數字應該要是 "%u" 要從第 [8] 的位置印出
原程式碼為 9 會從 "u" 開始印，則會顯示不出原始數字
:::
## 參考文獻
* [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)
* [ISO/IEC 9899:1999](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf)
* [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick?type=view#%E5%96%84%E7%94%A8-GNU-extension-%E7%9A%84-typeof)
Sign in with Wallet
Connect another wallet