# 2020q3 Homework3 (quiz3)
contributed by < [`Noahnut`](https://github.com/Noahnut) >

### 測驗 1
第一題主要是要實作跨平台的 ASR
在不支援 `signed` right shift 的環境下，right shift 前面的位數是會補零，會導致結果與預期的不符，所以目標會是要將前面補 0 的位元反轉成 1 ，但如果要能夠跨平台就不能單純將前面為 0 的值補成 1。

測驗 1 的第一題為判斷現有環境是否不支援 `signed` 的 right shift，我們知道 `-1` 在 32 位元的架構下為 `0xffffffff`，如果在不支援 `signed` 的 right shift 的話，-1 就會變成正數。
所以 `OP1` 為 `>> 1`
`OP2` 從 `return` 那邊反推可以發現是 `m` right shift n bits 並與 `fix ^ (fix >> n)` 的 OR 運算，在這個題目是要將因 right shift 而補 0 的位元換成 1，所以 `fix` 在 `m` 為負數的情況下必須為 -1，而從 `OP1` 可以知道在不支援 `signed` 的 right shift 環境下， logical 會為 1，所以 `OP2` 要為 `m < 0`，判斷目前的計算是為在不支援 `signed` 的 right shift 環境下且 `m` 為負。

`OP1 = >> 1`
`OP2 = (m < 0)`

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

### 測驗 2
測驗 2 是要去實作判斷一個數是否為 4 的次方。

`(num & (num - 1))` 是用來判斷，如果這個數字是 4 的次方，轉成 2 進位後，必定只有一個字元為 1，而如果將這個數字減 1 ，二進位的這個數字就會退位。
例如：
4 為 `00000100` ， 4 - 1 為 3 (`0000011`)，而將這兩個數字做 and 操作就會為零。
這個操作就可以篩選掉非為 4 的倍數的數字。
觀察一下 4 的次方在二進位的規則
4 `00000100`
16 `00010000`
64 `01000000`
可以發現從尾巴到第一個出現的 1 ，出現的 0 都會是 2 的倍數，利用 `__builtin_ctzl` 這個函式來得到從最尾數到第一個 1 的數，如果非為 4 的次方跟 `0X1` 做 & 運算就會為 1。

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

### [LeetCode 1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer)

int bitwiseComplement(int N){
     if (N == 0) {
         return 1;
     } 
    unsigned int mask = 0xFFFFFFFF; 
    int leadingZeroNumber = __builtin_clz(N);
    mask = mask >> leadingZeroNumber;
    return ~N & mask;
}

這邊的解題想法為，只要將現有的數做補數運算，其餘原先的 leading Zero 不做改變，所以用 `__builtin_clz` 就可以算出原先的 leading Zero 多少，然後再將 `0xFFFFFFFF` 做 right shift leading Zero 的數量，在與 ~N 做運算就可以將因 NOT 運算的變成 1 的 leading Zero 變成 0。

### [LeetCode 41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)

### Golomb-Rice coding

### 測驗 3
這題是要解 LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero)
題目的意思是，給一32位元的 int 的數，給出需要多少次運算才能將這個數變成 0，而且在運算這個數的時候有以下條件，當這個正整數目前為偶數時，將其除於 2，當其為奇數的時候將其減 1。

如果很直覺的來想這個題目的解法的話，會是以下邏輯
> 數的奇偶用其 LSB 跟 `0x1` 做 & 運算來判斷
1. 如果數為偶數，就將其 right shift 等同於對這個數除於 2
2. 如果數為奇數，就將其 減 1

int numberOfSteps (int num){
    int count= 0;
    while (num != 0) {
        if (num & 0x1) {
            count++;
            num ^= 0x1;
        } else {
            count++;
            num = num >> 1;
        }
    }
    return count;
}

所以從上面這個邏輯來看，如果位元為 1 必定代表一次運算，因為要減 1，而在減 1 的運算下，並不會讓位元有任何移動，如果要讓數為 0 就必須要退位，所以答案就會是整個 int 位元為 1 的數加上這個數在 32 位元中佔幾位。
AAA 就為 `__builtin_popcount(num)` 代表這個數中有多少個 1 位元
BBB 就為 `__builtin_clz(num)` 代表這個數從右邊數來要多少個 0 才會遇到 1。
個人覺得改寫成這樣比較直觀

return num ? 31 - __builtin_clz(num) + __builtin_popcount(num)  : 0;

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

### 測驗 4
在閱讀過 [Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/) 和 [Greatest Common Divisor 特性和實作考量](https://hackmd.io/@sysprog/gcd-impl) 後可以知道，GCD 的 x 與 y 在不同奇偶下會有不同特性。

1. x 跟 y 都為偶數

$gcd(x, y) = 2 * gcd(x/2, y/2)$

2. x 為偶數，y 為奇數

$gcd(x, y) = gcd(x/2, y)$

3. x 為奇數，y 為偶數

$gcd(x, y) = gcd(x, y/2)$

4. x 為奇數，y 為奇數

$gcd(x, y) = gcd((x - y)/2), y)$

並在搭配 $gcd$ 的性質
* $gcd(x, y) = gcd(y, x)$
* $gcd(x, 0) = |a|$
* $gcd(x, y) = gcd(x, x \% y)$

來閱讀測試的程式

for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
}

這一段的程式主要是在判斷 `u` 與 `v` 是否都是偶數，如果都是就將其除與 2 並根據第一個性質，所以我們要把除於 2 的次數存在 `shift` 的這個變數。

while (!(u & 1))
        u /= 2;
.....
while (!(v & 1))
        v /= 2;

當 `u` 或 `v` 為偶數時，根據性質，要單獨將其除於 1。
在 `while` 中的運算就為輾轉相除法的部分，而 `XXX` 的部分，會發現 `v` 會是 `u - v` 的值，所以如果當滿足 `u = v` 時，`v` 就會為零所以 `XXX` 會是 `v`。
而 `YYY` 從第一個性質可以知道最後我們算出來的 `u` 還必須在乘於在一開始我們除的 2 的倍數才會是我們的最大公因數，所以 `YYY` 是 `u << shift`。

### 測驗 5
這題的目的是要找到所有為 1 的 bit 在這個 bit array 的位置。
在最原本的實作中是對每個 bitset 去向右 shift 並對其與 `0x1` 做 & 運算，如果為 1 就將其位置記錄下來。
而效率更高的做法為利用 `__builtin_ctzll()` 計算從 LSB 到第一個出現的 1 中 0 的數量，所以當我算完一個 1 的位置，就要讓其變成 0，這樣才能找到下一個 1 的位置，所以 KKK = `bitset & -bitset` 並將其與 ` bitset ^= t` 做運算就可以將最右邊為 1 的 bit 變成 0。