2020q3 Homework3 (quiz3)

contribute by < simpson0114 >

tags: `sysprog2020`

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

這段程式碼是要判斷所做的位移是 logical shift 還是 arithmetic shift 並且輸出位移的結果。

OP1

function 內的第一行是要判斷所進行的運算是 logical 還是 arithmetic shift ，因為 logical right shift 和 arithmetic right shift 時對於 -1 所補的 bit 分別為 0 和 1，由此可由 > 0 與否判斷為何種 shift ，因此 OP1 =

(b) >> 1

OP2

function 內第二行是要判斷是否同時為 arithmetic right shift 和 m 為負數，若同時成立，則 fixu -1 ，否則 fixu 為 0 ，因此 OP2 =

(c) m < 0

測驗`2`

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

本題要測試輸入是否為 4 的倍數

OPQ

因為若 num 為 4 的倍數 __builtin_ctz(num) 會 >= 2 ，因此要使得 (__builtin_ctz(num) OPQ) = 0 ， OPQ =

(f) & 0x1

測驗`3`

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}

這段程式碼是要判斷用以下的規則，要幾步才可將 num 變成 0 ，若 num 為奇數則 -1 ，若為偶數則 / 2 。

以 14 為例：
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
output = 6

換言之，上述等同於「若尾數為 1 則需進行一次運算，若尾數為 0 也須進行一次運算，直到二進位數等於 0 。」
由此可知， leading zero 不須進行計算，所以可以用( 31 - leading zero 數) 來判斷非leading zero 的數量，剩下的位元必定要進行一次計算，而若位元為 1 ，因為 -1 後位元為 0 ，所以必須進行兩次計算，因此要再把位元數為 1 的個數加進去。

AAA

因為要把位元數為 1 的個數加進去，因此 AAA =

(b) __bultin_popcount(num)

BBB

因為要判斷非 leading zero 的數量，故 BBB =

(b) __bultin_clz(num)

測驗`4`





















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

這題在實做不用餘數的 GCD ，它所用的方法是用除法跟減法取代之，程式碼的 3、4 行是先將兩數共同的 2 的倍數除掉，最後面再加回來， 6 到 20 行則是先將另一數多餘的 2 除完，再將兩數相減，直到較小之數 v 為 0 為止，最後 19 行再將較大之數 u 把共同 2 的倍數利用左移乘回來。
因此， XXX =

(b) v

YYY =

(e) u << shift

測驗`5`

while (bitset != 0) {
    uint64_t t = KKK;
    int r = __builtin_ctzll(bitset);
    out[pos++] = k * 64 + r;
    bitset ^= t;                           
}

由 while 的條件式可判斷此迴圈要 bitset == 0 時才會跳出，因此每處理完一個 bit 後就要將最右的 bit 變成 0 ，又因最後要 ^= t 所以 t 必須是最右邊的 bit 等於 bitset 最右邊的 bit ，所以 KKK =

(e) bitset & -bitset