2020q3 Homework3 (quiz3)

contributed by < mickey30606 >

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

第3行判斷在負數的狀況下，系統做向右推移(>>)時，會補0或是補1，若補0的話那推移後會變成正數(不是我們想要的結果)，需要再做操作。
再來，若系統是補0的話，我們要想辦法把補的0變成1。所以我們可以想辦法做一個mask，他推移多少，我們的mask從MSB算來就有多少個1，而且其他的bit必須要為0。
先設一個全部bit為1的數(也就是-1)，看那個負數推移多少，我也用-1推移多少，然後在用-1去XOR推移完的數即可取的我們要的mask，最後再與m >> n進行OR的運算即可取得我們的答案。

這邊不能用NOT運算，因為若系統是補1的話，fixu會等於0，如果直接做NOT會使結果全部變成-1。

第4、5、6行就是在講上述的操作，第4行確認對負數系統是補0而且m為負數時，fixu會等於 -1。而第5行，把fixu轉為int的型態存入fix中（為了確保推移一定是補0)，而第6行的OR右半邊就是在做mask。

測驗 2





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

若要是
$4^{m}$ ，必定滿組下面條件
- 此數要大於 0 。(num > 0)
- 若以二進位表示，只會有 1 個 bit 是 1 。((num & (num-1)) == 0)
- 若以二進位表示，後面 0 的數量一定是偶數。(!(__builtin_ctz(num) & 0x1))

測驗 3




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

這個操作可分兩個步驟
1. 如果LSB是 0 ，除 2 。
2. 如果LSB是 1 ，減 1 。
所以只要計算包含最靠近MSB的1後有幾個 bit，在加上總共有幾個 1 就可以了。

測驗 4






















#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 (v);
    return u << shift;
}

使用輾轉相除法來取得最大公因數。
第5～7行，把兩個要操作的數字共同除2，並紀錄共同相除的次數在最後的時候把他乘回去。
8～9行和11～12行做的事一樣，因為在5～7行已經確定兩者其中一個數字已經不是2的倍數了，所以可以在程式進行中，能被2除的話就被2除，能增進程式的效率，實測若註解掉這兩行，不影響程式進行。
第13～19行在進行輾轉相除法，並確保 u 一定會大於等於 v 。

測驗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把他想辦法弄掉。
因為 2's complement 的操作會把由右至左，最先找到的1保留，然後把左邊剩下的全部做 not ，所以我只要讓原本的數字變負數，再把他 and 原本的數字，就只會留下最先找到的1，再把他拿去和原本的數字做 xor 就可以達到我們的目的。