# 2022q1 Homework2 (quiz2)
contributed by < `rickywu0421` >
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗 `1`
### 題目
考慮以下對二個無號整數取平均值的程式碼:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
接著我們可改寫為以下等價的實作:
```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);
}
```
### 解題
第一種實作方式為將 `a` 與 `b` 分別 right shift 1 bit 後相加, 此時還考慮到進位: `a` 與 `b` 的 LSB 是否都為 1, 故 EXP1 = `a & b & 1`。
第二種實作方式為加法器的概念, `x ^ y` 表示為位元和, `x & y` 表示為進位, 則
`a + b = x ^ y + (x & y) << 1` =>
`(a + b) / 2 = ((x ^ y) + (x & y) << 1) >> 1 = (x & y) + (x ^ y) >> 1`
故 EXP2 = `x & y`, EXP3 = `x ^ y`
## 測驗 `2`
### 題目
改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
### 解題
我們可以透過回傳值猜測題目中的表示式：
- 當 `a > b` 時, 回傳 `a`;
- 當 `b > a` 時, 回傳 `b`;
又 XOR 有兩個特性 (x 為任一整數)：
- `x ^ x = 0`
- `0 ^ x = x`
故我們可以使用這兩個特性猜測題目的解,
- 當 `a > b` 時, 回傳 `a ^ 0 = a`
- 當 `a < b` 時, 回傳 `a ^ a ^ b = b`
因此 EXP4 = `a ^ b`。
再根據上面的判斷, `a > b` 時 `EXP4 & -(EXP5) = 0`, `a < b` 時 `EXP4 & -(EXP5) = a ^ b` 可知, EXP5 在 `a > b` 時為 `0`, 在 `a < b` 時為 `-1` (全部位元為 1), 故可知 EXP5 = `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;
}
```
### 解題
第二種實作與第一種實作均是輾轉相除法, 但作法略為不同, 第一種利用除法運算, 而第二種利用減法運算, 以下是運算時會用到的操作, 以及對應的程式碼片段：
1. $gcd(0, 0) = 0$
2. $gcd(u, 0) = u$, $gcd(0, v) = v$
```c
if (!u || !v) return u | v;
```
---
3. 若 $u$ 與 $v$ 均是偶數, 則 $gcd(u, v) = 2 * gcd(\dfrac{u}{2}, \dfrac{v}{2})$
```c
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
---
4. 若 $u$ 為偶數, $v$ 為奇數, 則 $gcd(u, v) = gcd(\dfrac{u}{2}, v)$
```c
while (!(u & 1))
u /= 2;
```
---
5. 若 $u$ 為奇數, $v$ 為偶數, 則 $gcd(u, v) = gcd(u, \dfrac{v}{2})$
```c
while (!(v & 1))
v /= 2;
```
這個部分的程式碼是在 do-while loop 裡的, 因為每次 loop 完 v 都會更新而有機會變成 2 的倍數。
---
核心部分：輾轉相除法
```c
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;
```
loop 中首先進行上述的操作 5, 接著判斷 $u$ 與 $v$ 兩者誰大, 用大數剪去小數, $v$ 值更新為相減後的數, $u$ 值更新為 $u$, $v$ 中較小的數, 重複進行上述操作直到兩數相減為 `0`。
故 COND = `v`, return 值則需要乘上透過操作 3 除去的倍率 (`2` 的冪), 故 RET = `u << shift`。
## 測驗 `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;
}
```
考慮 GNU extension 的 [`__builtin_ctzll`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
> 範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元，我們可發現
0 → 0 → 0 → 0 → 1，於是 ctz 就為 4，表示最低位元往高位元有 4 個 0
用以改寫的程式碼如下:
```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 的特性)。
若 bitmap 越鬆散 (即 1 越少)，於是 improved 的效益就更高。
### 解題
根據原程式碼片段：
```c
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
```
其意義為從 LSB, 迭代檢查 bitset 的該 bit 是否為 1, 若是, 則 `out[pos++] = k * 64 + 該 bit 的位置`。
改良的程式碼片段如下：
```c
uint64_t t = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
```
其概念為透過 `__builtin_ctzll()` 找出 bitset 中從低位元往高位元數來的第一個 1, 再透過 `bitset ^= t` 把那一個 1 clear, 以便進行下一個 set bit 的搜索。
假設 `bitset = 0001 0100`, 則做完一次上述的操作後位置 2 的 bit 會被 clear：`bitset = 0001 0000`, 而要怎麼達成這件事呢？
根據題目的提示 (-bitset), 根據二補數, `-bitset = 1110 1100`, 我們可發現, 將 `t = bitset & -bitset` 後可以得到一個 `bit string = 0000 0100`, 其只有一個 bit 被 set, 那就是 bitset 中最小位元為 1 的位置, 之後再透過 `bitset ^= t` 把 bitset 中最小位元的 1 clear 掉 (根據 xor 的特性), 故 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;
}
```
### 解題
以下我們以循環小數 $12 / 11 = 0.090909...$ 作為該題的例子。
該題記錄小數的作法為：用 hash table 記錄每次迭代的餘數及其在小數中的位置。
#### iter 1
每次迭代時首先會檢查該次的餘數是否存在於 hash table 中,
```c
int pos = find(heads, size, remainder);
if (pos >= 0) {
...
}
```
若是, 則此數為循環小數, 並進行以下操作：
```c
while (PPP > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
```
但首次進入迴圈時因尚未有餘數加入到 hash table 中, 故 if 判斷不成立, 所以我們先往後看：
---
以下操作不難看出為將目前的餘數及餘數的位置加入到 hash table 中, 以當前的狀態, 餘數為 `12 % 11 = 1`, index 為 `i = 0`。
```c
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
list_add(&node->link, &heads[remainder % size]);
```
---
加入 hash table 後將餘數 * 10 後除以除數：
`*q++ = (1 * 10) / 11 + '0' = '0'` =>`result = '0'`
餘數則進行以下更新：
`remainder = (1 * 10) % 11 = 10`。
```c
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
```
#### iter 2
此時 `remainder = 10`, 故以下條件仍然不成立。
```c
int pos = find(heads, size, remainder);
```
之後的操作與 iter 1 類似, 接近 loop end 時
`*q++ = (10 * 10) / 11 + '0' = '9'` => `result = '09'`
`remainder = (10 * 10) % 11 = 1`
#### iter 3
此時 `remainder = 1`, 故 if 條件成立：
第一個 while loop 的功能為是將像 `1.34(15)` 中未循環的小數寫入 result 中, 故 PPP = `pos--`。(`12 / 11` 中不存在未循環的小數)。
之後將循環的小數用小括號包起來, 最後回傳 `result = '0.(09)'`。
```c
if (pos >= 0) {
while (PPP > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
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)
```
### 解題
透過題目的 `struct { char c; t _h; }` 可以猜到 `__alignof__` 的實作想法為將欲驗證的 type 之變數宣告在 struct 中的 char 變數之後, 透過 `_h` 的位置減去 `c` 之位置可得之 type `t` 之 alignment。
故 M = `_h`, 則 `((char *)(&((struct { char c; t _h; } *)0)->_h)` 表示為變數 `_h` 的相對於 struct 起始的位置, 又因起始位置為 `0`, 則 X = `0`。
## 測驗`7`
### 題目
考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身
直覺的實作程式碼如下: (naive.c)
```c
#include <stdio.h>
int main() {
for (unsigned int i = 1; i < 100; i++) {
if (i % 3 == 0) printf("Fizz");
if (i % 5 == 0) printf("Buzz");
if (i % 15 == 0) printf("FizzBuzz");
if ((i % 3) && (i % 5)) printf("%u", i);
printf("\n");
}
return 0;
}
```
觀察 printf 的(格式)字串，可分類為以下三種:
1. 整數格式字串 "%d" : 長度為 2 B
2. “Fizz” 或 “Buzz” : 長度為 4 B
3. “FizzBuzz” : 長度為 8 B
考慮下方程式碼:
```c
char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
```c
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 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"[(8 >> div5) >> (KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
其中 `is_divisible` 函式技巧來自 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/)，甚至 gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
對於處理器來說，每個運算所花的成本是不同的，比如 add, sub 就低於 mul，而這些運算的 cost 又低於 div 。依據〈[Infographics: Operation Costs in CPU Clock Cycles](http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/)〉，可發現整數除法的成本幾乎是整數加法的 50 倍。
作答區
KK1 = ? (變數名稱)
KK2 = ? (變數名稱)
KK3 = ? (表示式，不包含小括號)
### 解題
首先看題目的這段敘述：
```c
string literal: "fizzbuzz%u"
offset: 0 4 8
```
根據是否能被 3 (`div3`) 或 5 (`div5`) 整除而產生的 `offset` 以及 `length` 變化可以做成下列表格, 以下欄位以 (div3, div5) 呈現：
| (div3, div5) | (0, 0) | (1, 0) | (0, 1) | (1, 1) |
| --- | -------- | -------- | -------- | ---|
| offset | 8 | 0 | 4 | 0 |
| length | 2 | 4 | 4 | 8 |
回到程式碼, 根據上述表格可以作答：
- length 部分
```c
uint8_t div3 = is_divisible(i, M3);
uint8_t div5 = is_divisible(i, M5);
unsigned int length = (2 << KK1) << KK2;
```
KK1 = `div3`, KK2 = `div5`
- offset 部分
```c
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
```
KK3 = `div3 << 2`
Sign in with Wallet
Connect another wallet