# 2020q3 Homework6 (quiz6)
contributed by <`hsiehong`>
###### tags: `進階電腦系統理論與實作`

> [quiz6](https://hackmd.io/@sysprog/2020-quiz6)
> [其他繳交共筆](https://hackmd.io/@sysprog/2020-homework6)

### 測驗 1

FP32 to [BF16](https://en.wikipedia.org/wiki/Bfloat16_floating-point_format) 轉換程式

float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= BB1;
    r /= 256;
    y = x + r;

    *py &= BB2;
    return y;
}

測試程式

void print_hex(float x) {
    int *p = (int *) &x;
    printf("%f=%x\n", x, *p);
}

int main() {
    float a[] = {3.140625, 1.2, 2.31, 3.46, 5.63};
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
        print_hex(a[i]);
        float bf_a = fp32tobf16(a[i]);
        print_hex(bf_a);
    }
    return 0;
}

`BB1` = `0xff800000`
`BB2` = `0xffff0000`


#### 程式碼運作機制
* 轉換前會先確認 floating point 是否是 `NaN`, `0`, 或 `infinity`，是的話就直接回傳，`exp` 跟 `man` 分別就是在讀取 `exponent part` 跟 `fraction part` 的資訊，由於 BF16 與 FP32 對於 `Nan`(exponent 全 1，fraction 全 0), `Infinity`(exponent 全 1，fraction 非 0),`0` 的判斷條件都一樣，所以可以直接回傳
* 若是 Normalized Number，可以直接捨棄 FP32 的後 16 bits，

* reference
* [各種小數表示方式](https://moocaholic.medium.com/fp64-fp32-fp16-bfloat16-tf32-and-other-members-of-the-zoo-a1ca7897d407)
* [wiki](https://en.wikipedia.org/wiki/Bfloat16_floating-point_format)

---

### 測驗 2

---

### 測驗 3

---

### 測驗 4
#### [LeetCode 287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)

int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (CCC)
            res += bit;
    }
    return res;
}

`CCC = c1 < c2`

#### 程式碼運作機制
* `log_2` 代表取幾次 `log` 會等於 0，用意是在計算需要考慮幾個 bits，因為題目有說到 n 個數的範圍都介在 0 ~ n-1，這些數都能用 log_2 個 bits 來表示
* 這題的用到概念跟 [quiz2](https://hackmd.io/MpKiicu-SkaYWrvn5gB2kA?view#%E6%B8%AC%E9%A9%976) 的第 6 小題概念類似，**每個 bit 都是獨立個個體**，可以分開來看待
* 假設陣列大小是 4，出現的整數範圍會是 [1,3]，假設每個數都剛好出現一次會是下面的狀態:

| num | b~1~ | b~0~ |
|:---:|:----:|:----:|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
| sum | 2 | 2 |

* 可以把上面這個狀態當作**基準點**看待，雖然 0 並不會出現在陣列中，但因為這個**基準點**是沒有出現重複的數，加入判斷會比較好懂，再舉個例，假設有重複的數字是 2，那狀態會如下

| num | b~1~ | b~0~ |
|:---:|:----:|:----:|
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
| 2 | 1 | 0 |
| sum | 3 | 2 |

* 有了重複的數字之後，形成的狀態再跟上面的**基準點**比較，不難發現每個大於基準點相對的 bit 剛好就是重複的數字有的 bit，在這個例子來說就是 **10**~(2)~
* 程式碼中的 `c1`, `c2` 就是分別在統計**基準點**跟**重複陣列**在每個 bit 出現 1 的次數，若 > 基準點就表示重複的數在這個 bit 也是 1，裡面的迴圈就是在實做這個部份，而外面的迴圈是在將每個 bit 跑過一遍
* 執行結果：

#### 另解
* 1. 因為題目有給定數字範圍了，可以直接宣告一個 bool 陣列 `check[]`，其中 `check[i]` 代表 `i` 是否有出現過，若前面出現過就直接回傳 `i`
* 但缺點也很明顯，就是會使用過多的 memory

int findDuplicate(int* nums, int numsSize){
    bool *check = malloc(sizeof(bool) * numsSize);
    memset(check, false, numsSize);
    for (int i = 0; i < numsSize; i++) {
        if (check[nums[i]]) {
            free(check);
            return nums[i];
        }
        check[nums[i]] = true;
    }
    return -1;
}

執行結果

* 2. 利用 [鴿籠原理](鴿籠原理) 和 [binary search](https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95)，假設 arrSize 是 n ，出現數字範圍是 1 ~ n-1，利用 `low`, `high`, `mid` 來尋找重複出現的數字，初始定 `low` = 1, `high` = n - 1, `mid` = (`low` + `high`) / 2，每一輪利用 `mid` 當作標竿，`mid` 是 array 的 index，利用變數 `count` 統計陣列中 <= `mid` 的數字有幾個，每一輪統計完若 `count` > `mid`，根據鴿籠原理可以確認重複的數是落在小於 `mid` 這個區間的，此時再把搜索範圍改成 [1, mid]，反之亦然，下面舉例：

* arrSize 為 9 的陣列，數字範圍會在 [1,8]，初始 `low` = 1, `high` = 8, `mid` = ４，第一輪計算 <= 4 的 element 個數，發現 `count` = 6，<= 4 的數範圍只可能是 [1,4]，確有 6 個數，代表重複的數必定在這個區間並將搜索區間更改，直到 `low` >= `hign` 為止，`low` 即為所求
* 這個方法的核心概念就是透過題目限制的出現的數範圍在 `1 ~ n - 1`，`n` 是 array size，再透過 array 的 `index` 來當作一個 `flag` 來尋找重複的數
* [reference](https://leetcode.com/problems/find-the-duplicate-number/discuss/72844/Two-Solutions-(with-explanation)%3A-O(nlog(n))-and-O(n)-time-O(1)-space-without-changing-the-input-array)

| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|:-----:| --- | --- | --- |:---:| --- | --- | --- | --- | --- |
| num | 1 | 7 | 5 | 6 | 4 | 2 | 3 | 3 | 3 |

int findDuplicate(int* nums, int numsSize){
    int low = 1, high = numsSize - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        int count = 0;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] <= mid)
                count++;
        }
        if (count > mid)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

執行結果