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

## 測驗一

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

由於不知道該系統的 shift 是哪一種，而 asr_i 要當 m<0 時補 1 ，否則補 0 。
因此第三行的 `logical` 就是判斷負數的 shift 是補 1 還是補 0 （如果補 1 則還是負數，補 0 則會變成正數）
第四行的 `fixu` 則是判斷 `m` 是不是負數，如果 `m` 是負數且 `logical` 為 0 (shift 是補 0)，則需要特別處理，此時 `fixu` 會是 -1 也就是 `0xffffffff`。
第六行則會直接進行 shift ，並且使用 `fixu` 的數值，如果是 -1 則會把原本補 0 的地方變成 1 。如果是 0 則會直接沿用原本 shift 的結果。
因此 OP1 為 >> 1
OP2 為 m<0

## 測驗二

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

根據觀察，如果該數字為四的次方，則該數字為二的次方，且 tailing zero 為偶數。
其中 `(num & (num - 1))==0` 為判斷該數字是不是二的次方。
並且如果 tailing zero 的最後一 bit 為零，則代表其為偶數。
因此 & 0x1 可以判斷是不是基數，而將其反向就是偶數
因此 OPQ 為`&0x1`

## 測驗三
在題目 Number of Steps to Reduce a Number to Zero 中，每當最後的數字是 1 則需要兩次操作(先減一再除以二)，若是 0 則是需要一次操作(除以二)
因此全部需要的時間就是(全部的 1 )*2+(除了 leading zero 外的 zero )，而除了 leading zero 外的 zero 就是(32-(全部的 1)- (leading zero))
化減之後就是 32+(全部的 1 )-(leading zero)，但是因為最後一個 1 只要減 1 即可，不用除以 2 ，因此會少一步，也就是 31+(全部的 1 )-(leading zero)
也就是 31 + popcount - clz
因此 AAA 為 __builtin_popcount(num)
BBB 為 __builtin_clz(num)

## 測驗四

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