# 2022q1 Homework2 (quiz2)
contributed by < [Eric-liau](https://github.com/Eric-liau) >

## 實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           94
Model name:                      Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping:                        3
CPU MHz:                         900.002
CPU max MHz:                     3500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

## [作業要求](https://hackmd.io/@sysprog/BybKYf5xc)

## 測驗一
考慮以下對二個無號整數取平均值的程式碼:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

可改寫為以下等價的實作:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

其中 `EXP1` 為 `a`, `b`, `1` (數字) 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。

**想法\:** `(a >> 1) + (b >> 1)` 可以很輕易地看出是把 a 和 b 分別除以 2 後再相加，那麼剩下的 `EXP1` 就很明顯是在考慮進位問題，而會需要進位的情況就只有 a 和 b 的最後一個 bit 都是 1 一種，因此可得出 `EXP1` 為 `a & b & 1`。

再次改寫為以下等價的實作:

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

其中 `EXP2` 和 `EXP3` 為 `a` 和 `b` 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。

**想法\:** `EXP2` 沒有進行右移，推斷其為相加後會發生進位的部分，即 `a & b` ， `EXP3` 有進行右移，推斷其為相加後並未發生進位的部分，即 `a ^ b` 。

:::info
延伸問題
:::

## 測驗二
改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 `min`，我們得到以下實作 (`max`):

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

其中 `EXP4` 為 `a` 和 `b` 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。

`EXP5` 為 `a` 和 `b` 的比較操作，亦即 logical operator，限定用 ``>``, ``<``, ``==``, ``>=``, ``<=``, ``!=`` 這 6 個運算子。

**想法\:** 當 `a` 較大時， `((EXP4) & -(EXP5)) = 0`， 由此推測 `EXP5` 為 `a < b` 。而當 `b` 較大時， `((EXP4) & -(EXP5)) = a ^ b` ， 由於此時 `-(EXP5)` 等於 `-(a < b)` 等於 -1，即全部的 bit 都為 1，故可推測 `EXP4` 為 `a ^ b` 。
:::info
延伸問題
:::

## 測驗三

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#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;
}

改寫為以下等價實作:

#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`, `RET`

**解析\:** 4~7 行將公因數中包含 2 的部分先提出；9~10 行及 12~13 行分別將 `u` 和 `v` 中剩餘含有 2 的部分提出，即只留下奇數的部分；14~19 行則以 `v` 為被減數、 `u` 為減數進行輾轉相除法。

**想法\:** `v` 為被減數，所以只要 `v` 不為 0，迴圈都應繼續進行， 故`COND` 應為 `v` ；`u` 為減數，即透過輾轉相除法所算出的最大公因數，再乘上一開始被提出的所包含 2 的部分即為此題解，故 `RET` 應為 `u << shift`。

:::info
延伸問題
:::

## 測驗四
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼:

#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;
}

考慮 GNU extension 的 [__builtin_ctzll](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 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;
}

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 `t` 變數。舉例來說，若目前 `bitset` 為 $000101_b$，那 `t` 就會變成 $000001_b$，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

請補完程式碼。

**解析\:** 把值為 1 的 bit 存在 `out` 中，並回傳值為 1 的 bit 總數。

**想法\:** 運用 2 補數的概念，在對每個 bit 取 not 後還要再 + 1，所以 `bitset` 最低位元的 1 在 `-bitset` 中也會是 1 ，故可得出 `EXP6` 為 `bitset & -bitset` 。

:::info
延伸問題
:::

## 測驗五
以下是 LeetCode [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作:

#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;
}

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

**想法\:**
- 30 ～ 39 行分別檢查除數合被除數 = 0 的情況
- 51 ～ 53 行確認結果是否為負數
- 58行將商數存入 `result`
- 59 ～ 60 行檢查是否有小數部份，即餘數是否 = 0
- 78 ～ 79 行檢查是否出現循環小數，即 `remainder` 是否重複出現
- 80 ～ 81 行將未出現循環的部份存入 `result` ，可從此推斷出 `PPP` 為 `pos--`
- 82 ～ 86 行將循環的部份存入 `result`
- 89 ～ 93 行將 `node` 新增到 hash table ''`heads`'' 中，故 `MMM` 應為 `list_add` ， `EEE` 應為 `&heads[remainder % size]`
- 95 ～ 96 行為進行小數除法時補 0 的動作

:::info
延伸問題
:::

## 測驗六
[__alignof\_\_](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 GNU extension，以下是其可能的實作方式:

/*
 * 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)

請補完上述程式碼，使得功能與 __alignof\_\_ 等價。

**想法\:** 得出的值必須是 `t` 對齊所需的位元數，從題目看來是採用頭尾相減的方式，即 `_h` 的起始位址減掉 `c` 的起始位址。而`c` 的起始位址就是整個 struct 的起始位址，也就是 0 ，因此可得出 `M` 為 `_h` ， `X` 為 0 。

:::info
延伸問題
:::

## 測驗七
考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:

- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身
- 直覺的實作程式碼如下: (naive.c)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 `printf` 的(格式)字串，可分類為以下三種:

1. 整數格式字串 "%d" : 長度為 2 B
2. “Fizz” 或 “Buzz” : 長度為 4 B
3. “FizzBuzz” : 長度為 8 B

考慮下方程式碼:

char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:

string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.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;
}

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

**想法\:**
- `length` 的值為要輸出的字串長度，從上述討論可得知整除於 3 或 5 時長度為 4 ，即左移 1 位；整除於15時長度為 8 ，即左移 2 位；皆不整除於 3 或 5 時長度為 2 ，即不進行左移，因此可得出 `KK1` 為 `div3` ， `KK2` 為 `div5`。
- 第 17 行將要輸出的內容存入 `fmt` ，其中 `(9 >> div5) >> (KK3)` 即為前面所提到的 offset 值，可以發現只要 `div3` 為 1 ， offset 就必須為 0 ，而 9 的 2 進制為 '1001' ，必須要右移 4 位才會為 0 ，因此可得出 `KK3` 為 `div3 << 2`。

:::info
延伸問題
:::