# 2020q3 Homework3 (quiz3)
contributed by < `StevenChen8759` >
###### tags: `linux2020`
> 相關連結：
> [2020秋季進階電腦系統理論與實作 quiz3](https://hackmd.io/@sysprog/2020-quiz3)
> [2020秋季進階電腦系統理論與實作 quiz3 作業說明](https://hackmd.io/@sysprog/B12ftyoBD)
> [2020秋季進階電腦系統理論與實作 quiz3 作業繳交區](https://hackmd.io/@sysprog/2020-homework3)
> [color=green]
## :radio_button: 測驗一
```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));
}
```
### :building_construction: 程式碼分析
* 根據邏輯右移的規則，若我們將一個 int 型別的負數右移，則根據二補數的表示特性，該負數將變成正數，明顯不符原題目對於算術右移的規則。
* 因此，我們在 return 的部分增加了 `bitwise or` 項目，調整邏輯右移為算術右移。
* 我們參考 `-5 算術右移 1` 以及 `-5 算術右移 2` 運算，比較算術右移與邏輯右移的結果:
```verilog
logic_rs_1: 32'hFFFF_FFFB -> 32'h7FFF_FFFD
arith_rs_1: 32'hFFFF_FFFB -> 32'hFFFF_FFFD
logic_rs_2: 32'hFFFF_FFFB -> 32'h3FFF_FFFE
arith_rs_2: 32'hFFFF_FFFB -> 32'hFFFF_FFFE
```
* 進一步比較最高 4 位元的結果，可發現邏輯右移與算術右移的差異主要在於高位元的不同:
```verilog
logic_rs_1 (Highest 4 bits): 4'b0111
arith_rs_1 (Highest 4 bits): 4'b1111
logic_rs_2 (Highest 4 bits): 4'b0011
arith_rs_2 (Highest 4 bits): 4'b1111
```
* 經過上述的觀察，不難發現邏輯右移後須進行 `sign extension` 以符合算術右移的要求，且擴充的位元數恰等於邏輯右移的位元數。
* 綜合上述結論，在 m 為非負數的時候，我們不需要執行 `sign extension` 即可讓邏輯右移達成算術右移的要求，因此我們須限制 return 的 or 之 `(fix ^ (fix >> n))` 全零，又因為 `logical` 變數的指派為比較運算的結果，其值必定為 0 或是 1，因此我們可以得知 `OP2` 為 `m < 0`。
* 我們再回頭分析 `(fix ^ (fix >> n))`，因為這段運算需指出高位元需做 `sign extension` 的 bit 數，而其餘位元保持不變，因此我們根據上述的例子歸納出 `or mask` 的確切值:
```verilog
32'h7FFF_FFFD | 32'h3FFF_FFFE
or ) 32'h8000_0000 | or ) 32'hC000_0000
------------------- | -------------------
32'hFFFF_FFFD | 32'hFFFF_FFFE
```
* 透過上述的 `sign extension` 觀察，我們推導出下列的 `or mask` 計算過程 (以 `-5 算術右移 2` 為例):
```verilog
32'hFFFF_FFFF
xor ) 32'h3FFF_FFFF (右移兩個位元)
------------------------
32'hC000_0000
```
* 因此可知 `fix` 之值在 `m < 0` 時為 `32'd-1`，因此 `logical` 之值為 1。
* 根據 2 補數的特性，-1 邏輯右移 1 個位元作大於 0 比較才可保證 `logical` 之值為 1，故 `OP1` 為 `>> 1`
```cpp
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) >> 1) > 0;
unsigned int fixu = -(logical & (m < 0));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
## :radio_button: 測驗二
```cpp
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
### :building_construction: 程式碼分析
* 根據數值系統的特性，若一個數 $x$ 為 4 的羃次時 (假設 $x = 4^n$)，則從 $x$ 之二進位表示法的 LSB 算起，連續 0 個數必恰為 $2n$ 個。參考下列 4 羃次的 2 進制表示法:
```verilog
16'd4 -> 16'b0000_0000_0000_0100 (n = 1)
16'd16 -> 16'b0000_0000_0001_0000 (n = 2)
16'd64 -> 16'b0000_0000_0100_0000 (n = 3)
16'd256 -> 16'b0000_0001_0000_0000 (n = 4)
16'd1024 -> 16'b0000_0100_0000_0000 (n = 5)
...
```
* 除了上述的特性外，根據二進制的特性可發現若一個數 $n$ 為 4 的羃次，則 $n$ 在二進位表示方法中必定只會出現一個 `1`。
* 因此 `n & (n - 1)` 必等於 0。
* 又因輸入的數為 `signed`，綜合上述判斷式得到下列的邏輯判斷陳述式:
```cpp
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
```
* 根據上述推論，`__builtin_ctz(num)` 之值在輸入 num 為 4 的羃次的狀況下，其回傳值必定為偶數，因此我們透過位元運算判定 `__builtin_ctz(num)` 是否為偶數。
* 考量完整的偶數判定陳述式 `!(__builtin_ctz(num) OPQ)` ，當 `__builtin_ctz(num)` 為偶數時，括號內部值須為 0 才能輸出正確結果，因此 `OPQ` 應為 `& 0x1`
## :radio_button: 測驗三
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
### :building_construction: 程式碼分析
* 這段程式碼主要計算 [Leetcode No.1342](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/) 的計算次數。
* 在輸入 0 時因二進制表示法不含任何 1，因此直接回傳 0。
* 根據二進制表示法的特性，因 leading zero 的個數最多為 31，考量 leading zero 個數為 31 的時候，此時 num 必為 1，popcount 值亦為 1，其計算次數為 1 次。
* 接著我們考慮 num 為 2 的羃次之 case (假設為 $2^k$)。
* 當 num = 2 時，需計算 2 次 (clz = 30)。
* 當 num = 4 時，需計算 3 次 (clz = 29)。
* (以下類推)
* leading zero 所造成額外的計算次數隨著 leading zero 數量的增加而減少，因此我們扣除 leading zero 的數量，BBB 應填 `__builtin_clz(num)`
* 接下來我們討論 popcount 對計算次數造成的影響，以 8、12、14、15 為例。
* num = 8, clz = 28, popcount = 1, 計算 4 次
* num = 12, clz = 28, popcount = 2, 計算 5 次
* num = 14, clz = 28, popcount = 3, 計算 6 次
* num = 15, clz = 28, popcount = 4, 計算 7 次
* 根據歸納的結果，popcount 增加 1，則在計算的過程就需要多一次 -1 的計算，因此 AAA 應為 `__builtin_popcount(num)`。
## :radio_button: 測驗四
```cpp
#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 (XXX);
return YYY;
}
```
### :building_construction: 程式碼分析
* 第一個 for 迴圈必定執行至 u 與 v 至少一數為奇數時停止，而這樣的特性會使迴圈跳離後的 u 與 v 互質，即其最大公因數為 1。
* 根據 [Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity)，$gcd(a,b) = 1 \iff sa+tb=1, \exists \ s,t \in \mathbb{Z}$，我們可在原始的 u, v 皆為偶數的情況下將兩數持續除 2，直到至少一數為奇數時停止，而最後再針對計算出來的 gcd 左移除 2 的次數進行還原，得到原始的 gcd。
* 在第二個 `while` 迴圈裡面，針對經過前一迴圈處理後仍為偶數的 u 再行除 2，直至 u 為奇數，因為在先前的 for 迴圈處理後 u, v 已互質，因此再將 u 除以 2 並不會改變兩數互質的特性；除此之外，令數字更小可再減少計算的次數。
* do-while 迴圈內針對變數 v 操作的 while 迴圈亦同。
* 我們接續看到 do-while 迴圈內的 if 判斷式，此處應用了輾轉相除法的概念，並移除了 mod 運算，單純利用一連串的加減法與除二運算 (即右移一位元) 可使運作效能更佳。
* 觀察迴圈對變數 v 的操作，可發現迴圈在輾轉相除的過程中，除了 u > v 以外，被減的結果皆放在變數 u，而輾轉相除法的減數會放在變數 v。
* 在輾轉相除的過程中，v 最後將會歸零。
* 因此跳離迴圈的條件是 v > 0，故 XXX 填入 v
* 而最後迴圈返回時，如同前述所說需還原原始 gcd，故 u 需左移 shift 個位元，YYY 填入 u << shift。
## :radio_button: 測驗五
```cpp
#include <stddef.h>
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]; // traverse all elements
size_t p = k * 64; // offset of bitmap
// bitwise value check (1)
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i; // Indicate is-one index
}
}
return pos;
}
```
```cpp
#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;
}
```
### :building_construction: 程式碼分析
* 根據函式 `naive()`，最終回傳的變數 `pos` 值指出此 bitarray 所含 1 的個數，且陣列 `out` 內含值指出哪一個位元的值為 1。
* 在函式 `improve()` 中使用了 `__builtin_ctzll(bitset)` 函式，直接計算 tailing zero 的個數，可直接得到 offset 的位置並加速 `naive()` 的計算。
* 在每一次計算之後，tailing zero 前方的 1 須設定為 0，在新的實現中是採用 xor 運算設定該位元為 0。
* 根據二補數的特性，一數與其二補數做 bitwise and 運算，其結果中必定只包含 1 個 1，且其位置與原數從 LSB 數來的第一個 1 的位置相同。
* 因此，我們運用這個特性，可知 KKK 應為 `bitset & -bitset`。
Sign in with Wallet
Connect another wallet