# 2022q1 Homework2 (quiz2)
contributed by <`arthurchang09`>
## 測驗 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);
}
```
`a>>1` 和 `b>>1` 可視為 `a/2` 、 `b/2` 。然而，若 a 和 b 皆為奇數的話，顯然會和所要的結果差 1 。因此 `EXP` 需要確認 `a` 和 `b` 的最後的 bit 為 1 並加上，最直觀的方法為和 1 取 and ，若為偶數則會變成 0 ，奇數為 1。 `EXP` 為 `a & b & 1` 。
我們再次改寫為以下等價的實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
這邊可以運用半加器的方式思考。半加器是由一個 `AND` 和 `XOR` 組成。其真值表如下：
| A | B |A AND B|A XOR B|
|:-:|:-:|:-:|:-:|
|0|0|0|0|
|0|1|0|1|
|1|0|0|1|
|1|1|1|0|
因此 A XOR B 是兩數相加此位數的值，而 A AND B 是進位。考慮所求為 $\dfrac{A+B}{2}$ ， XOR 的部分需右移一位，即除以2方能表示此位數的狀況。進位的部分原本應左移一位加到下一位數，因為除以二而變成沒有左移。因此 EXP2 為 `a & b` 而 EXP3 為 `a ^ b >> 1`
## 測驗二
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
此題會運用 XOR 的幾個特性
* a ^ 0 = a
* a ^ (a ^ b) = b
因此，必須設法使 `((EXP4) & -(EXP5))` 中最後的值為 0 或 a ^ b 。若 a 大於 b 則為 0 ， a 小於 b 則為 a ^ b 。此時可以看到 & 在 EXP4 和 EXP5 之間且 EXP5 是帶有大於小於符號，可判斷 EXP4 為 `a ^ b` 而 EXP5 透過 `&` 使 `((EXP4) & -(EXP5))` 為 a ^ b 或 0 。
當 `EXP5` 為 0 ，`-(EXP5)` 為 0 ，經過 `&` 使 `((EXP4) & -(EXP5))` 為 0 ， a ^ 0 為 a 。
當 `EXP5` 為 1 ， `-（EXP5）` 為 `0xffffffff` ，經過 `&` 使 `((EXP4) & -(EXP5))` 為 `EXP4` ，即 `a ^ b` 。
又此函式求兩數最大值，因此 `EXP5` 為 `a < b` 。
## 測驗三
```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;
}
```
上方程式碼為 [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)，演算法如下
1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u.
2. gcd(2u, 2v) = 2·gcd(u, v)
3. gcd(2u, v) = gcd(u, v), if v is odd (2 is not a common divisor). Similarly, gcd(u, 2v) = gcd(u, v) if u is odd.
4. gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd.
首先，若兩數有一者為 0 ，則回傳另一數。這邊的回傳使用 `u | v` ，當其中一者為 0 時， or 的結果為另一數，同上述第 1 點。
若兩數皆為偶數，即 LSB 為 0 ，即可先除以二，這裡使用 for 迴圈將兩數同時除以二，直到有一數為奇數，並用 `shift` 記下除了幾次。
由於 2 不再是公因數，使用第一個 `while` 將其中一數 u 的 2 全部除乾淨。
接著使用 `do_while` 迴圈尋找奇數之公因數。因為 `v` 可能為偶數，且目前 `u` 和 `v` 之公因數不會有 2 ，故先除掉，如同地 3 點。接著進行減法找公因數，若 `v` 較大則 `v - u` 為正，直接進行下一次迴圈，若 `v` 較小，則將兩者之差 assign 給 `v` ， 將原本 `v` 之值給 `u` ，如同第四點所述。在此迴圈中主要被減的數為 `v` ，當 `v = 0` 時， `u` 之值為最大公因數中的奇數部分。接著，根據上述第 2 點要將兩數字被同除的 2 乘回。因此 COND 為 `v` ， RET 為 `u<<shift` 。
## 測驗四
```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 為
$000101_b$，那 t 就會變成 $000001_b$，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。
考慮到二補數之特性，某數先經過 `not` ，即 1 變 0 或 0 變 1 ，接著 `+ 1` 的話，若最低位元為 0 ，`not` 後為 1 ，相加進位為 0 ，直到某數某位元為 1 ， `not` 後為 0 ，相加結果為 1 ，進位即停止，某數最低位元的 1 的位置會變成 1 。此時較高位元和原數同樣位置呈 `not` 關係，較低位元皆為 0 。 如 `a = 10110` ， `~a = 01001` ， `~a + 1 = 01010` 。接著將某數與其二補數做 & ，即完成所求。 `a & -a = 10110 & 01010 = 00010` 。
## 測驗五
```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;
}
```
:::info
尚須修改
:::
程式一開始為輸出的字串配置空間，大小為 1024 byte ，接著算商和餘數，並使用 `sprintf` 將商放入 `result` 字串。接著在商後放入小數點。由於題目需要找到循環小數，這裡採用 hash table 存放每一位小數點後的數字。因此第 72 行到 第 75 行初始化 hash table。
第 77 行 `for` 迴圈是要尋找循環小數， `i` 表示目前處理到第幾位小數。一開始會先去 hash table 尋找數字是否有重複出現，若有的話，先將此位數之前的數字放入 `result` 中，在第 81 行， `*p` 是目前要放入值的位址，而 `deciaml` 則存著目前已處理的小數， `pos` 則是 hash table 中存放相同數值隻小數的位子，因此 PPP 應為 `pos--` ，才能完成前述目的。
接著，放入 `(` 再用 `while` 迴圈將重複數字後的位數一一放入 `result` 中，最後放入 `)` 和 `\0` 表示循環小數結束及字串結束，並回傳 `result` 。
若第 78 行沒有找到位置，表示數字沒重複，要在 hash table 中加入新的節點，因此第 89 到第 93 行即是初始化節點並插入。 MMM 為 `list_add` 將節點插入對應之 linked list 開頭，而所插入的 linked list 需透過 hash 找到是在 `heads` 陣列中第幾個元素，因此 EEE 為 `&heads[remainder % size]` 。接著將目前處理的小數放入 `decimal` 中並更新 `remainder` 。
最後若沒有循環小數，則將 `decimal` 複製到 `result` 小數點後，並回傳結果。
## 測驗六
`__alignof__` 是 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)
```
首先，注意到 `(struct { char c; t _h; } *)0` ，這裡宣告一個 `struct` 並將 0 轉型為 `struct *` ，使此 `struct` 的位址起點在 0 。在 `struct` 中，每一個成員所占用的記憶體長度不同，電腦為了方便記憶體存取，會額外給空間使整著 `struct` 對齊。舉個例子如下：
```c
struct example{
char c; // 1 byte
int i; // 4byte
};
```
為了對齊，實際上 `c` 後面會額外接上 3 byte ，使其長度和 `i` 一致。因此 `c` 的位址和 `i` 的位址之間是差 4 byte 而非 1 byte。
回到題目，由於以上的特性，想要求出 alignment ，必定要找到所傳入之 `t` 在這個 `struct` 的位址，因此 M 為 `_h` 。由於已將整個 `struct` 之位址定在 0 ， 要求出 alignment 則不必再寫出這一長串 `&((struct { char c; t _h; } *)0)->c` ， `(char *)0` ，即可。因此 X 為 0 。
## 測驗七
考慮貌似簡單卻蘊含實作深度的 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;
}
```
`for` 迴圈中， `div3` 和 `div5` 為某數能否被 3 或 5 整除，為真則為 1 ，反之為 0 。接著要透過控制 length 來決定輸出之方式，如題目所示：
```c
string literal: "fizzbuzz%u"
offset: 0 4 8
```
因此當某數為 3 倍數，需要印出 fizz ， `offset = 4 = 2 << 1` ， 因此 KK1 為 `div3` ，若同時為 5 之倍數，要再印出 buzz ， `offset = 8 = (2 << 1) << 1` ，因此 KK2 為 `div5` 。
接下來第 17 行便是決定要從 `"fizzbuzz%u"` 的哪個位置開始印出字串，若 `div3` 和 `div5` 皆為 0 ，則要從第 9 個字元，即數字部分開始印出。若只是為 3 倍數，要從最開頭開始印， 9 須被位移成 0 ， `9 >> 4 = 9 >> (1 << 2)` ，因此 KK3 為 2 。若只是為 5 倍數，要從第 4 個元素開始印 ， 9 須被位移成 4 ， `9 >> 1 = 1001 >> 1 = 0100 = 4` 。 若為 15 及其倍數，則一樣須從開頭開始印， 9 被位移成 0 ， `(9 >> 1) >> (1 << 2) = 4 >> 4 = 0` 。最後再印出處理好的字串。
:::info
測試的時候發現 "fizzbuzz%u" 應該要改為 "fizzbuzz %u" ，否則不會印出數字而是 u 。
:::
Sign in with Wallet
Connect another wallet