# 2020q3 Homework3 (quiz3)
contributed by < `eecheng87` >

###### tags: `進階電腦系統應用2020`

## 測驗 1

int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) >> 1
) > 0;
    unsigned int fixu = -(logical & (m < 0));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

運作原理：
`asr_i` 是為了避免 unspecified behavior，分別為負數右移補零或一，這裡希望不管怎樣都補一。從 `return` 的結果來看可以發現如果本來就補一那就回傳 `(m >> n)`，即什麼都不用改。反之則透過 `(fix ^ (fix >> n))` 修正。`logical` 是用來表示是否需要修正，如果負數右移補 1 則 `logical` 為 0，不須修正。如果需要修正則 `logical` 為 1，且 `fixu` 為 $11111..1$。`(fix ^ (fix >> n))` 為 $10000..0$，如此一來修正後剛好可以讓 most significant bit 變成 1。
## 測驗 2

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_clz(num) OPQ);  
}

運作原理：
`(num & (num - 1))==0` 是用來檢查是否為 2 power。`!(__builtin_clz(num) & 0x1)` 是用來檢查該 bit 所在的位置是否為偶數。(4 的 power，1 一定在偶數位)
## 測驗 3

int numberOfSteps (int num)
{
    return num ? __builtin_popcount(num)
 + 31 - __builtin_clz(num) : 0;
}

運作原理：
對 `num` 的運算有兩種，一是是偶數右移，二是奇數減一。`__builtin_clz(num)` 代表至少還要運算幾次，若 leading one 後均為 0，那答案就是 `31 - __builtin_clz(num)`。如果 leading one 後還有 1，那右移到 least significant bit 為 1 時就要停下來做 -1 的運算(答案加一)，而此時 `num` 又會繼續變偶數右移。可以發現如果 leading one 後有幾個 1 就要再多做幾個運算(減一)，所以最答案的公式還要再加 `__builtin_popcount(num)`。
## 測驗 4

#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 (v);
    return u << shift;
}

運作原理：
可利用已知的 gcd 相關知識來解題

* If both x and y are 0, gcd is zero gcd(0, 0) = 0.
* gcd(x, 0) = x and gcd(0, y) = y because everything divides 0.
* If x and y are both even, gcd(x, y) = 2*gcd(x/2, y/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
* If x is even and y is odd, gcd(x, y) = gcd(x/2, y).
* On similar lines, if x is odd and y is even, then gcd(x, y) = gcd(x, y/2). It is because 2 is not a common divisor.

一開始如果 `u`, `v` 均為偶數，那可以確定他們一定有公因數 2，用 `shift` 來記有幾個 2。接著 `while` 內就是輾轉相除法的實現，直到 `u == v` 跳出迴圈（這裡還有先處理一奇一偶的狀況，此狀況的公因數必不含 2，所以可以把偶數 shift，直到變成奇數）。

## 測驗 5

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 = bitset & -bitset;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;
        }
    }
    return pos;
}

運作原理：
本題最神的地方就是利用 `bitset & -bitset` 找出目前最低位的 1，並紀錄到 `t`。舉例來說，若目前 `bitset` 為 $000101_b$，那 `t` 就會變成 $000001_b$，接著就可以透過 XOR 把該位的 1 清掉，其他保留(XOR 的特性)。

註：網路上對 `__builtin_ctzll` 的解說有點容易讓人誤解，其行為為回傳由低位往高位遇上連續多少個 0 才碰到 1。

就速度方面，改善後的版本在每次 `while` 都可以直接找到下一個 1 做紀錄（一次跳過多個 0），相形之下，`naive` 版本在每個 k 都要迭代 64 次。

效能比較：
根據不同的 bitmap 分佈來做實驗

某區段特別集中的效能比較，可發現 `improved` 略優

void centralize_mp(uint64_t *mp) {
    for (int i = 0; i < MPSIZE; i++) {
        if ((i % 3) == 0) {
            mp[i] = 0xFFFFFFFFFFFFFFFF;
        }
    }
}


交錯分佈的 bitmap，兩種方法就差異較小，因為 `improved` 的內層迭代次數和 `naive` 拉進。

void interleave_mp(uint64_t *mp) {
    for (int i = 0; i < MPSIZE; i++) {
        mp[i] = 0xAAAAAAAAAAAAAAAA;
    }
}


所以簡單分類的話，如果你的 bitmap 越鬆散(1 越少)，那用 `improved` 的效益就更高。