# 2022q1 第 2 週測驗題
contributed by < ```DokiDokiPB``` >
<!--
[quiz2](https://hackmd.io/@sysprog/BybKYf5xc)
-->
### 測驗 ```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)``` 會無條件捨去二進位中最低位元的位數，但若 a 與 b 在最低位加法時進位，則```(a >> 1) + (b >> 1)``` 需再加上 1
以數位邏輯電路中， 取得進位數值的運算為```(a & b)``` 表示當前下個 $carry_{in}$的數值，即上圖中的 $carry_{out}$
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
取 EXP2 為 ```a & b```
取 EXP3 為 ```a ^ b```
> 在[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 節錄
在數位邏輯中， ```a + b``` 可以用表示```(a ^ b) + ((a & b) << 1)```
```(a + b) / 2``` 相當於 ```((a ^ b) + ((a & b) << 1)) >> 1``` = ```(a ^ b) >> 1 + (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 ^ ...``` 形式，可以推導
- ```a <= b```，則回傳的形式應為：```a ^ a ^ b = b```
- ```a > b```，則回傳的形式應為：```a ^ 0 = a```
若 ```a <= b``` 成立，表示 ```-(a <= b)```的數值為```-1```，在二的補數系統中，表示```0xFFFFFFFF```。最終取得```a ^ a ^ b = b```
若 ```a <= b``` 不成立，表示 ```-(a <= b)```的數值為```0```，在二的補數系統中，表示```0x00000000```。最終取得```a ^ 0 = a```
<!--
以上是在二的補數系統下才成立的函式，但若是一的補數系統呢？ 可以參考
> 在[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E7%AC%AC%E4%B8%89%E9%83%A8%E5%88%86%EF%BC%9A%E5%9C%A8%E8%B3%87%E8%A8%8A%E5%AE%89%E5%85%A8%E7%9A%84%E6%87%89%E7%94%A8)節錄
> 自 C99 提出 Fixed width integer types (定義於標頭檔 <stdint.h>) 並規範採用二補數，因此諸如 int16_t, int32_t, int64_t 等經由 typedef 定義 (因此會以 _t 結尾)、編譯器實作商提供的衍生型態，必定是二補數系統。
> > 參見 C 語言規格書 (7.18.1.1 Exact-width integer types, 1.) The typedef name 𝚒𝚗𝚝_𝑁𝚝 designates a signed integer type with width 𝑁 , no padding bits, and a two’s complement representation. Thus, int8_t denotes a signed integer type with a width of exactly 8 bits
-->
### 測驗 ```3```
```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;
}
```
取 COND 為 ```v```
取 RET 為 ```u << shift```
直接運算一次：
- 例如 $gcd(84, 13)$
$$
84 = 13 * 6 + 6 \\
13 = 6 * 2 + 1 \\
6 = 1*6 + 0
$$
- 例如 $gcd(84, 12)$
$$
84 = 12 * 7 + 0
$$
對應測驗題中原本 $gcd$ 的程式碼， while loop 的中止條件為： ```v``` = ```0```，推導出等價實作的 while loop 的中止條件也為```v```，因此取 COND 為 ```v```
在題目敘述中
> If x and y are both even, gcd(x, y)= 2 * gcd(x, y) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
因此 ```shift``` 的作用為預先將 2 公因數提出，最後再做 bitwise operation 回去。
在等價實作的程式碼中，都是對 2 預先做處理，其餘運算事實上與原本的 $gcd$ 實作相同。
#### 延伸問題 2 (在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升)
#### 延伸問題 3 (Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景)
> 節錄自 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c)
```c=
unsigned long gcd(unsigned long a, unsigned long b)
{
unsigned long r = a | b;
if (!a || !b)
return r;
/* Isolate lsbit of r */
r &= -r;
while (!(b & r))
b >>= 1;
if (b == r)
return r;
for (;;) {
while (!(a & r))
a >>= 1;
if (a == r)
return r;
if (a == b)
return a;
if (a < b)
swap(a, b);
a -= b;
a >>= 1;
if (a & r)
a += b;
a >>= 1;
}
}
```
在程式碼第 3 ~ 5 行中，```r``` 為 ```a``` 與 ```b``` 的 2 的冪共同因數，可得 $gcd(a,b) = r * \space ...$
> 在測驗 ```1``` 的延伸閱讀 [Introduction to Low Level Bit Hacks #7. Isolate the rightmost 1-bit.](https://catonmat.net/low-level-bit-hacks)，可以得知在二的補數下， ```r &= -r``` 取得最低位元的 1 的位置
在程式碼第 6 行中，已知 ```r``` 為 ```a``` 與 ```b``` 最大 2 的共同因數，將 ```b``` 多餘的 2 的冪移除。同理在 for loop 中，也將 ```a``` 的多餘的 2 的冪移除。
因此在接下來的程式碼中，假設```a``` = $mr$ 與 ```b``` = $nr$，其中 ```m, n``` 為奇數， ```r``` 為 2 的冪
在程式碼第 26 ~ 27 行中， ``` a -= b``` 必為 ```r``` 的倍數，且 ```(m - n)```必為偶數，必定多出至少一個 2 的冪，可以 ```a >>= 1```
在程式碼第 28 ~ 30 行中，可以簡單用例子說明：假設 ```a``` = $3r$, ```b``` = $3r$，若不執行```if(a & r) a += b```，會得到 ```a``` = $1.5r$，這樣 ```a``` 不為 ```r``` 的整數倍數。 已知 $gcd(a + b, b) = gcd(a, b)$，透過加回一個 ```b``` 不影響結果。
並且因為 ```a += b``` 必定產生新的 2 的冪，透過 ```a >>= 1``` 移除。
> 事實上移除第 28 ~ 30 行並不影響結果，在下一個 for loop 中， ```a``` 多餘的 2 的冪會被移除。
### 測驗 ```4```
```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;
}
```
以及改寫的程式碼
```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;
}
```
<!--
> 根據
-->
### 測驗 ```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 ))```
<!--
透過與其它 [LeetCode 的回答 Golang 版本](https://leetcode.com/problems/fraction-to-recurring-decimal/discuss/1729970/Golang-Solution-or-Simple-and-Easy-to-understand)，比對程式碼對照程式碼行為
-->
LeetCode 題目敘述為：
- 輸入兩個數字，```numerator```（分子）與```denominator```（分母），輸出它的小數。以這樣形式的輸入必為有理數，可能是循環小數或是有限小數。
- 題目保證輸出結果一定是 $10^4$ 長度內
在此可能實作中，先做一次整數除法後，得到 ```division```與```remainder```
- ```division```便是小數點前的整數部位
- ```remainder```便是小數點後的部位
每一次 for loop ，計算小數點後幾位的數字，並且計算```remainder```。而中止條件為：
* 當 remainder 為 ```0```，表示此小數為有限小數
* 當 remainder 在 hash map 中有相同的數字，表示此小數為循環小數。依據題目要求，在開始循環的小數部位前加入```(```與```)```
以 ``` 337 / 333 ``` 為例：
```
337 / 333 = 1 餘 4, remainder = 4
40 / 333 = 0 餘 4, remainder = (4 * 10) % 333
400 / 333 = 1 餘 67, remainder = (40 * 10) % 333 = 67
670 / 333 = 2 餘 4, remainder = (67 * 10) % 333 = 4
在 hashmap 中發現相同的 remainder 數值 --> 利用 pos 尋找循環數的起點，插入 ( 與 )並輸出結果
輸出 1.(012)
```
因此可以取 PPP 為 ```pos--```解答。
<!--
> 參考自 [laneser quzi2](https://hackmd.io/@laneser/linux2022-quiz2#%E6%B8%AC%E9%A9%97-5)筆記
-->
在可能實作的程式碼中，使用 hashmap 的方式儲存 remainder，共有 1333 個 index，並使用 Chaining 的方式解決 Collision。可以得出其 hash function 為 $k \space (mod \space 1333)$
因此可以推導出 EEE 為 ```&(heads + (remainder % size ))```
### 測驗 ```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```
> https://hackmd.io/@sysprog/c-pointer#Null-pointer
:::spoiler 神奇的問題
My Linux System got broken when I test with the following code, using ```gcc main.c; ./a.out``` command.
It is kinda fun.
```c
#include <stdio.h>
#include <stdalign.h>
int main(){
size_t a = alignof(int);
printf("%ld\n", a);
struct foo{
char c;
int _h;
};
// char b = (char *)( &(((struct foo *)0)->c) - ((char *) ));
char b = (char *) ( &(((struct foo *)0)->c) );
printf("%d\n", b);
return 0;
}
```
```
➜ ~ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
:::
### 測驗 ```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);
* 但是會令答案無解，但若是改成下列程式碼，則能正確輸出。
*/
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
取 KK1 為 ```div3```
取 KK2 為 ```div5```
取 KK3 為 ```div3 << 2```
列出其增值表
| div3 | div5 | (2 << KK1) << KK2 | KK1 | KK2 |
|:----:|:----:|:-----------------:|:---:|:---:|
| 0 | 0 | 2 | 0 | 0 |
| 0 | 1 | 4 | 0 | 1 |
| 1 | 0 | 4 | 1 | 0 |
| 1 | 1 | 8 | 1 | 1 |
因此取 KK1 為 ```div3```， KK5 取 ```div5```。兩者答案可以對調。
原題目
```strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);```
會令輸出產生 ```u``` 而非 ```%u```，因此改為
```strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);```
考慮 strncpy 複製的範圍，列出其增值表
| div3 | div5 | 8 >> div5 >> (KK3) | 預期的 KK3 |
|:----:|:----:|:------------------:|:---:|
| 0 | 0 | 8 | 0 |
| 0 | 1 | 4 | 0 |
| 1 | 0 | 0 | 4 |
| 1 | 1 | 0 | 4 |
可以發現 KK3 數值一直為 div3 的四倍，因此，取 ```div3 << 2```
Sign in with Wallet
Connect another wallet