---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `PinLin` >
## 測驗 `1`
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
// EXP1 = a & b & 1
```
`(a >> 1) + (b >> 1) + (EXP1)` 即是對兩個無號整數取平均值的結果，前面的 `a >> 1` 和 `b >> 1` 可以被理解為「除以二後無條件捨去至整數位」，後面的 `EXP1` 則是我們目前缺少的部分。
將 `a` 和 `b` 分別帶入數字，得到了下表：
| `a` | `b` | `(a >> 1) + (b >> 1)` | expected |
| :---: | :---: | :---: | :---: |
| 2 | 2 | 2 | 2 |
| 2 | 3 | 2 | 2 |
| 3 | 2 | 2 | 2 |
| ==3== | ==3== | ==2== | ==3== |
我們發現當兩者都是帶入奇數時，`a >> 1` 和 `b >> 1` 將各自捨去 0.5，相加後便比我們期望得到的答案還少 1。
因此在這裏 `EXP1` 應作為一個補償：在 `a` 與 `b` 皆為奇數時為 `1`，否則為 `0`，以 `(a & 1) & (b & 1)` 表示，最後簡化為 `a & b & 1`。
---
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
// EXP2 = a & b
// EXP3 = a ^ b
```
這樣的形式讓我想到了加法器的操作，只是要求平均需要多一個除以二的操作，嘗試推導了一下：
`a + b = (a ^ b) + ((a & b) << 1)`
`(a + b) / 2 = ((a ^ b) + ((a & b) << 1)) >> 1`
`(a + b) / 2 = ((a ^ b) >> 1) + (a & b)`
最後得證 `EXP2` 為 `a & b`，`EXP3` 為 `a ^ b`。
## 測驗 `2`
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
// EXP4 = a ^ b
// EXP5 = a < b
```
首先我們知道這個函式的輸出只有可能是 `a` 或是 `b`，假設 `a ^ ((EXP4) & -(EXP5))` 的結果是 `a`，那麼 `(EXP4) & -(EXP5)` 就必須是 `0`；反之，若結果是 `b` 則將運用到 XOR 的特性，`(EXP4) & -(EXP5)` 的結果必須是 `a ^ b`。
根據題目的限制，推斷 `EXP4` 為 `a ^ b`，而當 `b > a` 時 `-(EXP5)` 應為 `-1`，否則應為 `0`，推得 `EXP5` 即為 `a < b`。
### 針對 32 位元有號整數撰寫同樣 branchless 的實作
只需將參數 `a`、`b` 和回傳值型別改為 `int32_t` 即可，因為 `a` 和 `b` 皆為有號數，進行的便是有號數的比較。
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
## 測驗 `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;
}
// COND = v
// RET = u << shift
```
這個函式首先在第 5~8 行中透過檢查 LSB 的方式判斷 `u` 跟 `v` 是否是 2 的倍數，是則將兩者各除以二，並將除以二的次數記錄在 `shift` 中。
接著在第 11~21 行中執行類似輾轉相除法的流程來嘗試找出兩者的最大公因數，由於 `u` 會等於操作前的 `v`，`v` 會等於操作前的 `u - v`，所以 `COND` 在此應該判斷 `v` 是否為 `0`。
最後離開迴圈之後需再將 `u` 的值左移 `shift` 次，便是 `u` 跟 `v` 真正的最大公因數。
## 測驗 `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;
}
// EXP6 = bitset & -bitset
```
這段程式首先將 `bitmap` 一塊一塊取出作為 `bitset`，接著透過 `EXP6` 表示式找出 `bitset` 目前最低位元的 `1` 並紀錄到 `t`。
研究了一下題目提到的 `-bitwise` 特性，嘗試列出幾個數字和它二的補數：
$$ 104 = (01101000)_b \\ -104 = (10011000)_b $$
發現將一個數字和其二的補數做 AND 運算，便可找出該數字最低位元的 `1`，因此 `EXP6` 應為 `bitset & -bitset`。
## 測驗 `5`
```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;
}
// PPP = pos--
// MMM = list_add
// EEE = &heads[remainder % size]
```
這段程式嘗試求出給定分數的比值，主要分成求出整數和小數的部分。
整數部分直接使用整除除法求得 `division` 和 `remainder`，接著小數的部分：
- 第 72~75 行，因為考慮到有循環小數，需要記錄曾經出現過的 `remainder`，於是先配置了一段大小為 `size * sizeof(struct list_head)` 的空間並初始化，作為 hash table 的 buckets。
- 第 77~97 行，若是 `remainder` 不為 `0` 則進入迴圈，首先檢查 hash table 是否存在目前的 `remainder`。
- 第 79~88 行，若存在即代表結果為「循環小數」，首先整併不循環的小數部分，再整併加上括弧後循環的小數部分，因為 `remainder` 不可能等於 `0`，所以至此直接回傳結果。
- 第 89~96 行，若不存在則將其記錄到 hash table 中，接著做下一輪的除法並記錄結果。
- 第 99~100 行，最後當 `remainder` 等於 `0`，便將小數的部分整併至整數的部分並回傳結果。
## 測驗 `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)
// M = _h
// X = 0
```
這段程式利用到 `struct` 會以成員中最大的對齊長度來對齊所有成員的特性，因為成員 `char c` 對齊長度只有 `1`，所以只要將目標型別帶入 `t` 後計算 `struct` 開頭到成員 `t _h` 的長度，就可以知道型別 `t` 所需的對齊長度。
## 測驗 `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;
}
// KK1 = div3
// KK2 = div5
// KK3 = div3 << 2
```
這段程式藉由修改 `fmt` 的內容去控制輸出，而 `fmt` 的內容又是在第 17 行中透過 `"FizzBuzz%u"` 根據不同條件使用不同的起始位置和長度複製過去的。
根據 `div3` 和 `div5` 值的不同，列出了下表顯示我們期望的 `fmt`，以及其所需的 `length` 和起始位置：
| `div3` | `div5` | 起始位置 | `length` | `fmt` |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 0 | 8 | 2 | `%u` |
| 0 | 1 | 4 | 4 | `Buzz` |
| 1 | 0 | 0 | 4 | `Fizz` |
| 1 | 1 | 0 | 8 | `FizzBuzz` |
但是我發現在第 17 行中間的 `&"FizzBuzz%u"[(9 >> div5) >> (KK3)]` 在 `div3` 和 `div5` 皆為 `0` 時會將字串起始位置訂在 `9`，這樣便無解了。所以我認為應該把此處的 `9` 改為 `8` 才對。
為了控制 `length`，`KK1` 和 `KK2` 應為 `div3` 和 `div5`。而為了控制起始位置，`KK3` 應該為 `div3 << 2`。
Sign in with Wallet
Connect another wallet