Try   HackMD

2020q3 Homework3 (quiz3)

contributed by < jeremy3951 >

tags: (2020q3)進階電腦系統理論與實作

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

解答分析 :

失敗的算術右移 :







struct



1

1

1

1

0

1



l2

0

1

1

1

0



1->l2

-3 位移完變 +14 .
為了避免這種情況發生 , 我們要讓負數右移後新的 bits 變成 1 .
運作原理 :　根據 ｍ 的正負來決定右移後要補 ０ 還是 １ .

根據運作原理來觀察這行程式碼 (m >> n) | (fix ^ (fix >> n)) 可以得知在 m 位移完後 , 要用 fix 來修改位移後的新 bits .

首先觀察 logical 這個變數會發現它不是 0 就是 1 , 再看到
unsigned int fixu = -(logical & (OP2)) , 如果此時把 logical=0 帶進去後 :
fixu=0 -> fix=0 -> return (m>>n)|0 ( 沒有動到 m>>n )
這樣代表當 logical=0 的時候是正常狀況不用做修改
這時我們知當 logical=1 的時候就是我們要做修改的時候了 .

此時回來看第一行 (((int) -1) OP1) > 0; 若 logical=1 則 -1 經過 op1 後要 >0 , 選項 ( c )~( g ) 都會隨著 input 而有不同的正負值 , 所以可以去掉 , 選項( a ) 會讓 logical=0 , 所以 op1 的答案是 ( b ) >>1 .

根據 op1 的答案我們會發現 -1 經過算術右移後變成了正數 , 想必是用 0 來當作左邊的新 bits , 所以這時候才有修改的必要 .
接下來再看回 unsigned int fixu = -(logical & (OP2)) , 推測 fixu 的值不是 -1 * 0 就是 -1 * 1 , 這時我們看 -1 * 1 這條支線可以推得 logical & op2=1 也就是 1 & op2 =1 , 所以 op2 就是 1 根據這個答案從選項中只剩 (m>0) 和 (m<0) 可以選 , 這時回頭看我們的假設是建立在需要修改的時候做更動 , 也就是 "負數做右移的時候補0當作新的 bits" , 從這個假設可得知我們的 m 要小於 0 才符合我們的假設 , 故 op2 選 ( c )

測驗 2

題目 :
利用 __builtin_ctz 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:

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

題目要求的是 4 的次方數 .

解題分析 + 運作原理

觀察 (num & (num-1))==0 , 帶幾個數字進去 trace 後發現這個條件式是在篩選 num 是不是只有 1 個 bit ?

觀察 4 的次方數 :
4 -> 16 > 64 -> 256 -> 1024
用二進位來表示 :
22 -> 24 -> 26 -> 28 -> 210
由上述觀察可以發現的特性 :

  1. 在二進位表示法中只有 1 個 bit
  2. 經由 __builtin_ctz return 的值都是偶數(2,4,6,8…)

根據上面的特性寫的特性 , 對應的條件式如下 :

  1. (num & (num-1))==0
  2. !(__builtin_ctz(num) OPQ)

由此可知 OPQ 就是偵測 ctz return 的結果是否為偶數(搭配前面的 !) ,
OPQ 要填 ( f ) 0&1

測驗 3

題目 :
針對 LeetCode 1342. Number of Steps to Reduce a Number to Zero，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:

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

請補完程式碼

解答分析 :

要填補上述的程式其實很簡單 , 帶幾次數字後就可以得知答案為
AAA=(a) BBB=(b) , 不過運作原理需要再想想

運作原理 :

題目的步驟 :

while(num)
    (num 為偶數 ? )除 2 : 減 1 ;

除 2 相當於往右 shift 1 個 bit ; 減 1 相當於把 LSB 設為 0.

我最初的想法 :
每個 1 都會被設為 0 並且位移 (除了最後一個 bit)
所以把 1 的個數 * 2 減 1 再加上這些 1 中間有幾個 0 再加上右邊有幾個 0 就是答案

照我上面的想法 , 這樣會需要 clz , ctz , popcount 來做運算 , 而且還不知道怎麼算中間的 0 , 跟老師的作法比起來既多一個 function 要呼叫 , 又要算出這些 1 之間的 0 …

後來我換個角度來分析 , 把 num 分 3 區 :

0000000000― 111001101011― 0000000000―

第一區 : clz
第二區 : popcount * 2 - 1 + 中間的 0 個數
第三區 : ctz
答案 :　第二區　＋　第三區

最後發現第二、三區的 0 可以算在一起 , 這些數字再加上 popcount 等價於 32 - clz
這時候第三區都算進去了 , 第二區剩下 popcount - 1 , 把這項加進去 :　32 - clz + popcount -1 = popcount + 31 - clz
上述的式子就是此題的答案了！

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

運作原理 :

先把兩數共同的 2 次方因數提出來 , 做完輾轉相除法後 , 把公因數乘上該 2 次方因數(藉由 shift 的方式)

程式分析 :
先看 for 迴圈裡的判斷式 : !((u | v) & 1)
&1 代表只跟最右邊的 bit 做 & 運算 , 再觀察回圈內的行為(u 和 v 都除 2) , 所以推斷得出此行程式碼在看是否 u 和 v 均為偶數 .
如果 u 或 v 其中一個為奇數就會跳出迴圈.

此時的狀態 : 2 已經不再是當下的 u 和 v 的公因數了(因為其中一者是奇數)
所以這時先把 u 用成奇數再進 while 迴圈 .
在迴圈裡的行為就是把 v 用成奇數 , 然後作輾轉相除法後就結束了 .

解題分析 :

XXX : 由於 do while 迴圈內還有一個迴圈就是看 v 的最後一個 bit 決定它是不是偶數 , 但是如果 v 當下為 0 的話 , 這個迴圈就跑不停了 , 所以 XXX 一定要做到偵測 v 為 0 的時候就停止運作 , 故這題選擇 ( b ) v

YYY : 根據前面的運作原理 , 求完公因數後還要再 shift 原本的 2 次方公因數 , 所以選 ( e ) u << shift

測驗 5

題目 :
在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

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 改寫為效率更高且等價的程式碼:

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

請補完程式碼

解題分析 :

其實這題的解答在第三題的題目講解就劇透了( 不知道是巧合還是? )

總是要讓學員偶爾占到好處，學員才會想繼續看下去，人性操作

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

比對修改前和修改後的程式後我發現只有以下的程式碼不太一樣 :

for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }

這個迴圈針對 bitset 的 LSB 做判斷後再決定要不要寫入 out[] 裡面 ,

改版後的程式碼 :

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

先看第二行得知 r 可以知道 bitset 的右邊還有幾個連續 0 , 再跳到第四行看到 bitset 被 t 改變了後進行下一輪 , 這時一樣是看當下的 bitset 的右邊有幾個 0

看到這裡可以推測 , t 可以改變 bitset 的樣子 , 甚至讓 ctz return 的值都不一樣 , 再看一下迴圈的條件 , 就可以推得 :
bitset 最右邊 1 的每次都會被設成 0 !

然後我又想起第三題的某段補充 :

類似的操作還有 x & -x，將 x 的 LSB 取出 (isolate LSB)

由這段得知這個方法
所以這題選 ( e ) bitset & -bitset

Last changed by 
 
jeremy3951
1
340
Published on HackMD