# 2020q3 Homework3 (quiz3)
contributed by < `jeremy3951` >
###### tags: `(2020q3)進階電腦系統理論與實作`
## 測驗 `1`
填補下面的程式碼 :
```cpp
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));
}
```
### 解答分析 :
失敗的算術右移 :
```graphviz
digraph struct{
node[shape="record"]
1[label="1|1|1|0|1"]
l2[label="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](https://leetcode.com/problems/power-of-four/)，假設 int 為 32 位元寬度。實作程式碼如下:
```cpp
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
用二進位來表示 :
2^2^ -> 2^4^ -> 2^6^ -> 2^8^ -> 2^10^
由上述觀察可以發現的特性 :
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](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
請補完程式碼
### 解答分析 :
要填補上述的程式其實很簡單 , 帶幾次數字後就可以得知答案為
AAA=(a) BBB=(b) , 不過運作原理需要再想想
### 運作原理 :
題目的步驟 :
```cpp
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 區 :
$\underline{0000000000} \ \underline{111001101011} \ \underline{0000000000}$
第一區 : clz
第二區 : popcount * 2 - 1 + 中間的 0 個數
第三區 : ctz
答案 : 第二區 ＋ 第三區
最後發現第二、三區的 0 可以算在一起 , 這些數字再加上 popcount 等價於 32 - clz
這時候第三區都算進去了 , 第二區剩下 popcount - 1 , 把這項加進去 : 32 - clz + popcount -1 = popcount + 31 - clz
上述的式子就是此題的答案了！
## 測驗 `4`
填補下面的程式碼 :
```cpp
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) 廣泛使用，考慮以下程式碼:
```cpp
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 改寫為效率更高且等價的程式碼:
```cpp
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;
}
```
請補完程式碼
### 解題分析 :
其實這題的解答在第三題的題目講解就劇透了( ~~不知道是巧合還是?~~ )
> 總是要讓學員偶爾占到好處，學員才會想繼續看下去，人性操作
> :notes: jserv
比對修改前和修改後的程式後我發現只有以下的程式碼不太一樣 :
```cpp
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
```
這個迴圈針對 `bitset` 的 LSB 做判斷後再決定要不要寫入 out[] 裡面 ,
改版後的程式碼 :
```cpp
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`
Sign in with Wallet
Connect another wallet