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

## 測驗一
依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):
>“The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is **iplementation-defined**.”

在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR) 歸屬於 unspecified behavior.
本題希望我們實作出一個可以跨平台使用的 ASR 函式。

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

而除了算數位位移，還有邏輯位移，以題目的範例為例子，假設有 5 個位元， -5 的二進位表示為 `1111 1011`。
* 如果是算術位移的話則的到 `1111 1101` 為 -3。
* 如果是邏輯位移的話則得到 `0111 1101` 為 125。

同樣套用程式碼 -1 上
* -1 >> 1 若為算數位移，則位移後結果為 < 0， logical 為 0， `fix` 變數一定為 0，直接操作 `m >> n`。
* -1 >> 1 若為邏輯位移，則位移後結果為 > 0， logical 為 1

算術位移才是我們所想要的，所以可以看出 logical 變數是用判斷位移的種類，所以 `OP1` 答案為 `>>1`。

知道 logical 是來判斷位移後的補位方式後：
* `m < 0` 且 logical 為 1
* 代表最左邊會補 0，但這不是我們所想要的，所以希望 `(fix ^ (fix >> n))` 補對應的 n 位 1。
* 從 return 可以發現， `fix` 和 `fixu` 不是 `0000 0000` 就是 `1111 1111`。
* 根據以上推論 `OP2` 為 `(m < 0)`。

## 測驗二
本題為使用`__builtin_clz`, `__builtin_ctz` 等 [GCC extensions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 來實作出判斷給定數值 `num` 是否為 4 的冪。

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

`return` 這裡有三個判斷式：

1. `num > 0`
2. `(num & (num - 1))==0`
3. `!(__builtin_ctz(num) OPQ)`

第一點用來判斷 `num` 是否為正數，因為 $4^n$ 一定 >= 1。

第二點是用來判斷 `num` 是否為 2 的冪。
* 因為二進位的特性，$2^n$ 為從低位元開始數，會有唯一的 bit 為 1 在第 n+1 bit ，將其減去 1 的二進位表示為第 1 ~ 第 n bit 都為 1，兩個二進位表示進行 AND 後會為 0。

第三點 `!(__builtin_ctz(num) OPQ)` 則是用來判斷已知 `num` 是 2 的冪的情況下，是否為為 4 的冪。
* $4^n = 2^{2n}$，也就是如果 `num` 為 4 的冪，n若增加 1 ，則原本 bit 為 1 的那個 bit 會往高位元增加兩格 ( $\times 4$ )， `__builtin_ctz` 計算出來一定為偶數，因此 `OPQ` 為 `& 0x1` ，用來判斷機偶數。

## 測驗三
針對 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}

>Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

題目要求計算經過 `/2` 和 `-1` 的次數。
考慮題目給的範例 `14 (00001110)`，根據題幹可以推出，若最右邊的 bi 是 1 則減 1 ，若是 0 則向右移一位。而我們可以從 `__builtin_clz` 得知目前最高的位元在哪裡， `__builtin_popcount` 則可以推出位移的過程中會產生幾次奇數需要做減 1 操作。

因此 `AAA` 為 `__builtin_popcount` ， `BBB` 為 `__builtin_clz` 。

## 測驗四
64-bit GCD (greatest common divisor, 最大公因數)
* 參考[Binary GCD](https://hackmd.io/@sysprog/gcd-impl#Binary-GCD)

#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 (XXX);
    return YYY;
}

此程式主要就在實作輾轉相除法。

binary gcd 的精神就是當兩數為偶數時，必有一 $2$ 因子。`shift` 同時去紀錄有幾個共同 $2$ 因子，直到一方變成奇數。接著不斷以 `v -= u;` 對 `v` 做操作，因此 `XXX` 為 `v`，脫離迴圈後則要利用 `shift` 補回先前右移的數值，因此 `YYY` 為 `return u << shift` 。

## 測驗五

在影像處理中，[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;
}

naive 程式碼中會去逐一檢查 `bitset` 中 bit 為 1 的個數，及位置為何，但其實我們在意的只有 bit = 1 的那些 bits ，直接使用迴圈去逐一檢查太沒有效率，因此以下利用 clz 改寫為效率更高且等價的程式碼:

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

`__builtin_ctzll` 會去計算出 LSB 離第 0 位元間的距離，透過此函式可以去知道最右邊的 bit 1 出現在哪個 bit。可以減少逐一檢查的操作時間，更有效率。

當我們利用 `__builtin_ctzll` 完成計算後得到 LSB 的位置之後，再進行下一次的計算之前需要將 bitset 的 LSB 消除，避免計算到同樣的位置，而 `bitset ^= t;` 的目的就是這個。因此 `t` 的二進位表示會是 LSB 的位置和 bitset 一樣，其餘 bits 都是 0，達到之後做 XOR 計算可以將 bitset 的 LSB 消除的效果，因此 `KKK` 為 `bitset & -bitset`。