---
tags: linux2022, linux
---
# 2022q1 Homework2 (quiz2)
contributed by < `AmyLin0210` >
> [2022q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗 1
### 解釋程式碼運作原理
在以下的程式碼中，`a >> 1` 與 `b >> 1` 分別代表將 `a` 與 `b` 除二並無條件捨去到整數位，而後方的 EXP1 要處理的就是進位的問題。
在 `a` 與 `b` 皆為奇數時，會需要把前面相加的結果加一，因此 `EXP` 在這裡是 `a & b & 0x1`。若 `a` 與 `b` 都是奇數，那做完 and 之後最右邊的位元應該要是 `1` ，後面再與 `0x1` 做 and，得到最右邊的位元。
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
觀察二進位加法，以下面的範例為例：
```
a = 0011
b = 0010
a + b = 0011 + 0010 = 0100 + 0001 = (a & b) << 1 + (a ^ b)
```
`a & b` 可以找到 a 與 b 在相同位置是否都是 1，如果是的話，表示在那個位置他們需要進位。
`a ^ b` 則是找到在哪邊 a 與 b 分別有值，代表的是相加後不需要進位的地方。
在取平均數時，需要把 a 與 b 相加除二，因此我們把上述的算式改進一下：
```c
(a + b) / 2 = ((a & b) << 1 + (a * b)) / 2 = (a & b) + ((a ^ b) >> 1);
```
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
## 測驗 2
### 解釋程式碼運作原理
在 `max` 這個函式裡，要做的就是回傳比較大的那個值，因此先來思考，在已經給定
```c
a ^ ((EXP4) & -(EXP5));
```
這樣的算式時，我要如何分別回傳出 `a` 與 `b` 。
看到 xor 的特性:
- 一個數與 `0` 這個數字做 xor ，那會得到的便是自己。
- 一個數與自己做 xor ，那會得到 `0`。
再來看看 and 的特性：
- 若一個數與 `0` 這個數字做 and ，那會得到 0 。
- 若一個數與二進制表示時全部都是 `1` 的數字做 and ，那會得到自己。
在二補數的系統中，`-1` 在使用二進制表示時，會全部都是 1 ，因此推論 `EXP5` 這個判斷式是回傳出 `a` 或者是 `b` 的關鍵。
先去考慮 `a ^ (EXP)` 會回傳出什麼東西
- 若 EXP 為 0 ，會回傳 a 。
- 若 EXP 為 `a ^ b` 由於 `a ^ a` 會變成 `0` ，所以得到 `0 ^ b` 會是 `b` 。
推測 `EXP4` 為 `a ^ b` ，這樣才有機會去拿到一個完整的 `b`。
接下來看到 `EXP5` ，目前我們知道目標是如果我想回傳 `a` ，那會變成 `a ^ ((a ^ b) & 0)`，如果我想回傳 `b`，那會變成 `a ^ ((a ^ b) & -1)` ，這樣 `EXP5` 的答案就很顯而易見，就是 `a < b` 。
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
## 測驗 3
### 解釋程式碼運作原理
GCD 的演算法特性
1. If both x and y are 0, gcd is zero $gcd(0, 0) = 0$
2. $gcd(x, 0) = x$ and $gcd(0, y) = y$ because vevrything divides 0.
3. If x and y are both even, $gcd(x, y) = 2 * gcd(\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor. Multiplication with $2$ can be done with bitwise shift operator.
4. If x is even and y is odd, $gcd(x, y) = gcd(\frac{x}{2}, y)$.
5. On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \frac{y}{2})$. It is because 2 is not a common divisor.
以下的程式碼就是根據上述 GDB 演算法特性而改寫而來：
```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 (v);
return RET;
}
```
在第 4 行可以對照到 GDB 演算法特性的第 1 點與第 2 點，若 `u` 與 `v` 其中一方或雙方是 0 時， `u | v` 的結果便是 0 (在 u 和 v 皆為 0 時) 或者是非 0 的那個數 (在 u 和 v 僅有其中一方為 0 時)。
在第 6 行到第 8 行，可以對照到 GDB 演算法特性的第 3 點，把 `u` 與 `v` 共同對 2 的因數給取出來。
在第 9 行到第 10 行與第 12 行到第 13 行，可以對照到 GDB 演算法特性的第 4 點與第 5 點，代表把 u 與 v 對 2 的倍數給拿出來。
在第 14 到 19 行，就是經典的 GDB 操作，大數減去小數後，將結果存在 `v`，因此第 21 行的 while 迴圈判斷條件為 `v`，當減完的結果還有值，就表示 GDB 還沒完全完成。
第 22 行，回去看到第 6 到第 8 行，可以發現有把 `u` 與 `v` 共同的二的因數個數礎存在 `shift` 中，因此最後需要回傳 `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;
}
```
我們直接跳到程式碼的第 10 行，在這裡想要使用 GNU extenstion 的 [__builtin_ctzll](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
在這裡的 r 是從低位元往高位元需要連續遇上多少個 0 才碰的到 1。
然後第 12 行想要做的事情就是把已經數到的位元清零，從這邊判斷，EXP6 這裡想要做的事情是找到最低位元的 1 在哪裡，並把他設為 1，其餘位元設為 0。
因此最開始我猜 EXP6 為 `1 << __builtin_ctzll(bitset)`，但顯然的不符合作答規範。
現在來思考在什麼狀況下可以拿到等同於 `1 << __builtin_ctzll(bitset)` 的數字。
由於想要把大部分的數字給清零，首先知道 `a & ~a` 會變成 0 ，但這還不是我們想要的，我們需要留下最低位元的 1 。
以下是範例：
```
bitmap = 0b00001100
~bitmap = 0b11110011
~bitmap + 1 = 0b11110100
bitmap & (~bitmap + 1) = 0b00000100
```
然後根據二補數的定義， `~bitmap + 1` 會等同於 `-bitmap`，
所以可以得到 `EXP6 = bitset & -bitset`
## 測驗 5
這裡我們先來討論一般來說求循環小數會怎麼求。
在數學式部份，以 `4 / 333` 當作範例：
```
0.0120...
----------
333) 4 --- 1
00
---------
40 --- 2
333
---------
67 --- 3
666
--------
4 --- 4
00
```
可以從上圖很直覺地看到，當我們做到 (4) 時，由於已經與 (1) 重複了，所以就會判斷他是一個循環小數。
現在來對照下方的程式碼：
- 在第 77 行之前，做的事情為判斷正負、找到整數部份等等，第 77 行之後的 for loop 才正式開始找循環小數。
- 在第 78 行的地方，去找到是否數字已經被放在裡面了，在第 13 行的 find 函式就在做這件事情，而且使用 hash table 來加速。
- 如果有找到重複的數字，執行第 79 行到第 88 行的程式碼，如果沒有找到，則執行 89 到第 96 行的程式碼。
- 我們先來看看沒有找到的情況，在第 90 到 93 行，目標就是把目前的 remainder 與位置存起來，接著做的事情就非常的接近直式除法的部份，將 remainder 乘以 10 之後除以 denominator。
- 再來是看到有找到的情況，首先我們可以由 pos 得到從哪裡開始重複，當找到重複開始的位置之後，後面的就是循環小數。
```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 (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;
}
strcpy(p, decimal);
return result;
}
```
## 測驗 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)->_h) - (char *)0)
```
首先我們來拆解一下這份程式碼
- 看到 `struct { char c; t _h; } *)0` ，表示有個 `struct { char c; t _h; }` 型態的指標指向了記憶體的位置 0
- `(struct { char c; t _h; } *)0)->_h` 那到當中的 `_h` 參數
- `(&((struct { char c; t _h; } *)0)->_h)` 找到 `_h` 參數的位置
- `((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)` 強至轉形成 `char *` 的型態，並找到與 `(char *)0` 的距離差
簡單作個小實驗，程式碼：
```c
#include <stdio.h>
struct align_int {
char c;
int _h;
};
struct align_intp {
char c;
int *_h;
};
int main () {
char *c = 0;
struct align_int *a_int = 0;
struct align_intp *a_intp = 0;
}
```
可以發現 `int` 的 align 為 4， `int *` 這個指標的 align 為 8。
```bash
(gdb) p c
$1 = 0x0
(gdb) p &(a_int->_h)
$2 = (int *) 0x4
(gdb) p &(a_intp->_h)
$3 = (int **) 0x8
```
再來看看下面的程式碼，在這邊我做的變化是，在 `int` 型態的變數前，多塞幾個 `char` 型態的變數，看看 `int` 型態變數的記憶體位置會不會有什麼變化。
```ｃ
#include <stdio.h>
struct align_int2 {
char c[2];
int _h;
};
struct align_int4 {
char c[4];
int _h;
};
struct align_int5 {
char c[5];
int _h;
};
int main () {
char *c = 0;
struct align_int2 *a_int2 = 0;
struct align_int4 *a_int4 = 0;
struct align_int5 *a_int5 = 0;
}
```
從結果可以看到，`int` 型態變數的記憶體位置的確會以 4 為倍數對齊。
```bash
(gdb) p c
$1 = 0x0
(gdb) p &(a_int2->_h)
$2 = (int *) 0x4
(gdb) p &(a_int4->_h)
$3 = (int *) 0x4
(gdb) p &(a_int5->_h)
$4 = (int *) 0x8
```
## 測驗 7
```c=
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
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 << div3) << div5;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], 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/) 這篇文章
下面控制 FizzBuzz 的部份，先來看到 `length` 這個變數，以下有 3 種可能:
- 不是 3 或 5 的倍數，`length` 為 2 ( **%u** )。
- 是 3 的倍數或是 5 的倍數，`length` 為 4 (**Fizz** 或 **Buzz**)。
- 是 3 及 5 的倍數，`length` 為 8 (**FizzBuzz**)。
看到程式碼的第 20 行，這裡會是 `(2 << div3) << div5` 的原因為，div3 與 div5 分別表示是不是被 3 或被 5 整除，所以只會是 1 或 0，`2 << 0 << 0` 、 `2 << 1` 與 `2 << 1 << 1` 的結果分別為 2, 4, 8 ，對應到 `length` 為 2, 4, 8 的情形。
再看到程式碼第 23 行的地方，這裡表示了要從哪裡開始讀 **FizzBuzz%u** 這個字串。
我們先看到 `8 >> div5`，這樣出來可能的結果為 8 或者是 4，換句話說就是，如果可以被五整除，那就是從 4 這個位置開始讀，如果不行，那就從 8 這個位置開始。
再來我們來看 `div3`，如果它是 3 的倍數，那我無論如何都是從 0 開始讀，如果不是，則要維持上面是否為 5 的倍數的結果。在 `div3 << 2` 這裡，可以發現如果 `div3` 為 1，出來的數值為 4，若 8 >> 4 會變成 0，反之若 `div3` 為 0，則不會動。
Sign in with Wallet
Connect another wallet