2020q3 Homework6 (quiz6)

contributed by <hsiehong>

tags: 進階電腦系統理論與實作

quiz6
其他繳交共筆

測驗 1

FP32 to BF16 轉換程式

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

  • 各種小數表示方式
  • wiki

---

測驗 2

---

測驗 3

---

測驗 4

LeetCode 287. 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 的第 6 小題概念類似，每個 bit 都是獨立個個體，可以分開來看待
• 假設陣列大小是 4，出現的整數範圍會是 [1,3]，假設每個數都剛好出現一次會是下面的狀態:

num	b1	b0
0	0	0
1	0	1
2	1	0
3	1	1
sum	2	2

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

num	b1	b0
1	0	1
2	1	0
3	1	1
2	1	0
sum	3	2

• 有了重複的數字之後，形成的狀態再跟上面的基準點比較，不難發現每個大於基準點相對的 bit 剛好就是重複的數字有的 bit，在這個例子來說就是 10₍₂₎
• 程式碼中的 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，假設 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

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

執行結果