# 2022q1 Homework2 (quiz2)
contributed by <`scottxxxabc`>
## 測驗 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);
}
```
---
### `EXP1` :
$low + (high - low) / 2$ 即為 $low / 2 + high / 2$，由題目可觀察到當 `a` 、`b` 皆為偶數時 `a >> 1` 及 `b >> 1` 分別等價於 $low /2$ 、 $high / 2$ 。 但當 `a` 、`b` 皆為奇數時，答案會和預期的少 1。因此 `EXP1` 為 `a & b & 1`。
---
- [ ] 我們再次改寫為以下等價的實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
---
### `EXP2` 、 `EXP3` :
此題須以半加器思考。如下表，`x`、`y`相加可視為 `x ^ y`，而 `carry` 則等於 `x & y`
| x | y | x+y |carry|
| -------- | -------- | -------- | -------- |
| 0 | 0 | 0 |0|
| 0 | 1 | 1 |0|
| 1 | 0 | 1 |0|
| 1 | 1 | 0 |1|
將半加器拓展至 `uint32_t` ，可寫為 `x ^ y + (x & y) << 1`。又題目要求為 $(a+b)/2$，因此應回傳 `(x ^ y) >> 1 + x & y`。
## 測驗 2
- [ ] 改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
其中 EXP4 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。EXP5 為 a 和 b 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, != 這 6 個運算子。
---
由題目可知 `EXP5` 的值應為 0 或 1。`a ^ ((EXP4) & -(EXP5))` 表示式在 `EXP5` 的值為 0 時會回傳 `a ^ 0`，根據 XOR 特性，`a ^ 0` 等於 `a`。因此 `EXP5` 應為 `a < b`。
當 `a > b` 時，`a ^ ((EXP4) & -(EXP5))` 等於 `a ^ (EXP4) ` 。此時應回傳 `b`，因此 `EXP4` 為 `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;
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;
}
```
---
此為輾轉相除法的實作，終止條件為 `v` 為零，因此 `COND` 為 `v`。
由題目之敘述
> If x and y are both even, $gcd(x, y) = 2 * gcd(x/2, y/2)$
可觀察到 `for` 迴圈為上述算法的實作，因此 `RET` 為 `u << shift`。
## 測驗4
在影像處理中，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 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
用以改寫的程式碼如下:
```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 的效益就更高。
---
此題須找出最低位元的 1，根據題目的提示利用 2 補數的特性 `-bitset = ~bitset + 1`，可以觀察到若 `bitmap` 為 `...XXX1000...`，則`~bitmap` 為 `...~X~X~X0111...`，`~bitmap + 1` 為 `...~X~X~X1000...`，利用 `&` 可以將其他的位元設為 0。
## 測驗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;
}
```
---
首先觀察 `find` 函示，不難發現 `find` 的作用是在 Hash table 中尋找指定的 `key` 並返回 `index`，hash function 為 `key % size`。觀察`fractionToDecimal`函式，發現在 41 ~ 63 行的作用是把整數的部分存入 `result` 中。 72 行開始將 Hash table 初始化，由 72 行可知hash function 的 `size` 為 1333 。
78 行將 `pos` 設為 `find` 回傳的 `index` ，第 91 行可發現 `index` 為 `i`，可推測 93 行應該將 `node` 加入 Hash table ，因此 `MMM` 為 list_add ， `EEE` 為 `&heads[remainder % size]` ，其中 array index 即為 hash function。
由 96 行發現每次迴圈 `remainder` 會乘 10 ，因此 `i` 值為小數後的位數。觀察 `PPP` 所在的 `while` 迴圈，可發現迴圈應該執行的次數等於小數點後為循環的位數，也就是找到相同的 hash 之前。因此 `PPP` 為 `pos--` 。
## 測驗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)
```
[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory?type=view) 提到
> struct 會自動做 alignment，假設創了一個 struct，如下面 code 所示
```
struct s1 {
char c;
int a;
}
```
> 原本推論 char 為 1 byte，而 int 為 4 byte ，兩個加起來應該為 5 byte，然而實際上為 8 byte，由於 int 為 4 byte ，所以 char 為了要能 alignment 4 byte 就多加了 3 byte 進去 ，使得 cpu 存取速度不會因 address 不是在 4 的倍數上，存取變慢。
編譯器會在根據下一個變數的大小在 `char c` 後面加入適當的 padding。如上述的變數 int 就會加入 3 byte padding。
> [Wiki](https://en.wikipedia.org/wiki/Data_structure_alignment)
> ... ,and GNU (GCC) when compiling for 32-bit x86:
> - A char (one byte) will be 1-byte aligned.
> - A short (two bytes) will be 2-byte aligned.
> - An int (four bytes) will be 4-byte aligned.
> - A long (four bytes) will be 4-byte aligned.
> - A float (four bytes) will be 4-byte aligned.
> - A double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux (8-byte with -malign-double compile time option).
> - A long long (eight bytes) will be 4-byte aligned.
> - A long double (ten bytes with C++ Builder and DMC, eight bytes with Visual C++, twelve bytes with GCC) will be 8-byte aligned with C++ Builder, 2-byte aligned with DMC, 8-byte aligned with Visual C++, and 4-byte aligned with GCC.
> - Any pointer (four bytes) will be 4-byte aligned. (e.g.: char*, int*)
由此可推得 `struct { char c; t _h; }` 中的 `c` 會根據 `_h`的型態自動做適當的 alignment。
題目中將 `0` cast 成 `struct { char c; t _h; }` 型態的指標，題目所求的 alignment 為 `c` 及 padding 的大小，即為 `_h` 的位址減去 `c` 的位址。因此題目的 `&((struct { char c; t _h; } *)0)->M)` 中的 `M` 應為 `_h` 。
`(char *)X` 為 `c` 的位址，也就是 struct 的起始位址，先前將 `0` cast 成 `struct` 型態的指標，所求即為 `0` 的位址，因此 `X` 為 `0` 。
## 測驗 7
考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身
```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;
}
```
觀察 `is_divisible` 可發現函式回傳 `n` 是否能整除 `M`，可以整除回傳 1，不能回傳 0。
第 14 行設定字串的長度，只能整除 3 或 5，length 為 4 ; 若整除 15，length 為 8 ; 不能整除 3 或 5，length 為 2。因此 `KK1` 為 `div3` ， `KK5` 為 `div5`
第 17 行設定字串的起始位置，整除 3 或 15 起始位置為 0 ; 若整除 5， 起始位置為 4 ; 不能整除 3 或 5，起始位置為 8。將 9 右移到 0 至少要右移 4 位元，因此 `KK3` 為 `div3 << 2`
Sign in with Wallet
Connect another wallet