# 2020q3 Homework4 (quiz4)
contributed by < `grb72t3yde` >
###### tags: `sysprog2020`
---
## Links
* [第四週測驗題](https://hackmd.io/@sysprog/2020-quiz4)
* [作業區](https://hackmd.io/@sysprog/2020-homework4)

## 測驗 `1`

LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)，例如整數 `1` 的二進位為 `0 0 0 1`，而整數 `4` 的二進位為 `0 1 0 0`，則 `1` 與 `4` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為 `2`。

運用[第 3 周測驗](https://hackmd.io/@sysprog/2020-quiz3) 提到的 `__builtin_popcount` (gcc extension 之一)，我們可實作如下:

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

參考資訊:
* [詳解二進位數中 `1` 的個數](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html)

### 個人解題思路
OP = ?
1. 考慮到使用 `__builtin_popcount`, 因此直觀地使用 `XOR` 來使得兩個輸入 x, y 相同的 bit 結果為 `0`, 而不同的 bit 為 `1`

### 延伸問題
- [x] 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼
- [x] 練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
* 以下為我的實作 (`naive.c`), runtime 目前為 `48ms` (better than 35%), 待改進
* 我使用直覺的想法, 以陣列紀錄 `0`, `1` 的個數方式, 以空間換取時間以避免 TLE

int totalHammingDistance(int* nums, int numsSize){

    int res = 0;
    int zeroCount[31] = {0};
    int oneCount[31] = {0};
    
    if (!numsSize)
        return 0;
    
    for(int i=0; i<numsSize; i++)
    {
        for(int j=0; j<30; j++)
        {
            if(nums[i] & (1 << j))
            {
                res += zeroCount[j];
                oneCount[j]++;
            }
            else
            {
                res += oneCount[j];
                zeroCount[j]++;
            }
        }
    }
    
    return res;
}

:::warning
或許試著找出減少 `branch` 的方法
:::
- [ ] 研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/上課講義/[20170710][抽象代數的實務應用].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
* 搭配閱讀 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&feature=youtu.be) 及 [Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE&feature=youtu.be)，你可適度摘錄影片中的素材，但應當清楚標註來源
- [ ] 研讀 [Reed–Solomon error correction](https://en.wikipedia.org/wiki/Reed–Solomon_error_correction)，再閱讀 Linux 核心原始程式碼的 [lib/reed_solomon 目錄](https://github.com/torvalds/linux/tree/master/lib/reed_solomon)，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範

## 測驗 `2`
TODO

## 測驗 `3`

:::info
> 白板 coding 其實本意 (最好不要是) 不是考一些你已經會的東西，而是考一個你可能不會的問題，然後你要 keep trying, keep doing 下去，因為它的本質是在考一個未來你可能碰到的問題 (而且可能 Google 不到)。
出處: [簡單的 FizzBuzz 藏有深度 (Google 面試題)](https://medium.com/@Bear_/簡單的-fizzbuzz-藏有-深度-google-面試題-f5e66e3a97be)
:::

考慮貌似簡單卻蘊含實作深度的 [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

考慮下方程式碼:

#define MSG_LEN 8
char fmt[MSG_LEN + 1];
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`)

#define MSG_LEN 8

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 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

gcc-9 還內建了 [FizzBuzz optimization](https://hackmd.io/9OuLG3FgQ22TPpaTXUI_kQ) (Bug 82853 - Optimize x % 3 == 0 without modulo)。

### 個人解題思路
KK1 = ?
1. 觀察程式碼, 發現 `div3`, `div5` 分別表示整數 `i` 能否被 `3`, `5` 整除
2. 考慮到要從不同的 `start` 複製 "FizzBuzz%u" 字串, 可以判斷用 `MSG_LEN` 進行左移兩次的數值 `KK1` 與 `(KK2 << KK3)` 個別在處理 能被 `5` 整除 以及 能被 `3` 整除的情況
3. 考慮到 `i` 是 `3` 的倍數或是 `15` 的倍數時, 都應該從 [0] 處開始複製, `KK1` 應為 `div5` (否則沒有其他判斷 `div5` 處)

KK2 = ? KK3 = ?
1. 假設 `i` 為 `3` 之倍數, 應該從 [0] 處開始複製, 此時 `(KK2 << KK3)` 必須為 `3` 以上的值
2. 但同時考慮到 `i` 不為 `3` 的倍數時, 只能透過 `KK2` = `div3` 且 `KK3` = `2` 來控制此種條件