# 2020q3 Homework3 (quiz3)
contributed by < `OscarShiang` >
## 作業要求
- [ ] 重新回答[第 3 周測驗題](https://hackmd.io/@sysprog/2020-quiz3)，連同附帶的「延伸問題」。
## 測驗 `1`
因為在 ISO/IEC 9899:TC2 6.5.7 有提到
> “The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a **negative value**, the **resulting value is implementation-defined.**”
所以在本題中我們嘗試實作出一款無論編譯器實作是算數位移還是邏輯位移都適用的 arithematic right shift 函式 `ars_i`
```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));
}
```
實作的想法是這樣的：因為我們想要計算的是算數位移的數值，所以若編譯器針對一個 `int` 負值進行右移的實作是邏輯位移的話，我們就將右移產生的 `0` 修改為 `1`。
例如我們對 `-5` 進行位移，若假設其只有 4 個位元的話，在二進位的表示則是 `1011` 若位移後得到 `0101` 也就是 5，我們只需要在剛才因為邏輯位移而產生的 `0` 改為 `1` 就會得到 `1101` 也就是我們要的 -3
所以在第一步的時候，我們需要先確認目前編譯器針對負數右移的行為是算數還是邏輯的位移，因此我們可以知道 `logical` 就是用以判斷位移的種類，所以 `OP1` 需要是
> OP1 = `>> 1`
才能知道在我們當前使用的編譯器是不是採用邏輯右移的實作方式
而在 ISO/IEC 9899:TC2 6.5.8 Relational operators 中提到
> Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false. The result has type int.
因此可以知道 `logical` 的值應為 0 或是 1，於此對應 `fix` 的數值應為 -1 與 0
若 `fix` 是 -1 且假設使用 4 個位元來表示一個整數的話，則
```
(fix ^ (fix >> n))
```
就會是
```
(1111 ^ (1111 >> n))
```
因為我們已經使用 `logical` 確認編譯器的行為是邏輯位移，所以在右移 n 位的情況下就會形成一個用來補償 most significant bits 的 bit pattern，所以根據用途 `OP2` 應該為
> OP2 = `m < 0`
## 測驗 `2`
本測驗的用意是在使用 `__builtin_clz`, `__builtin_ctz` 等 [GCC extensions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 來實作出判斷給定數值 `num` 是否為 4 的冪。
相關的實作如下：
```cpp
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1)) == 0 &&
!(__builtin_ctz(num) OPQ);
}
```
在 `return` 的敘述這邊有三個條件用以判斷該數值是否符合 4 的冪：
1. `num > 0`: 用以判斷該數值為正
因為 $4^n \geq 1, \ when \ n \geq 0$
2. `(num & (num - 1))`: 用以判斷給定數值是否為 2 的冪
這個部分要以 bitwise 的角度來看，因為如果 `num` 是 3，而在二進位則表示為 `011`， `num - 1` 則為 `010`，進行 AND 運算後則得到 `010` ，運算結果不為 0
若 `num` 是 4 的話，則二進位為 `100`， `num - 1` 則為 `011` 進行 AND 運算後則為 0。因此可以知道該運算是用以判斷
3. `!(__builtin_ctz(num) & 0x1)` 則是用來判斷在該數是 2 的冪次的情況下是不是屬於 4 的冪次
因為我們在第二個判斷式已經知道該數值為 2 的冪次，因此可以知道該數在二進位的表示中，只有一個 bit 為 1。我們知道 4 的冪次在表示為 2 的次方時可以寫為 $2^{2n}, \ n \geq 1$，也就是說我們在使用 `__buitin_ctz` 的時候，如果該數值是 4 的冪次則 `__builtin_ctz` 計算出來的數值就會是一個偶數。因此只要我們判斷 `__builtin_ctz` 的結果為奇數的話，該數就只是一個 2 的冪次，如果計算結果是偶數的話，給定的該數就會是一個 4 的冪次。
因此在本題中，`OPQ` 的答案就會是
> OPQ = `& 0x1`
## 測驗 `3`
本題的敘述如下：
> Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
我們可以給定一個數字 `14` 來嘗試看看
- 14 是偶數，所以我們將其除以 2 ，得到 7
- 7 是一個奇數，所以我們將其減 1，等於 6
- 6 是偶數，所以將其除以 2 得到 3
- 3 是奇數，減 1 得到 2
- 2 是偶數，除以 2 得到 1
- 1 是奇數，減 1 得到 0
考慮到 14 的二進位表示法為 `00001100`，若我們將除以 2 這個操作以向右位移來思考的話，表示我們對該數進行了 4 次向右位移，2 次減 1 的操作，因此我們可以將該題的操作過程轉換為二進位的角度來敘述
> 如果最右邊的位元為 1 時，將該數減 1；若最右邊的位元是 0，則將該數向右位移一位
因此我們可以透過 `__builtin_clz` 得知 MSB 在哪個位元，並從而得知我們需要位移幾次；並且透過 `__builtin_popcount` 得知在位移的過程中，會產生幾次奇數，而需要進行幾次減 1 的操作。
所以在實作上就會變成
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
因此我們可以從這個實作推論 AAA 的答案是
> AAA = `__builtin_popcount(num)`
而 BBB 對應的答案則是
> BBB = `__builtin_clz(num)`
## 測驗 `4`
該測驗題的目的是在利用 [Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/) 來計算最大公因數
> The **Binary GCD algorithm** or **Stein's algorithm**, is an algorithm that calculates two non-negative integer's largest common divisor by **using simpler arithmetic operations than the standard euclidean algorithm** and it reinstates division by numerical shifts, comparisons, and subtraction operations.
因此可以知道在本題實作中
```cpp
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
的目的在於利用 2 將兩數進行化簡，從而減輕之後進行輾轉相除法的運算，而在進行完輾轉相除法後，只需要將該數利用 `shift` 變數所記錄的位移次數來修正就可以得到最後我們要求得的最大公因數了
而在本題的實作中，為了避免使用 `%` 取餘這種運算子，所以採取如下圖的方式進行相關的運算
從這張圖就可以知道，如果除去使用取餘這種運算子，而在兩數沒有化簡的情況下，需要執行非常多次迴圈才能完成運算。因此在該實作中才會採取先化簡，再進行運算的手法來進行
若我們假設 u = 12, v = 6 來執行本題實作的程式碼，則會發生以下的情況
1. 一開始 `u = 12`, `v = 6`
2. 經過迴圈化簡後， `u = 6`, `v = 3` 且 `shift = 1`
3. 因為 `u = 6` 不是一個奇數，所以利用迴圈化簡直到該數變成一個奇數，則 `u = 3`
4. 因為 `u = 3` 且 `v = 3` 所以走到 `else` 的 statement，也就是 `u = 3` 且 `v = 0` 的狀況，很明顯因為在這個時候我們已經得到了最終的結果也就是 `u = 3` 所以在 `v = 0` 的時候我們應該要有辦法可以從迴圈中跳出來，因此 `XXX` 的答案應該為
> XXX = `v`
最終我們應該要將最大公因數，也就是 `u` 的數值回傳回去，但是因為我們在進行運算之前有做過化簡，所以我們需要運用剛剛化簡的參數 `shift` 將 `u` 還原為最大公因數，因此我們最後回傳回去的數值就會是 `u << shift` ，因此 `YYY` 的答案就是
> YYY = `u << shift`
### 延伸問題
:::info
以 `__builtin_ctz` 改寫程式碼
:::
因為使用 `ctz` 的目的在於不需要使用迴圈一次一次嘗試該數是否已經是一個奇數，可以直接使用 `ctz` 所計算出的數字直接進行 shift 即可
因此在修改上只需要將
```cpp
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
這樣的實作改為下列等價的形式及可以
```cpp
int shift = min(__builtin_ctz(u), __builtin_ctz(v));
u >>= shift, v >>= shift;
```
而 `min` 函式可以使用 macro 進行定義
```cpp
#define min(a, b) ((a < b) ? (a) : (b))
```
而像是
```cpp
while (!(u & 1))
u /= 2;
```
則可以改寫為
```cpp
u >>= __builtin_ctz(u);
```
程式碼請參考 [gist](https://gist.github.com/OscarShiang/04808cba28c302220f0a4f0a11c14133)
## 測驗 `5`
測驗五的目的是在將影像處理常用到的 bit operation 改以 `ctz` 或是 `clz` 等指令改寫為等效但較為簡潔的版本
在原本 `naive` 函式的實作中我們可以看到這樣的 for 迴圈
```cpp
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;
}
}
```
這樣的目的在於利用 unsigned integer 位移的運算來判斷這一個 64 位與的正整數中有哪些位元是 `1` ，如果是 `1` 的話，就在 `out` 變數中， `pos` 的位置記錄 `p + i` 的運算數值。
從這邊可以發現：我們雖然只需要對 `bitset` 變數中是 `1` 的位元有興趣，但是為了判斷，我們必須使用迴圈檢查全部的位元，也就是 64 個位元，因此才會有 `improved` 的實作方式。
```cpp
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;
}
}
```
在 `improved` 的這個實作中，我們使用 GCC extensions 中的 `__builtin_ctzll` 來達到我們的目的，因為 `ctz` 可以計算出 least significant bit 距離第 0 位的距離。而因為這樣的函式，我們可以透過計算 `ctz` 就可以得知我們要處理的 bit 在第幾個位元，從而減去逐一執行迴圈的操作，簡化我們的操作。
而當我們利用 `ctz` 完成相關的運算之後，我們需要將 `bitset` 的 least significant bit 消除，避免在執行下個迴圈的時候，重複計算到同一個位置，因此我們會需要先計算出一個 `t` 值，用途是在完成運算後利用
```cpp
bitset ^= t;
```
去除處理完的 LSB，因此在本題的 `KKK` 就會是
> KKK = `bitset & -bitset`
因為 `bitset & -bitset` 可以算出只有 LSB 存在的數值，就像如果 `bitset` 是 1，那 `1 & -1` 的結果就會是 `0001 & 1111` 結果就會是 `0001` 也就是只有 LSB 存在的數值。
:::info
同理我們也可以運用 `__builtin_ctz` 得到的數值算出相同的數值，即 `t = 1 << r`
:::
所以我們就可以利用這樣的方式算出 LSB 並利用 XOR 運算將其消除。
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet