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

[TOC]
## 測驗 1

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

程式流程如下:
1. 測試平台上有號數 ASR 是否行為正確
2. 測試輸入值正負號
3. 產生修正值
4. 修正值透過 or 修正原始值 shift 後新增的 bits

將 -1 向右 shift 後有無變號可知道 ASR 是否行為正確
`OP1 = (b) >> 1`
在 "ASR 不行為正確" 與 "輸入值為負" 時進行修正，fixu 為 -1 ，否則為 0
`OP2 = (c) m < 0`
將 fix 右側 設為 0 ，只留下左側 shift 數的 1 ，這樣 or 在一起後就會矯正 shift 補 0 的錯誤
## 測驗 2

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

若是 4 的冪次方，從右側開始在遇到 1 之前的 0 必須為偶數個，也就是 LSB 須為 0
`OPQ = (f) & 0x1`
## 測驗 3
num 若非 0 ，則必須進行 :
1. 消除所有 LSB 的 1
2. 向右 shift 到最高位的 1 來到 LSB
`AAA = (a) __builtin_popcount(num)`
`BBB = (b) __builtin_clz(num)`
## 測驗 4

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

處理其中一者為 0 的情況

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

將兩者的公因數 2 都先提出來，存在 shift

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

因為 2 被提出來了，接下來產生的公因數不會有 2 的成分，因此只要是偶數都可以 shift right 消除

        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (XXX);

減法結果存在 v ，會先變成 0
`XXX = (b) v`

    return YYY;
}

減出 0 時，減數會是公因數，再補上先前提出來的 2
`YYY = (e) u << shift`
## 測驗 5

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

找出最小的 1 的位置，寫入 out 移除那個 1 再重複步驟
`KKK = (e) bitset & -bitset`
因為在 two's compliment 與自己的負數做 and 會全是 0 除了最小 1 的位置會是 1
再與 bitset 做 exclusive or 就可移除最小的 1