---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `Chao-Shun-Cheng` >
## 測驗 `1`
### 程式碼解釋
```c=1
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
首先可以觀察 `a >> 1` 與 `b >> 1` 是直接先進行除以 2 的動作再相加，不過要去補償是不是第一個 `bit` 都是 1，如果是的話要補償回來。
##### `Example`
`a` = 0101, `b` = 0011, `(a + b) / 2` = 0100
`a >> 1` = 0010, `b >> 1` = 0001, `(a >> 1) + (b >> 1)` = 0011
`(a >> 1) + (b >> 1) + (a & b & 1)` = 0100
所以 `EXP1` 是 `a & b & 1`。
---
```c=1
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
可以觀察到兩數相加可以分為要進位的 `bit` 跟不須進位的 `bit`，假如是要進位的 `bit` 再除以 2 其實就是自己本身，而不需要進位的 `bit` 則需要另外再除以 2。因此可以知道 `EXP2` 是代表要進位的 `bit`，所以 `EXP2` 是 `a & b`；`EXP3` 則是代表不須進位的 `bit`，所以 `EXP3` 是 `a ^ b`。
## 測驗 `2`
### 程式碼解釋
```c=1
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
假設 `a > b` 那就代表 `a ^ ((EXP4) & -(EXP5)) == a`，另外我們知道 `a ^ 0 = a`，所以代表當 `a > b` 時 `(EXP4) & -(EXP5) == 0`。再來 `EXP5` 是 logical operator，只會輸出 `0` 或 `1` 再加上負號，所以會只有 `0` 跟 `-1` 兩種可能性。因此我們可以推出 `EXP5` 就是 `a < b`。另外我們知道 `a ^ a = 0`，因此我們可以推出 `EXP4` 就是 `a ^ b`。
## 測驗 `3`
### 程式碼解釋
```c=1
#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;
}
```
首先可以看到第六行的 `for` 迴圈，會利用 `shift` 把最大公因數裡有幾次 2 存起來。再來 `do while` 做的事情就跟 GDB 說明程式一樣，因此 `COND` 就是 `v`。當結束 `while` 迴圈，就代表 `u` 是最大公因數，但還要記得用 `shift` 補償回去，因此 `RET` 就是 `u << shift`。
## 測驗 `4`
### 程式碼解釋
```c=1
#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;
}
```
第八行開始的 `while` 迴圈就是直接利用 `__builtin_ctzll` 去找出有 1 的位置，再存進去 `out` 裡面，其中 `t` 用來存從低位元開始，第一個出現 1 的位置。
##### `Example`
`a` = 1010, `-a` = 0110
`a & -a` = 0010
因此 `EXP6` 就是 `bitset & -bitset`
## 測驗 `5`
### 程式碼解釋
```c=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;
}
```
這題主要是建立 1024 個大小的 `hash table` 來去尋找是否有相同的餘數。首先看到第 7 與 12 行，先確定除數跟被除數都非 0 。35 行則是先將整數的部分存進 `result` 裡面，緊接著就是進入 `for` 迴圈處理餘數的部分。可以先看到 66 行會建立 `node` ，並把餘數當作是 `key` ，要存進去 `hash table` 裡面。第 70 行就是要將 `node` 存進對應的 `bucket` 裡面，因此 `MMM` 就是 `list_add`，而 `EEE` 就是 `heads + (remainder % size)`。第 72 行則是把看目前的數字存進 decimal 裡面。緊接著回頭看第 55 行，如果有找到對應的值，就代表發生循環小數，不過循環小數不一定是小數點第一位，因此要先將循環小數前面的數字存進 `result` 裡面，因此可以得知 `PPP` 就是 `pos--`。
## 測驗 `6`
### 程式碼解釋
```c=1
/*
* 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)
```
從題目可以知道會回傳 `alignment` 的大小，因此只要我們知道一個 member 所佔的大小即可知道答案。因此可以知道 `M` 就是 `_h`，而 `X` 就是 `0`
## 測驗 `7`
### 程式碼解釋
```c=1
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;
}
```
## 測驗 `7`
### 程式碼解釋
```c=1
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;
}
```
先從以下程式碼可以知道， length 會代表要 print 出來的長度，因此可以知道當整除三同時整除五時 `length = 8`，當只有整除五或只整除三時 `length = 4`。因此可以猜出 `KK1` 就是 `div3`，`KK2` 就是 `div5`。
```c=1
char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
再來看 17 行的程式碼，會有以下幾種情況可以觀察
* 只被三整除 : `(9 >> div5) >> (KK3) = 0`
* 代表 `9 >> KK3 = 0`
* 只被五整除 : `(9 >> div5) >> (KK3) = 4`
* `9 >> 1 = 4` 代表 `KK3 = 0`
* 都不整除 : `(9 >> div5) >> (KK3) = 9`
* 代表 `KK3 = 0`
* 都能整除 : `(9 >> div5) >> (KK3) = 0`
* `9 >> 1 = 4` 代表 `KK3 >= 3`
因此可以推斷出 `KK3` 就是 `div3 << 2`
Sign in with Wallet
Connect another wallet