---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `StevenChou499` >
* [作業需求](https://hackmd.io/@sysprog/BybKYf5xc)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz2#2022q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
---
## 測驗 `1`
> 考慮以下對二個無號整數取平均值的程式碼:
> ```c=
> #include <stdint.h>
> uint32_t average(uint32_t a, uint32_t b)
> {
> return (a >> 1) + (b >> 1) + (EXP1);
> }
> ```
> 我們再次改寫為以下等價的實作:
> ```c=
> uint32_t average(uint32_t a, uint32_t b)
> {
> return (EXP2) + ((EXP3) >> 1);
> }
> ```
### 思考與想法
題目中的第一題因為想到要做平均，所以應該要用 `>>` 來做除以二的動作。但是因為再二進位制中，若兩數的同一位皆為 `1` 則需要進位，而只有 `&` 可以提取出兩數同時出現的 `1` ，因此 `EXP1` 應該是 `a & b` 才對。
而下一題的在再次改寫，因為後面有一個 `>> 1` ，應該是除以二的結果，而如果 `a` 與 `b` 皆需要除以二，應該以 `^` 的方式提取兩者各單獨擁有的位元，再使用 `&` 來找出兩者共同擁有的位元，而因為＼兩者皆擁有此位元，所以不需要進行除以二的動作。所以 `EXP2` 為 `a & b` ，且 `EXP3` 為 `a ^ b` 。
:::success
EXP1 : a & b
EXP2 : a & b
EXP3 : a ^ b
:::
### 延伸問題
> 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
> 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
## 測驗 `2`
> 改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
> ```c=
> #include <stdint.h>
> uint32_t max(uint32_t a, uint32_t b)
> {
> return a ^ ((EXP4) & -(EXP5));
> }
> ```
### 思考與想法
因為答案需要回傳 `a` 或是 `b` ，所以首先想到的是若要回傳 `a` 則需要利用 `^` 的特性，也就是任何數值在與 `0` 做 `EXR` 後，還會是自己本身。因此我們可以知道 `((EXP4) & -(EXP5))` 等於 `0` 。而若是需要回傳 `b` ，則可以想到 `b` 在與 `a` 做兩次 `^` 後又會回到 `b` ，因此若需要回傳 `b` ，則 `((EXP4) & -(EXP5))` 等於 `a ^ b` ，以下為兩種結果的表格：
| 情況 | a > b (回傳a) | a < b (回傳b) |
|:------------------:|:-------------:|:-------------:|
| ((EXP4) & -(EXP5)) | 0 | a ^ b |
---
而因為需要回傳 `0` 或是 `a ^ b` 且中間還需要做 `&` 的操作，因此 `(EXP4)` 應該要等於 `a ^ b` ，且 `-(EXP5)` 在 `a > b` 時應該要等於 `0x0` ，在 `a < b` 時應該要等於 `0xFFFFFFFF` ，也就是 `-1` 。依據這樣的條件，在加上去除加上負號後的轉換， `(EXP5)` 應該要是 `0` 或 `1` ，因此 `(EXP5)` 應該為 `(a < b)` ，此時若 `a > b` ，會回傳 `0` ，加上負號後為 `0` ，與 `a ^ b` 做 `^` 後為 `0` ，而 `a ^ 0` 等於 `a` ，就會回傳 `a` 。若 `a < b` ，會回傳 `1` ，加上負號後為 `0xFFFFFFFF` ，與 `a ^ b` 做 `^` 後為 `a ^ b` ，最後則會回傳 `b`，以下為詳細講述計算過程的表格：
| 情況 | a > b (回傳a) | a < b (回傳b) |
|:--------------------------:|:-------------:|:-------------:|
| a < b | 0 | 1 |
| -(a < b) | 0x0 | 0xFFFFFFFF |
| a ^ b | a ^ b | a ^ b |
| (a ^ b) & -(a < b) | 0 | a ^ b |
| **a ^ (a ^ b) & -(a < b)** | **a** | **b** |
因此我們可以得知 `EXP4` 等於 `a ^ b` ， `EXP5` 等於 `a < b` 。
:::success
EXP4 : a ^ b
EXP5 : a < b
:::
### 延伸問題
## 測驗 `3`
> 考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
> ```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;
> }
> ```
### 思考與想法
因為是要求兩數之最大公因數，因此前面的程式碼:
```c=6
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
此階段為利用 `shift` 紀錄下總共有幾次方的 `2` 兩數可以進行整除，
```c=9
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
```
接著下方的程式碼則是將剩下無法成為公因數的 `2` 去除。
而最後一段的 `do while` 迴圈則可以看出是用來計算最大公因數的[輾轉相除法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)。而[輾轉相除法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)的結束條件為兩數字相等也就是兩者相減為 `0` ，且因為當最後兩數相等時， `do while` 迴圈中會進入 `else` 的流程，此時 `v` 會等於 `0` ，因此 `while` 結束的條件為 `v == 0` ，所以 `COND` 為 `v` ，當 `v` 不為 `0` 時代表還需要進行下一次的[輾轉相除法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，直到 `v` 等於 `0` 為止。而因為最後要回傳兩者之最大公因數，此時之 `u` 為去除二倍數之最大公因數，所以最後還需要再利用一開始求出的 `shift` 乘回算出來的 `u` ，因此 `RET` 為 `u << shift` 。
:::success
COND : v
RET : u << shift
:::
### 延伸問題
## 測驗 `4`
> 改寫的程式碼如下:
> ```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 的特性)。
### 思考與想法
因為變數 `t` 是想要將原數字中二進位最低位的 `1` 保留下來，而由二補數系統(two's complement)的定義，一數字在加上 `-` （負號）並與原本的數相加後，會因為一直進位而變成零，而最一開始進位的位置就是該數在二進位制中最低位的 `1` 。因此 `EXP6` 等於 `bitset & -bitset` ，這樣第一次進位的位置即是兩數同時擁有 `1` 的位置。
```c
6 0110
-6 1010
+ -----------
0 (1)0000
^
-開始進位的位置(同時都擁有1)
```
| 6 | -6 | 6 & -6 |
|:----:|:----:|:------:|
| 0110 | 1010 | 0010 |
:::success
EXP6 : bitset & -bitset
:::
### 延伸問題
## 測驗 `5`
> 以下是 LeetCode 166. 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;
> }
> ```
### 思考與想法
程式碼講解：
因為其程式碼有一定的長度，因此需要經過 `trace code` 再做完整的判斷會比較好。
先從程式開始執行的第24行開始：
```c=24
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;
```
此段是在配置足夠的記憶體來存取在做運算後的小數點，並先將分母以及分子為零的狀況排除。
接著是第55行：
```c=55
long long remainder = n % d;
long long division = n / d;
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
if (remainder == 0)
return result;
```
此段主要是先計算出該數的商數與餘數，接著利用 `sprintf` 將 `division` 存入 `%ld` 再轉成 `char` 存入 `p` 。
第62行：
```c=62
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;
```
此段是將小數點加入 `p` ，再定義一個存放小數的變數 `decimal` ，配置空間後再用 `memset` 轉換其全部內容成 `0` 。
第72行：
```c=72
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
```
此段開始要真正做小數運算的動作，先重新定義 `size` 為 `1333` ，接著定義一個 `heads` 並配置記憶體，在利用 `INIT_LIST_HEAD` ，依序進行初始化。
第77行：
```c=77
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;
}
```
接著利用 `for` 迴圈開始進行計算，透過呼叫 `find` 函式找出是否有相同的 `key` ，若有則回傳他的 `index` ，若無則回傳 `-1` 。
* `find` 函式：
```c=13
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;
}
```
而獲得 `pos` 後，變可以印出小數點的數值，並回傳 `result` 。
第89行：
```c=89
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;
```
若沒有找到相同的 `key` ，則需要將其 `remainder` 與 `i` 記錄下來，並將其存入配置圍成的 `struct list_head*` 中，接著最後兩行是存入當前餘數 `remainder` 的數值至 `q` 與更新 `remainder` 的數值。此處的 `+ '0'` ，其實為加上 `48` ，將餘數算出後型態從 `long long` 轉換至 `char` 。
以下為解釋(以 `remainder = 3, d = 6` 為例)：
```c
(remainder * 10) / d + '0';
3 * 10 / 6 + '0';
30 / 6 + '0';
5 + '0';
5 + 48;
53 = '5'; // 利用 + '0' 將int轉換成char
```
0~9 之ASCII編碼：
| Binary | Decimal | Character |
|:-------:|:-------:|:---------:|
| 0110000 | 48 | 0 |
| 0110001 | 49 | 1 |
| 0110010 | 50 | 2 |
| 0110011 | 51 | 3 |
| 0110100 | 52 | 4 |
| 0110101 | 53 | 5 |
| 0110110 | 54 | 6 |
| 0110111 | 55 | 7 |
| 0111000 | 56 | 8 |
| 0111001 | 57 | 9 |
由上述的運作情況，我們可以知道 `PPP` 為 `pos--` ，因為 `pos` 為記住小數點後不重複的位數，因此當 `pos` 等於零時，代表不重複的小數已經計算完了。而在後面的 `MMM` 與 `EEE` 則分別是 `list_add` 與 `&heads[remainder % size]` 。此處的用意是將餘數與位置放入 `struct list_head` 的結構 `node*` 當中，再利用 `list_add` 加入 `head[remainder % size]` 中。
整個運作上其實為一個雜湊表，透過雜湊表找出循環與非循環的小數。
以下為實際運作的示意圖（以分母為 `90` ，分子為 `102` 為例）：
* 找出第一次運算下的商數以及餘數 (102 / 90 = 1 ... 12)
```c
long long n = numerator; // n = 102
long long d = denominator; // d = 90
long long remainder = n % d; // remainder = 12
long long division = n / d; // division = 1
```
* 將商數存入 `result` 並同時加入小數點
```c
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
// p = result = 1
if (remainder == 0)
return result;
p = result + strlen(result);
*p++ = '.'; // result = 1.
^ ^
result的位置 p的位置
```
* 初始化 `decimal` 並準備存入小數
```c
char *decimal = malloc(size);
memset(decimal, 0, size);
char *q = decimal;
// q = decimal = '000000000000000...'
```
* 建立一雜湊表並初始化
```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 INIT {
rankdir = "LR"
subgraph h1332{
heads1332[label="
{<p1332>prev|<f1332>heads[1332]|<n1332>next}", shape=record, fixedsize=false,width=3]
heads1332:p1332 -> heads1332:f1332
heads1332:n1332 -> heads1332:f1332
}
omit[label = ".\n.\n.\n",shape = none]
subgraph h2{
heads2[label="
{<p2>prev|<f2>heads[2]|<n2>next}", shape=record, fixedsize=false,width=3]
heads2:p2 -> heads2:f2
heads2:n2 -> heads2:f2
}
subgraph h1{
heads1[label="
{<p1>prev|<f1>heads[1]|<n1>next}", shape=record, fixedsize=false,width=3]
heads1:p1 -> heads1:f1
heads1:n1 -> heads1:f1
}
subgraph h0{
heads0[label="
{<p0>prev|<f0>heads[0]|<n0>next}", shape=record, fixedsize=false,width=3]
heads0:p0 -> heads0:f0
heads0:n0 -> heads0:f0
}
}
```
* 進入第一個 `for` 迴圈 (i = 0):
```c
for (int i = 0; remainder; i++) {
int pos = find(heads, size, remainder);
if (pos >= 0) {
while (pos-- > 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;
list_add(&node->link, &heads[remainder % size]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
```
`pos` 回傳為 `-1` ，引此不會進入 `if` 條件式，並且把 `remainder` 與 `i` 加入 `node*` ，並透過 `list_add` 加入 `heads[remainder % size]` ，即為 `heads[12]` 。
```graphviz
digraph INIT {
rankdir = "LR"
subgraph h1332{
heads1332[label="
{<p1332>prev|<f1332>heads[1332]|<n1332>next}", shape=record, fixedsize=false,width=3]
heads1332:p1332 -> heads1332:f1332
heads1332:n1332 -> heads1332:f1332
}
omit1[label = ".\n.\n.\n",shape = none]
subgraph h12{
heads12[label="
{<p12>prev|<f12>heads[12]|<n12>next}", shape=record, fixedsize=false,width=3]
heads12:p12 -> heads12:f12
}
omit[label = ".\n.\n.\n",shape = none]
subgraph h0{
heads0[label="
{<p0>prev|<f0>heads[0]|<n0>next}", shape=record, fixedsize=false,width=3]
heads0:p0 -> heads0:f0
heads0:n0 -> heads0:f0
}
node1[label="{<prev>prev|<node>node|<next>next}|{<index>index = 0|<key>key = 12}", shape = record, width = 1]
heads12:n12 -> node1:n
}
```
加入雜湊表後，接著將餘數記住並加入 `q` 中，並且重新計算下一次的餘數
```c
*q++ = (remainder * 10) / d + '0'; // q = 1
remainder = (remainder * 10) % d; // remainder = 30
```
* 再次進入下一個 `for` 迴圈 (i = 1):
進入 `for` 迴圈後， `pos` 會回傳 `-1` ，接著再次加入 `heads[30]` 中。
```graphviz
digraph INIT {
rankdir = "LR"
subgraph h1332{
heads1332[label="
{<p1332>prev|<f1332>heads[1332]|<n1332>next}", shape=record, fixedsize=false,width=3]
heads1332:p1332 -> heads1332:f1332
heads1332:n1332 -> heads1332:f1332
}
omit2[label = ".\n.\n.\n",shape = none]
subgraph h30{
heads30[label="
{<p30>prev|<f30>heads[30]|<n30>next}", shape=record, fixedsize=false,width=3]
heads30:p30 -> heads30:f30
}
omit1[label = ".\n.\n.\n",shape = none]
subgraph h12{
heads12[label="
{<p12>prev|<f12>heads[12]|<n12>next}", shape=record, fixedsize=false,width=3]
heads12:p12 -> heads12:f12
}
omit[label = ".\n.\n.\n",shape = none]
subgraph h0{
heads0[label="
{<p0>prev|<f0>heads[0]|<n0>next}", shape=record, fixedsize=false,width=3]
heads0:p0 -> heads0:f0
heads0:n0 -> heads0:f0
}
node1[label="{<prev>prev|<node>node|<next>next}|{<index>index = 0|<key>key = 12}", shape = record, width = 1]
node2[label="{<prev>prev|<node>node|<next>next}|{<index>index = 1|<key>key = 30}", shape = record, width = 1]
heads12:n12 -> node1:n
heads30:n30 -> node2:n
}
```
接著再次紀錄商數至 `q` ，並刷新餘數。
```c
*q++ = (remainder * 10) / d + '0'; // q = 1.3
remainder = (remainder * 10) % d; // remainder = 30
```
* 第三次進入 `for` 迴圈(i = 2):
進入 `for` 迴圈後， `find` 函式會進入 `heads[30]` 尋找相同的 `key` ，找到相同的 `key` 後，便會回傳 `1` 給 `pos` 。接著進入 `if` 判斷式，將 `decimal` 的內容複製給 `p` ，因為 `pos` 等於 `1` ，所以只會將 `decimal` 的第一位的 `1` 複製給 `p` ，此時 `result` 為 `1.1` 。加上 `(` 並複製剩下的內容直到遇到 `\0` ，最後在加上 `)\0` 即可回傳。
```c
int pos = find(heads, size, remainder); // pos = 1
if (pos >= 0) {
while (PPP > 0)
*p++ = *decimal++; // result = 1.1
*p++ = '('; // result = 1.1(
while (*decimal != '\0')
*p++ = *decimal++; // result = 1.1(3
*p++ = ')'; // result = 1.1(3)
*p = '\0'; // result = 1.1(3)\0
return result;
```
:::success
PPP : pos--
MMM : list_add
EEE : &heads[remainder % size]
:::
## 測驗 `6`
> \_\_alignof\_\_ 是 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)
> ```
### 思考與想法
其程式碼講解：
先定義一個結構體其中擁有 `char c` 與 `t _h` 。
```c
struct { char c; t _h; }
```
再將其結構之起始位置設定為 `0` 。
```c
(struct { char c; t _h; } *)0
```
接著找出其結構中元素 `_h` 的位置。
```c
((char *)(&((struct { char c; t _h; } *)0)->M)
```
最後與 `X` 的位置相減。
```c
((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)
```
因為 `__alignof__` 就是計算 `type t` 的長度，所以 `M` 就是需要求的 `_h` ，而 `X` 就是 `0` 。
以 `_h` 是 `int` 為例：
```c
#include <stdio.h>
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
int main(void)
{
printf("%ld\n", ALIGNOF(int));
return 0;
}
```
其結構實際樣貌：
```graphviz
digraph INIT {
rankdir = "LR"
subgraph mem{
memforint[label="
{<m0>char|<m1>|<m2>|<m3>|<m4>int|<m5>int|<m6>int|<m7>int}", shape=record, fixedsize=fasle, width=5]
}
}
```
```c
0:定義結構的起始位置為0
|
v
| | | | | | | | |
{char} { int }
^ ^
| |
0:char的起始位置 4:int的起始位置
```
其執行結果：
:::success
M : _h
X : 0
:::
## 測驗 `7`
> 考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
> * 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
> * 如果是 5 的倍數，印出 “Buzz”
> * 如果是 15 的倍數，印出 “FizzBuzz”
> * 如果都不是，就印出數字本身
>
> 以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: ( `bitwise.c` )
> ```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;
>
> 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"[(9 >> div5) >> (KK3)], length);
> fmt[length] = '\0';
>
> printf(fmt, i);
> printf("\n");
> }
> return 0;
> }
> ```
### 思考與想法
因為題目要求依據各數字是否為 `3` 或 `5` 的倍數去做變化，而若只是 `3` 或是 `5` 的倍數只需要印出 `Fizz` 或是 `Buzz` ，所以我們可以知道 `length` 在皆否的情況下為 `2` ，只為其中一數之倍數為 `4` ，同時為兩數之倍數的話為 `8` ，而剛好 `2 << 1` 等於 `4` 且 `2 << 2` 等於 `8` 。因此我們可以知道 `KK1` 與 `KK2` 分別為 `div3` 和 `div5` ，也可以互換，因為不管先後都會作到 `<<` 的動作。
| 情況 | `3` 的倍數 | `5` 的倍數 | `15` 的倍數 | 皆不是 |
|:---------------:|:----------:|:----------:|:-----------:|:------:|
| `length` 的數值 | 4 | 4 | 8 | 2 |
搞定 `length` 的問題後，後面的 `strncpy` 則是依據不同情況去複製不同位置以及大小之字串。若是 `3` 或是同時是 `3` 與 `5` 的倍數，則要從 `0` 的位置開始複製，若是單純 `5` 的倍數，要從 `4` 的位置開始複製，而若兩數皆不是的話則要從 `8` 的位置開始複製。
| 情況 | `3` 的倍數 | `5` 的倍數 | 同時為 `3` 與 `5` 的倍數 | 皆不是 |
|:--------------:|:----------:|:----------:|:------------------------:|:------:|
| 開始複製之位置 | 0 | 4 | 0 | 8 |
```c
strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
```
而因為 `div5` 已經決定好了，所以若是單純為 `5` 的倍數， `9 >> 5` 等於 `4` ，剛好是開始複製的位置，此時 `KK3` 應該要為 `0` 。而若是 `3` 的倍數或是 `15` 的倍數，則需要一直位移直到數值為 `0` ，便可以從起始位置開始複製，所以 `KK3` 應該是 `div3 << 2` ，這樣在單純只為 `3` 的倍數的情況下，也可以讓 `9` 位移 `4` 次，變成 `0` 的結果。
但是當兩數皆不為倍數時，其值為 `9` ，此時只會印出 `u` 的結果，與 `8` 的結果不符，因此 `9` 應該改為 `8` ，這樣不會影響原本推導的結果，又可以讓兩數皆不為倍數的情況下複製並輸出正確的結果。
```c
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
```
:::success
KK1 : div3
KK2 : div5
KK3 : div3 << 2
:::
Sign in with Wallet
Connect another wallet