# 2022q1 Homework2 (quiz2)
contributed by < [Nomad1230](https://github.com/Nomad1230) >
## 測驗 `1`
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
此函式的目的是要計算無號整數的平均值，觀察其回傳值 `(a >> 1)` 及 `(b >> 1)` 其實就是 `a / 2` 跟 `b / 2` 的意思，最後再加上 `EXP1` 就是答案，而 `EXP1` 就是要檢查 `a` 跟 `b` 的最後一個位元相加後有沒有產生進位，若有進位則要將其補回。
| a:0 | b:0 | result |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
觀察上方表格， `a:0 & b:0` 可以得到我們要的結果，因此 `EXP1` 應為 `a & b` 再加上 `& 1` 取最後一個位元，答案為 `a & b & 1` 。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
題目提示 `EXP2` 及 `EXP3` 為 `a` 和 `b` 的表示式，且只能使用 OR, AND, XOR 運算子。
可以發現這段程式碼很類似:
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
因此可以推斷 `EXP3` 應為 `a` 和 `b` 的"差距"，故先假設 `EXP3` 為 `a ^ b` ，觀察以下例子:
```graphviz
digraph struct {
label = "a"
node [shape = record]
num1 [label = "1|0|0|1"]
}
```
```graphviz
digraph struct {
label = "b"
node [shape = record]
num2 [label = "0|1|0|1"]
}
```
```graphviz
digraph struct {
label = "a ^ b"
node [shape = record]
num1 [label = "1|1"] [fontcolor = red]
num2 [label = "0|0"]
}
```
`a ^ b` 會把 `a` 和 `b` 間不一樣的 bit 設為 1 ，右移一位後再加上 `EXP2` 就會是我們要的答案，這時憑直覺判斷 `EXP2` 會是 `a` 和 `b` 相同的 bit ，推測 `EXP2` 為 `a & b` ，再進行檢驗。
```graphviz
digraph struct {
label = "a & b"
node [shape = record]
num1 [label = "0|0"]
num2 [label = "1|1"] [fontcolor = red]
}
```
```graphviz
digraph struct {
label = "a ^ b"
node [shape = record]
num1 [label = "1|1"] [fontcolor = red]
num2 [label = "0|0"]
}
```
確實 `0011` + `0110` = `1001` 為答案，以上假設成立。
### 延伸問題
#### 使用最佳化編譯觀察其組合語言
編譯指令: `gcc -S -O3 average.c`
其中 `-S` 是輸出組合語言的檔案形式，可以用文字編輯器查看，`-O3` 的意思是開啟最高等級的最佳化， gcc 有 4 個等級的優化模式 `-O0` 為關閉優化， `-O1` ~ `-O3` 為等級最低到最高。
#### (a + b) / 2
```c
uint32_t average1(uint32_t a, uint32_t b)
a in %rcx, b in %rdx
average1:
.seh_endprologue
1) leal (%rcx,%rdx), %eax
2) shrl %eax
3) ret
```
第一個指令是 `leal` ，這邊參考了<[How does leal instruction work?](https://stackoverflow.com/questions/19760290/how-does-leal-instruction-work)>這篇文章。
`leal` 本身的作用是取記憶體位置並存入指定暫存器，但其也可以用在整數的加法或乘法上，因為地址本身也是用整數表示。
例如此處就把 `rcx` 跟 `rdx` 當成了地址，而 `leal` 會把括號內的數值相加，因此第一行最後呈現的結果會是 `eax = rcx + rdx` 。
第二行就很簡單了，就是把 `eax` 右移一個 bit 。
最後回傳 `eax`
不過上述其實有一個很奇怪的地方，我查閱 CS:APP 第三章時，書上有寫到 `rdx` 跟 `rcx` 理應是用來儲存第三個跟第四個參數的，第一個及第二個參數的暫存器應為 `rdi` 跟 `rsi` ，這讓我蠻疑惑的。
另外這邊使用的是 `rdx` 跟 `rcx` ，這兩個暫存器都是 64 位元大小，但其他 3 個函式編譯完都是用 32 位元大小的暫存器來儲存，推測是因為要使用 `leal` 才會這樣安排?
#### low + (high - low) / 2
```c
uint32_t average2(uint32_t low, uint32_t high)
low in %ecx, high in %edx
average2:
.seh_endprologue
1) movl %edx, %eax
2) subl %ecx, %eax
3) shrl %eax
4) addl %ecx, %eax
5) ret
```
1.把 `edx` 存入 `eax`
2.`eax` -= `ecx`
3.`eax` 右移一個 bit
4.`eax` += `ecx`
5.回傳 `eax`
蠻直觀的，就不贅述。
#### (a >> 1) + (b >> 1) + (a & b & 1)
```c
uint32_t average3(uint32_t a, uint32_t b)
a in %ecx, b in %edx
average3:
.seh_endprologue
1) movl %ecx, %eax
2) movl %edx, %r8d
3) andl %edx, %ecx
4) shrl %eax
5) shrl %r8d
6) andl $1, %ecx
7) addl %r8d, %eax
8) addl %ecx, %eax
9) ret
```
1.`ecx` 存入 `eax`
2.`edx` 存入 `r8d`
3.`ecx` = `edx & ecx`
4.`eax` 右移一個 bit
5.`rd8` 右移一個 bit
6.`ecx` = `1 & ecx`
7.`eax` += `r8d`
8.`eax` += `ecx`
9.回傳 `eax`
一樣不贅述。
#### (a & b) + ((a ^ b) >> 1)
```c
uint32_t average4(uint32_t a, uint32_t b)
average4:
.seh_endprologue
1) movl %ecx, %eax
2) andl %edx, %ecx
3) xorl %edx, %eax
4) shrl %eax
5) addl %ecx, %eax
6) ret
```
1.`ecx` 存入 `eax`
2.`ecx` = `edx & ecx`
3.`eax` = `edx ^ eax`
4.`eax` 右移一個 bit
5.`eax` += `ecx`
6.回傳 `eax`
#### 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)
在 `average.h` 中程式碼實作了 EWMA (Exponentially weighted moving average) ，在研究其程式碼之前，先來搞懂這樣的實作有何應用，首先先理解何謂 moving average ?在此我從網上找到了一篇股票分析的文章<[一文看懂移動平均線(Moving Average)及其運用策略](https://www.dailyfxasia.com/cn/feaarticle/20190222-6337.html)>。
文章中提到 moving average 是一套分析資料走向的算法，可以看到文中的範例圖:
其計算了 20 日內的平均線以及 50 日內的平均線，當 20 日的平均線有往上走的趨勢並與 50 日平均線交叉，就可以推測其在短期內股票會有上漲的趨勢。
而 EWMA 就是用來計算平均線的一套算法，其定義如下:
其中 St 是時間為 t 時所計算出的平均值， Yt 是時間為 t 時實際取得的資料， α 是時間的權重， α 越大代表舊資料的重要性越低。
以剛才提到的股票為例子， 20 日平均線就是以 20 天前的資料為 Y0 ，然後計算出 S(20) 的值畫在圖上，把每一天計算出的 S(20) 都連接起來就會是 20 日平均線。
理解完其原理後來研究其程式碼:
```c
#define DECLARE_EWMA(name, _precision, _weight_rcp)
```
可以看到此巨集中有三個參數， `name` 為自定義的名字， `_precision` 表示要用幾個 bit 來儲存小數點， `_weight_rcp` 用來計算 α 值，其公式為 α = 1/weight_rcp ，且要求 `_weight_rcp` 必須為 2 的冪。
```c
struct ewma_##name {
unsigned long internal;
};
```
`average.h` 中定義的結構體，只儲存一個 `unsigned long` 的變數 `internal` ，此變數就是公式中的 S 值。
```c
static inline void ewma_##name##_init(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
/* \
* Even if you want to feed it just 0/1 you should have \
* some bits for the non-fractional part... \
*/ \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
e->internal = 0; \
}
```
此函式用來把結構體中儲存的資料歸 0 ，可以看到前面有幾行 `BUILD_BUG_ON` 的函式，這幾個函式會在編譯時期檢查括號內的 condition 若 condition 成立則會報錯，用來提早檢查參數有沒有符合條件。
這邊要求的條件有 4 個，第一個為 `!__builtin_constant_p(_precision)` ，此為 gcc 內建的函式，若在編譯時期就能確定參數值就回傳 1 ，否則 0 ，因此前兩個條件在於確保 `_precison` 及 `_weight_rcp` 不為常數。
第三個條件是 `_precision` 不大於 30 ，最後一個條件為 `_weight_rcp` 須為 2 的冪。
```c
static inline unsigned long
ewma_##name##_read(struct ewma_##name *e)
{
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
return e->internal >> (_precision);
}
```
此函式用來讀取結構體儲存的 `internal` 變數並回傳。
```c
static inline void ewma_##name##_add(struct ewma_##name *e,
unsigned long val)
{
unsigned long internal = READ_ONCE(e->internal);
unsigned long weight_rcp = ilog2(_weight_rcp);
unsigned long precision = _precision;
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
WRITE_ONCE(e->internal, internal ?
(((internal << weight_rcp) - internal) +
(val << precision)) >> weight_rcp :
(val << precision));
}
```
此函式的功能為使用公式計算 `internal` 的值，參數 `*e` 儲存前一次計算的 S 值、 `val` 為當前的資料。
其中在讀取跟寫入資料時使用 `READ_ONCE` 跟 `WRITE_ONCE` 避免 multi-thread 出現問題，且將 `_weight_rcp` 取 log2 ，這樣在計算時只要使用 shift operater 就可以了，以增進程式效能，這也是為什麼一開始要求 `_weight_rcp` 為 2 的冪。
可以發現此函式只計算一次 Ｓ 值，若是要從 S(0) 算到 S(20) 就要重複呼叫此函式 20 次，因為每次都要把新的 val 輸入進來。
---
## 測驗 `2`
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
題目給定條件:
1.`EXP4 `為 `a` 和 `b` 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。
2.`EXP5` 為 `a` 和 `b` 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, != 這 6 個運算子。
此函式的功用是比較 `a` 和 `b` 的大小並回傳較大的數，可以看到回傳值為 `a ^ ((EXP4) & -(EXP5))` ，其中 `((EXP4) & -(EXP5))` 和 `a` 作 XOR 的預期輸出為 `a` 或 `b` ，因此推斷 `EXP4` 跟 `a` 作 XOR 後會輸出 `b` ， 而 `EXP5` 是判斷 `a` 和 `b` 的大小。
因為 `a ^ 0 = a` ，所以當 `a >= b` 時 `-(EXP5)` 應為假，故 `EXP5` 為 `a < 0` 。
再來推論 `EXP4` ，預期 `a ^ EXP4 = b` ，故 `EXP4` 應為 `a ^ b` 。
### 延伸問題
#### 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
有號的實作應與無號的相同，因為其思路相同，都是 `a` 較大回傳 `a` ， `b` 較大回傳 `b` ，在 bitwise 的操作上也沒有差異。
#### 在 Linux 核心找出相似 branchless / branch-free 的實作
---
## 測驗 `3`
```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;
}
```
此函式是用輾轉相除法來計算最大公因數。
簡單解釋一下輾轉相除法，以 252 及 105 兩數為例，其最大公因數為 21 ， 當這兩數相減時 252 - 105 = 21 * 12 - 21 * 5 = 21 * 7 = 147 ，可以發現 147 跟 105 的最大公因數也是 21 ，同理只要把兩數一直相減，減到最後餘數為 0 時，此時剩下的不為 0 的數即為最大公因數。
觀察程式碼，可以看到迴圈中 `u` 的值保持大於 `v` ，故輾轉相除法結束時 `v` 值應為 0 ，此時 `u` 值為最大公因數。
因此 `COND` 應為 `v > 0` ，為求精簡寫一個 `v` 就好，而 `RET` 應為 `u` ，但程式一開始便將 2 的公因數全部提出並存為 `shift` ，在回傳之前應把值補上，故 `RET` 為 `u << shift` 。
### 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
`__builtin_ctz(unsigned int x)` 為 gcc 內建的函式，用來計算 `x` 從第一個位元開始有幾個 0 才出現 1 ，例如 `__builtin_ctz(0xFFFFFF00)` 的回傳值為 8 。
此函式可以用來改良上述程式碼中計算 `shift` 的部分，嘗試改良如下:
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int ctz_u, ctz_v;
ctz_u = __builtin_ctz(u);
ctz_v = __builtin_ctz(v);
u >>= ctz_u;
v >>= ctz_v;
do {
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << (ctz_u < ctz_v)? ctz_u : ctz_v;
}
```
在一開始計算 `__builtin_ctz(u)` 跟 `__builtin_ctz(v)` 的值存為 `ctz_u` 及 `ctz_v` ，在最後回傳前將 `u` 左移較小的數。
並且可以將原本用 `while` 迴圈提出 2 的因數的程式碼改成 `v >>= __builtin_ctz(v)` 的寫法。
### 解釋 [gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 實作手法和探討在核心內的應用場景
`gcd.c` 會根據 `__ffs` 有沒有啟用而分成兩種實作手法，有 `__ffs` 的版本會有較好的效率。
#### `__ffs` 版本:
```c=
unsigned long gcd(unsigned long a, unsigned long b)
{
unsigned long r = a | b;
if (!a || !b)
return r;
b >>= __ffs(b);
if (b == 1)
return r & -r;
for (;;) {
a >>= __ffs(a);
if (a == 1)
return r & -r;
if (a == b)
return a << __ffs(r);
if (a < b)
swap(a, b);
a -= b;
}
}
```
先看到第 8 行， `b >>= __ffs(b)` 把 `b` 所有 2 的因數提出，若是提出後 `b == 1` 代表 `b` 為 2 的冪，並會回傳 `r & -r` 。
```c
b >>= __ffs(b);
if (b == 1)
return r & -r;
```
`r & -r` 這個語法的作用是找出 `r` 中最低位元的 1 ， 又程式碼中的 `r = a | b` ，此時 `r` 最低位元的 1 便會是 `a` 和 `b` 的公因數中最大的 2 的冪，若 `b` 為 2 的冪，則此值會為 `a` 和 `b` 的最大公因數。
再來用 `for` 迴圈做輾轉相除法， 14 行判斷 `a` 是否為 2 的冪，若是則回傳 `r & -r` ，16行為輾轉相除法的最後一步，兩值相等時代表此數為最大公因數，回傳前再把 2 的因數乘回來。
`gcd.c` 的實作方式跟我們自己實作的 `gcd64` 最大的不同處有二，首先是多了一個 `r` 的變數來儲存 `a | b` ，這樣的方式可以直接取出公因數中最大的 2 的冪，不用再經過多餘的計算跟條件判斷。
第二個不同之處是優化輾轉相除法，若 `a < b` 就將兩數交換即可，讓程式碼看起來簡潔許多。
#### 無 `__ffs` 版本:
```c=
unsigned long gcd(unsigned long a, unsigned long b)
{
unsigned long r = a | b;
if (!a || !b)
return r;
/* Isolate lsbit of r */
r &= -r;
while (!(b & r))
b >>= 1;
if (b == r)
return r;
for (;;) {
while (!(a & r))
a >>= 1;
if (a == r)
return r;
if (a == b)
return a;
if (a < b)
swap(a, b);
a -= b;
a >>= 1;
if (a & r)
a += b;
a >>= 1;
}
}
```
一開始將 `a` 和 `b` 公因數中最大的 2 的冪提出存為 `r` ，第 11 行的迴圈用來把 `b` 多餘的 2 的因數除掉。
值得注意的是在輾轉相除法的迴圈中多了幾個步驟加快迴圈的進行， `a -= b` 時由於此時 `a` 跟 `b` 必為兩個偶數或兩個奇數，因此 `a -= b` 後 `a` 必為偶數，可以將 `a` 因為相減而多產生的 2 的因數提出，28 行判斷會不會把 2 的因數提過頭，因為 `a & r` 成立時若再把 `a` 右移一位會導致出錯，因此再加一個 `b` 回來，這樣的演算法在數字很大的時候可以減少不少迴圈的次數。
---
## 測驗 `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 的特性)。
`EXP6` 應為 `bitset & -bitset` ，此為利用二補數特性的實作，參考以下例子:
```graphviz
digraph G{
label = "bitset"
node [shape = record]
num1 [label = "1|0|0|1|0|0"]
}
```
```graphviz
digraph G{
label = "~bitset"
node [shape = record]
num2 [label = "0|1|1|0|1|1"]
}
```
```graphviz
digraph G{
label = "-bitset"
node [shape = record]
num1 [label = "0|1|1|1|0|0"]
}
```
可以看到因為 `-bitset == ~bitset + 1` ，原本 `bitset` 中最低位開始連續的 0 在 `~bitset` 會變成連續的 1 ，此時若再加上 1 ，則會一路進位到 `bitset` 中最低位元的 1 的位置，因此 `bitset & -bitset` 可以將最低位元的 1 提出。
### 延伸問題
---
## 測驗 `5`
#### rem_node
```c
struct rem_node {
int key;
int index;
struct list_head link;
};
```
首先看到其結構體，其中儲存了兩個變數， `key` 用來儲存餘數， `index` 用來儲存此資料為小數點後第幾位，這邊會用到 linked list 儲存資料的原因是避免造成循環小數的重複計算。
#### find
```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;
}
```
此函式用來查找 linked list ，注意這邊回傳的是 `index` 而非 `key` ，因為主要是要查找循環小數有幾個數。
#### fractionToDecimal
```c=
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;
}
```
前面為整數部分的計算跟正負號判斷，第 54 行的迴圈才是整個程式的重點，首先迴圈一開始進行查尋 linked list ，若查找成功則代表後面都是循環小數，將其印出後即可回傳結束程式。
因此看到第 57 行的 `PPP` ，此時的 `pos` 為查找到的 `index` ，因此迴圈內的 condition 應為 `pos-- > 0` ，將 `decimal` 儲存的小數位的部分根據 `index` 位數印出到 `result` 中。
第 70 行 `MMM(&node->link, EEE)` 的作用應為把查詢失敗的資料儲存入 hash table 中，因此 `MMM` 應為 `list_add` ，由於查詢 hash table 時應由 `index` 較大的開始查詢，故使用 `list_add` 而非 `list_add_tail` ，而 `EEE` 應為 `&heads[remainder % size]` ， `remainder % size` 為 hash key 。
### 延伸問題
#### 搭配研讀 [The simple math behind decimal-binary conversion algorithms](https://indepth.dev/posts/1019/the-simple-math-behind-decimal-binary-conversion-algorithms)指出其中不足，並予以改進
---
## 測驗 `6`
```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)
```
可以發現這個巨集的實作跟 `container_of` 非常的像，`container_of` 是藉由結構中成員的絕對記憶體位置減掉相對的位移量來取得結構體的絕對位置，在此巨集中也用了記憶體中的絕對位置相減的方式來實作。
`__alignof__` 的功能是計算一個變數型態中 alignment 的大小，其概念與 `sizeof` 很像，詳細可參考 <[What's the difference between sizeof and alignof?](https://stackoverflow.com/questions/11386946/whats-the-difference-between-sizeof-and-alignof)>。
記憶體在分配結構體空間的時候會將結構體切成大小一致的區塊，例如上方連結的文章中有以下舉例:
```cpp
// c has to occupy 8 bytes so that d (whose size is 8) starts on a 8 bytes boundary
// | 8 bytes | | 8 bytes | | 8 bytes |
struct Bad { char c; double d; int i; };
cout << alignof(Bad) << " " << sizeof(Bad) << endl; // 8 24
// | 8 bytes | | 8 bytes |
struct Good { double d; int i; char c; };
cout << alignof(Good) << " " << sizeof(Good) << endl; // 8 16
```
在此舉例中由於 `double` 佔的空間為最大的 8 bytes 所以其 alignment 為 8 ，而 `sizeof` 會根據 alignment 的結果而有所不同，如圖示:
```graphviz
graph G{
label = "bad : total 24 bytes good : total 16 bytes"
subgraph a{
node [shape = record]
struct1 [label = "{{c : 1 byte}|{... : 7 bytes}|{d : 8 bytes}|{i : 4 bytes}|{... : 4 bytes}}"]
}
subgraph b{
label = "good : total 24 bytes"
node [shape = record]
struct2 [label = "{{d : 8 byte}|{i : 4 bytes}|{c : 1 bytes}|{... : 3 bytes}}"]
}
}
```
`__alignof__` 計算方式如下:
1.用一個結構體的指標指向記憶體 0 的位置`(struct { char c; t _h; } *)0` ，結構體中儲存了一個 `char` 型態變數 `c` 及一個 `t` 型態變數 `_h`。
```graphviz
digraph G{
label = "struct"
node [shape = record]
struct1 [label = "{{c}|{...}|{_h}}"]
}
```
2.`(&((struct { char c; t _h; } *)0)->M)`指向其中的 `_h` ，故 `M` 應為 `_h` ，並將指標轉型成 `(char *)` ， `(char *)(&((struct { char c; t _h; } *)0)->M)` ，轉型的原因是 `(char *)` 的大小為 1 byte ，與記憶體中以 1 byte 為單位紀錄位置一致。
```graphviz
digraph G{
node [shape = record]
struct1 [label = "{c}|{...}|{<here>_h}"]
rankdir=LR;
node [color = white]
" " -> struct1:here
}
```
3.將指標減掉結構體的起始位置即可得到 alignment 的大小，因此 `X` 應為 0。
### 延伸問題
---
## 測驗 `7`
```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;
}
```
第 14 行計算輸出字串的長度，因此 `KK1` 及 `KK2` 應為 `div3` 及 `div5` ，這樣在兩個條件都符合的時候剛好長度為 8 ，與 `FizzBuzz` 一致。
第 17 行要決定輸出的字串，若 `div5` 成立且 `div3` 不成立，那麼 `(9 >> div5) >> (KK3)` 應為 4 ，因此 `KK3` 應為 `div3` 的表示式， 若 `div3` 及 `div5` 皆成立則 `4 >> KK3` 應為 0 ，故 `KK3` 在 `div3` 成立時其值應 >= 3 ， `KK3` 應為 `div3 << 2` 。
Sign in with Wallet
Connect another wallet