# 2020q3 Homework3 (quiz3)
contributed by < `Sisker1111` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz3)
>
## 1. ASR
考慮到程式碼的相容性，目的是實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:
`-3 是 (-5) / 2 的輸出，並往負無限大的方向前進`

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

* logical 是用來判斷 compiler 的 >> 是 logical shift 還是 arithmetic shift.
* 若是 arithmetic shift ， logical 會是 0 且 fixu = 0，第 6 行的`fix ^ (fix >> n)`會變成`2b'000.....0 ^ 2b'000.....0 = 2b'000.....0`(不影響結果)
* 若是 logical shift ， logical 會是 1 且 fixu = 111.....1( 32 個 1)，第 6 行的`fix ^ (fix >> n)`會變成`2b'111.....1 ^ 2b'000.....1 = 2b'111.....0`( 1 的數量等同 n)
## 2. int __builtin_ctz & int __builtin_clz

>Built-in Function: int __builtin_ctz (unsigned int x)
>* Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
>
>Built-in Function: int __builtin_clz (unsigned int x)
>* Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

用 __builtin_ctz 來實作 LeetCode [342 . Power of Four](https://leetcode.com/problems/power-of-four/)，假設 int 為 32 位元寬度。實作程式碼如下:

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

此題是要確認該數字是否為 4 的冪次方，若該數為 4 的冪次方 32bits 中只會有 1 個 bit 為 1 且該 bit 右邊的 bits 數量應該偶數個，`num > 0 && num & (num-1)`首先確認該數是否為正數且只有 1 個 bit 為 1，`!(__builtin_ctz(num) & 0x1)`則是在判斷右邊0的數量是否為偶數個.
### 不同的實作
`(num & (num - 1))==0`的部分可以使用`!(__builtin_popcount(num) ^ 1)`來代替，原本想用 `__builtin_clz(num)` 來代替`num > 0`，但會因為 undefined behavior <s>噴 compiler error</s>.
:::danger
避免說「噴 compiler error」這樣不精準的話，因為
1. 閱讀者無法區分是 internal compiler error (ICE，在 gcc 開發過程中常見)，抑或是你遇到編譯器拋出的一般錯誤訊息;
2. 漢語的「[噴](http://dict.revised.moe.edu.tw/cgi-bin/cbdic/gsweb.cgi?ccd=it446W&o=e0&sec=sec1&op=v&view=0-1)」意義和上述的編譯器行為無涉;

你可額外加上 `num > 0` 的檢查條件，置於 clz 呼叫之前
:notes: jserv
:::

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

int bitwiseComplement(int N) {
        if(!N)
            return 1;
        int offset = (1 << (32-__builtin_clz(N)) ) - 1; 
        return N ^ offset ; 
}

* Runtime : 0 ms, faster than 100.00% of C++ online submissions.
Memory Usage : 6.1 MB, less than 40.99% of ...

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

 int firstMissingPositive(vector<int>& nums) {
        
       if(nums.size()==0) return 1;
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0 && nums[i] <= nums.size()){
                int pos = nums[i]-1;
                if( nums[pos] != nums[i]){
                    nums[pos] ^= nums[i];
                    nums[i] ^= nums[pos];
                    nums[pos] ^= nums[i];
                    i--;
                }
               
            }
        }
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i]!=(i+1))
                return i+1;
        }
        
        return nums.size()+1;
    }

* Runtime : 4 ms, faster than 79.63% of C++ online submissions.
Memory Usage : 9.9 MB, less than 49.44% of ...

## 3. __builtin_popcount
針對 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;
}

32 bits 內的 bit = 1 的數量等同要執行 subtract 的次數，因此可以很容易之道`AAA`的答案應為`__builtin_popcount(num)`，執行完`__builtin_popcount(num)`後我們還需要向右移動 1 個 bit，透過`__builtin_clz(num)`我們可以找到最左邊的 1 在哪個位置，找到後用
`31-__builtin_clz(num)`就可以知道應該向右 shift 幾次，所以 `BBB`為`__builtin_clz(num)`.

## 4. 64-bit GCD
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

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

1. 5~7 行檢查 u、v 是否皆為偶數(或是講是否能一起除以2)，因為`gcd(u,v) = 2*gcd(u/2,v/2)`
2. 8~10 行檢查 u 是否為偶數，如果 u 為偶數則 v 為奇數，所以`gcd(u,v) = gcd(u/2,v)`
3. 11~12 行檢查 v 是否為偶數，如果 v 為偶數則 u 為奇數，所以`gcd(u,v) = gcd(u,v/2)`
4. 然後剩下的其實就是輾轉相除法，並且會確保進入下一個迴圈的 v 是比較小的那個值，重複直到進入這次輾轉相除時的 u 和 v 相同，因此 `XXX = v`
5. 最後 return 要把 gcd 往左邊 shift 最開始除以2的次數，才能得到正確的值，固`YYY = u << shift`.

### 透過 __builtin_ctz 改寫
注意到下面的實驗中會將 quiz3 中題目的作法命名為 fast gcd，使用 __builtin_ctz 調整後的版本則稱為 faster gcd 以方便解釋。

前面的 `for (shift = 0; !((u | v) & 1); shift++)` 迴圈可以使用 __builtin_ctz 來改寫為如下:

#ifndef min
#define min(x, y) ((x) < (y) ? (x) : (y))
#endif

uint64_t faster_gcd64(uint64_t u, uint64_t v){ 
    if (!u || !v) 
        return u | v;
    
    int shift = min(__builtin_ctz(u), __builtin_ctz(v));
    u >>= shift; v>>= shift;
    
    while (!(u & 1)) 
        u >>= 1;
    do {
        while (!(v & 1)) 
            v >>= 1;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }   
    } while (v);
    return u << shift;
}

## 5. bit array
在影像處理中，[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;
}

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

看向原 Code 第 9 行，目的是要從最右邊的 bit 開始 check 是否為 1，下面改寫的版本把 for 改成 while，`bitset & -bitset`是把 `bitset` 與 `-bitset` 的 2 的補數做 & ，這樣即可得到最右邊 bit 數為 1 且其他 bits　皆為 0 的 bitmap，最後第 12 行是用來將最右邊 1 改為 0，這樣下次`__builtin_ctzll(bitset)`就不會找到錯誤的 bit .