# 2020q3 Homework3 (quiz3)
contributed by < `Tim096` >
> [2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3#2020q3-%E7%AC%AC-3-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
> [Github](https://github.com/Tim096/dict)
## 測驗 1
### 事前準備
何謂 const ?
答 : 不詳細但是精簡的說法會是 "只讀"。
以下舉例解釋：
```cpp=
const int a;
int const a;
const int *a;
int * const a;
int const * a const;
```
前兩行的作用是一樣，a是一個常數型整數。
何謂常數型整數 ?
答 : 常數就是恆常不變的數值，一但經初始化就無法再改變其值而且必須在宣告的時候便初始化。
第三行意味著a是一個指向常數型整數的指標 (也就是，整型數是不可修改的，但指標可以)。
第四行意思a是一個指向整數的常數型指標 (也就是說，指標指向的整數是可以修改的，但指標是不可修改的)。
最後一行意味著a是一個指向常數型整數的常數型指標 (也就是說，指標指向的整數是不可修改的，同時指標也是不可修改的)。
### 題目：
**(做一個「算數右移」出來)**
$-5≫^{arith}1=-3$
上述 $-3$ 正是 $\dfrac{-5}{2}$ 的輸出，並向 $−∞$ 進位(rounding)。
`m` = -5
`n` = 1
針對有號整數的跨平台 ASR 實作如下:
```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));
}
```
請補完程式碼。
OP1 = `>> 1`
OP2 = `m < 0`
<font color="red">Q : 第二行 `((int) -1)` 為何要特地這樣寫 ? 有甚麼特別的意義嗎 ? </font>
A : 為了題目方便 (選擇題的不便性)
### 原理：
* 根據 C 語言規格書所述，對有號型態的物件進行算術右移歸屬於 [unspecified behavior](https://hackmd.io/@sysprog/c-undefined-behavior) ，程式行為仰==賴編輯器實作和平台特性==而定
>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.
* 第二行 : 因此 logical 所做的事，就是確認目前的執行環境，是「邏輯右移」還是「算數右移」
* 透過 `(int) -1` 確認執行環境狀態，將 `-1` 右移一個 bit ，因此 OP1 為 `>>1`
* 邏輯右移：將最左的 bit (Most Significant Bit) 補 0 ，結果 > 0 ，`logical = 1`
* 算數右移：將最左的 bit (Most Significant Bit) 補上原本失去的符號，在此是補上 1 ，結果 < 0 ，`logical = 0`
* 第三行 : 若執行環境為「邏輯右移」 ( `logical = 1` )，且` m < 0` ，就需要對最左 bit 補上有號狀態，因此可推測出 OP2 為 `m < 0`
:::info
* 算數右移：
* 若 m > 0 補 0 `fixu = 0`
* 若 m < 0 補 1 `fixu = 0`
* 邏輯右移：
* 若 m > 0 補 0 `fixu = 0`
* 若 m < 0 補 0 `fixu = -1`
題目的目標是實作出來一個「算數右移」，因此若系統本身就是「算數右移」則不用理他，此時觀察「邏輯右移」在`m < 0`時做的事情和「算數右移」是不一樣的，所以我們需要使用`第三行`把這一種情況挑出來
:::
* 第四行 : `*(int *) &fixu` 用意在於將 `fixu` 強制轉型為 `int` 型態
<font color="red">Q : 為何不一開始就把它定義成`int` ? </font>
A : 可避免編譯器進行過度 (aggressive) 最佳化
<font color="red">Q : 還是不懂請老師說得更佳詳細一點 ? 何謂"過度的最佳化" ? </font>
A : 老師的用意會要使用組合語言來輸出比較，是否會有差別
* 若環境為「邏輯右移」且 `m < 0` ， `fix` 經強制轉型後為 `-1`，透過 `(fix ^ (fix >> n))` 保留下需補上的有號 bit ，確保與 `m >> n` 後的結果做 `or` 運算不會失真
* 簡單一點來說 : `fix`把原本經過「邏輯右移」少掉的 1 補回去了。
## 測驗 2
### 題目：
**找出輸入是不是$4^n$次方**
>Built-in Function: `int __builtin_ctz (unsigned int x)`
>* Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.(返回"右"起第一個1之後的0的個數)
>Built-in Function: `int __builtin_clz (unsigned int x)`
>* Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.(返回"左"起第一個1之前0的個數)
我們可用 `__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);
}
```
請補完程式碼。
OPQ = `& 0x1`
### 原理：
* `num > 0` : $4^n$肯定 >0
* `(num & (num - 1))==0` : 假設 n 為 2 的次方，且 n > 0 ，從二進制角度觀察， n 的最右邊的 bit 1 ，其他值為 0 ，則 n & n-1 必為 0 ，如果 `num` 不是 $2^n$ 就必不為 $4^n$
::: info
**x & (x - 1) == 0**
判斷x是不是$2^N$次方(無號數)
如果一個數字是$2^N$次方，那麼其二進位表達的最高位為1，其餘位為0。
換個角度思考: 讓某個值少 1，就是讓那個值對最右邊的1產生借位。x & (x - 1)實際上是在把二進位表示中最靠右邊位的1變成0，而$2^N$次方最右邊的1
e.g. : 8 = (1000) , 7 = (0111) , 8 & 7= 0
:::
* 在滿足前兩個條件的前提下，從右往左數到第 1 個 1 之前的 0 總數(也就是ctz)為偶數個，`__builtin_ctz`肯定是一個偶數，而偶數和`0x1`做 AND 運算肯定是 `0`
:::danger
### 延伸問題：
1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
* 若 n 為 2 的倍數，以二進制表示下，只有其中一值為 1 ，其他皆全為 0
* 若 n 為 4 的倍數，在二進制表示下，一次會向右位移 2 格，因此透過 `__builtin_ctz(num)` 計算的結果，會皆為偶數
* 透過 `__builtin_popcount(num)` ，可知 `1-bits` 的個數
>Built-in Function: int __builtin_popcount (unsigned int x)
>* Returns the number of 1-bits in x.
```cpp=
bool isPowerOfFour(int num)
{
return __builtin_popcount(num) == 1 && ( __builtin_ctz(num)%2) == 0 ;
}
```
2. LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
* 透過 xor 運算，做 bit 翻轉
* 利用 `__builtin_clz(N)` ，計算需運算 xor 的有效長度
* 根據 `__builtin_clz(N)` 說明， `N=0 is undefined` ，因此需額外考慮 N=0 的狀況
```cpp=
int bitwiseComplement(int N)
{
if(N==0) return 1 ;
return N^(0xffffffff >> __builtin_clz(N)) ;
}
```
3. LeedCode [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
* 因為此題是為了找出陣列中，未出現的最小正整數，因此可將數值安插在所屬的陣列位置，例如 `1` 放在 `nums[0]` ， 3 放在 `nums[2]` 這樣的手法，再透過對陣列內容尋訪，若該位置 `nums[i]` 沒有放入數值，那麼最小值就是 `i+1` ，若陣列中每個位置都有對應的值，則最小值為 `NumsSize+1`
* 排序過程所需時間複雜度為 $O(n)$ ，而在尋訪陣列尋找最小值時， `wosrt case` 為 $O(n)$ ，即陣列中每個位置都有數值，因此在 `worst case` 下，整體時間複雜度為 $O(2n)$
* 排序方法說明：若 `nums[i]` 不為正整數，就不在排列目標名單中，直接將其值設為 0 ；如果 `nums[i]` 未超出 numsSize (可被安排於陣列內)，且目標位置內尚未存放目標值，則做交換的動作，交換過程需考慮到同值交換 ( 程式碼10~16行 ) 而導致的無窮迴圈
* 以陣列 `[4,1,3,5,6]` ，最後排列的結果會為 `[1,0,3,4,5]` ，因此輸出結果為 `2`
```cpp=
int firstMissingPositive(int* nums, int numsSize)
{
for(int i=0 ; i<numsSize ; i++)
{
if(nums[i] > 0)
{
if (nums[i] < (numsSize+1) && (i+1) != nums[i])
{
int tmp = nums[i] ;
if(nums[i] == nums[tmp-1]) nums[i] = 0 ;
else
{
nums[i] = nums[tmp-1] ;
nums[tmp-1] = tmp ;
i-- ;
}
}
else if (nums[i] > numsSize) nums[i] = 0 ;
}
else nums[i] = 0 ;
}
for(int i=0 ; i<numsSize ; i++)
{
if(nums[i] == 0) return i+1 ;
}
return numsSize+1 ;
}
```
:::
## 測驗 3
### 事前準備
- `__builtin_popcount()` : 用於計算一個 32 位無號整數有多少個為1
- `__builtin_clz(num)` : 返回"左"起第一個1之前0的個數
- `population count`簡稱 `popcount` 或叫 `sideways sum`，是計算數值的二進位表示中，有多少位元是 `1`
### 題目：
針對 [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 = `__builtin_popcount(num)`
BBB = `__builtin_clz(num)`
### 原理：
* 在二進制表示法中，每個 1 最後都要進行 -1 的動作，每向右挪 1 bit 都要進行除 2 的動作，直到最後最後結果剩下 1 ，再做最後的 -1 ，過程有點類似透過「短除法」將十進制轉為二進制
* 透過 `31 - __builtin_clz(num)` 計算需要往右挪多少次
* 再透過 `__builtin_popcount(num)` 計算需要 `-1` 多少次
### 舉例幫助理解
Input: num = 14
Output: 6
Explanation:
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.
`__builtin_popcount(num)`當中有多少個 `1` 就需要被扣除多少次數(14當中有3個`1`)
`31 - __builtin_clz(num)`二進制當中最高位元的 `1` 代表者要被除多少次數(14最高位元中的 `1` 在第3個)
:::danger
### 延伸問題：
1. 改寫上述程式碼，提供等價功能的不同實作並解說
* 透過 `(num|0x1)` 的動作，避免 `__builtin_clz()` 發生輸入為 0 的狀況，且不影響整體執行結果
```cpp=
int numberOfSteps(int num){
return 31 - __builtin_clz(num|0x1) + __builtin_popcount(num) ;
}
```
:::
## 測驗 4
### 題目：
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
```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;
}
```
請補完程式碼。
XXX = `v`
YYY = `u << shift`
### 原理：
```cpp=
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
* 透過上述的程式碼，了解輾轉相除法的整個過程：
* 根據輾轉相除法的概念，當過程執行到 u 、 v 其中一值為 0 ，則最大公因數為不為 0 的那個數，因此可以得知 $gcd(a,0)=a$ 的特性， `if (!u || !v) return u | v` 此部分就是在確認 u 、 v 是有 0 存在
* 再來輾轉相除法是依循著 $gcd(a,b)=gcd(b,a$ $mod$ $b)$ 這個概念在進行，整個 `while` 迴圈就是在做這樣的重複計算，直到 `v = 0` 為止
```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;
}
```
* 回到最大公因數的概念，如果兩數都可被 $2$ 連除，則最大公因數必參雜著 $2^n$
* `!(u | v) & 1`只會有 `1` 或 `0` 的情況
* 若是 `1` 的情況代表 `u` 和 `v` 皆為偶數，因此最大公因數必參雜著$2^n$，所以 `for` 迴圈跑一次去做 $gcd(u, v) = 2 * gcd(u/2, v/2)$
* 若是 `0` 的情況代表 `u` 和 `v` 其中一個是奇數，因此最大公因數必**沒有**參雜著$2^n$，那就不用做 `for` 迴圈了
<font color="red">Q : 是不是我有理解錯誤不然為甚麼不要直接用 `if-else` 就好了 ? </font>
A : 程式碼行數可以短一點，迪摩根定律可以用來當延伸教材，希望能自己去改 `if-else` 自己去實驗效能
:::info
* 透過 `(u | v) & 1` 這個計算動作，確認 u 、 v 兩者皆為偶數，若其中 1 值為奇數，與 1 做 & 計算後會有不為 0 的結果，並透過 shift 這個變數，紀錄總共右移多少次，來得到兩數皆為 0 或產生至少一個奇數的計算結果
:::
* 第8~11行 : 因為奇數與偶數無法做到整除的動作，因此透過 while 迴圈將判斷 u 、 v 是否為偶數，若是的話就進行除 2 的動作，以方便後面的計算
:::info
* 再比較 u 、 v 大小，透過相減的方式，使 v < u ，而 else 的部分，則是 v =< u 的狀況，將 u - v，然後再與 v 對調
* 而輾轉相除法的結束條件就是其中一值被減為 0 ，因此 `XXX = v`
* 輾轉相除法的最後結果就如同一開始所述，為 $gcd(a,0)=a$ ，但一開始有做對 2 連除的動作，因此這邊補上連除後的結果，故 `YYY = u << shift`
:::
* 其實上述就只是在做一般的 **輾轉相除法(Euclidean algorithm)** 而已，但是最後的 `return u << shift` 要注意一下記得如果上面最一開始的 `for` 迴圈那邊有被 $/2$ 過的話這邊需要乘 ($*2$) 回來
:::danger
### 延伸問題：
1. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
* 藉由 `__builtin_ctz( u|v )` ，可快速計算出shift的值
* 將原本透過 `while` 計算出的 `shift` 改由 `__builtin_ctz( u|v )` 來執行 ( 5~11 行)
```cpp=
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
shift = __builtin_ctz( u|v ) ;
if(shift)
{
u >>= shift ;
v >>= shift ;
}
if (!(u & 1))
u >>= __builtin_ctz(u) ;
do {
if (!(v & 1))
v >>= __builtin_ctz(v) ;
if (u < v)
{
v -= u;
}
else
{
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u<<shift;
}
```
因為 `__builtin_ctz()` 主要是在對一開始判斷是否存在著因數 $2^n$ 進行優化，因此在測試設計上，針對 u 、 v 都為偶數的狀態去做測試，並透過 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 進行效能分析：
```gcc
int main()
{
for(int i = 0 ; i < 0xffff ; i+=2)
{
for(int j = 0 ; j < 0xffff ; j+=2)
{
gcd64(i, j) ;
}
}
return 0 ;
}
```
* 以原本的方法進行測試：
```
Performance counter stats for './perf_test.o':
15,0863.80 msec task-clock # 1.000 CPUs utilized
624 context-switches # 0.004 K/sec
23 cpu-migrations # 0.000 K/sec
45 page-faults # 0.000 K/sec
6258,6631,7894 cycles # 4.149 GHz
3804,6978,9838 instructions # 0.61 insn per cycle
976,2472,2490 branches # 647.105 M/sec
141,9692,1133 branch-misses # 14.54% of all branches
150.882867503 seconds time elapsed
150.864725000 seconds user
0.000000000 seconds sys
```
* 透過 `__builtin_ctz()` 取代 while 迴圈的方法測試：
```
Performance counter stats for './perf_test.o':
8,4535.58 msec task-clock # 1.000 CPUs utilized
303 context-switches # 0.004 K/sec
10 cpu-migrations # 0.000 K/sec
45 page-faults # 0.001 K/sec
3499,8308,2866 cycles # 4.140 GHz
2541,5180,7243 instructions # 0.73 insn per cycle
552,3677,8057 branches # 653.415 M/sec
51,5058,8256 branch-misses # 9.32% of all branches
84.536884443 seconds time elapsed
84.536043000 seconds user
0.000000000 seconds sys
```
:::info
可以發現，透過 `while` 的方式計算 shift ，在 `branch` 使用上，比 `__builtin_ctz()` 多了將近一倍的數量，這也是導致效能低落的主要原因。
:::
## 測驗 5
### 題目：
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 `bitset`) 廣泛使用，考慮以下程式碼:
```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];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
可用 clz 改寫為效率更高且等價的程式碼:
```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;
}
```
請補完程式碼。
KKK = `bitset & -bitset`
### 原理：
先理解這個程式的目標是在實作什麼功能，有一個存放 `64-bits` 的 `array ( bitmap )` ，裡面共可存放 `bitmapsize` 個變數，而 `array` 是透過連續記憶體分配的方法去實作，在 `bitmap` 中，每一個數字占用 `64-bits` 的空間， `bitmap[0]` 區段為 0-63 ， `bitmap[1]` 區段為 64-127 以此類推，而整個程式的運作目的是透過 `out` 這個陣列，去依序儲存在這連續的記憶體空間裡面，出現 `bit 1` 的位置，而 `pos` 則是回傳出現 `bit 1` 的數量。
舉個例子來說，輸入 `bitmap = [0,1]` ，會得到 `pos = 1` ，`out[0] = 64` 這樣的結果，因為第一個數字為 0 ，在前 64 個 bit 中，沒有任何 1 出現，而第二個數字為 1 ，因此在第二個數字個第一個 bit 為 1 ，對應的連續位置為 64 。
* `naive` 運作流程解釋：
* 透過 `bitset` 來記錄當前所讀到的數值
* 透過 `p = k*64` 來計算目前數值所對應到的連續位置起始值
* 透過迴圈逐一右移再與 `1` 做 `&` 計算，確認是否為 `bit 1`
* 如果是的話，則將該位置 `p + i` 儲存到 `out` 陣列中
* `improved` 運作流程解釋：
* 透過 `__builtin_ctzll` 來計算當前的 `bitset` 中 `bit 1` 的位置，計算完成後，將該位置的 `bit` 清為 0 ，再繼續判斷 `bitset` 中是否還有 `bit 1` 存在
* 如何將最右邊的 1 設成 0 呢？我們知道如果 $A$ & $\bar{A}$ = 0(每個 bit 都相異)，$A$ & $(\bar{A} + 1)$ 則會得到和 $A$ 最右邊的 1 相同位置為 1，其他為 0 的 mask `t`，與此 mask 做 XOR 運算就可以消除最右邊的 1 。
* 因此我們可以透過 `bitset & -bitset` 這樣的方法，得到可以將從右數來的第一個 `bit 1` 設為 `0` 的 `mask`，因此 `KKK = bitset & -bitset` 。
* 最後再透過 `bitset ^= t` 將 `ctz` 指出的` bit` 清為 0 ，得以繼續下一輪執行 bit 檢查
<font color = "red">Q : 在學習的過程當中，中間這一些運算是每一個應該是知道如何應用即可，還是說要知曉如何精準的證明會比較好 ? </font>
A : 工程領域其實比較不需要這麼精準的證明，除非特別的領域
先知道證明在哪裡，未來做擴充的時候會更好用
###### tags: `進階電腦系統應用2020` `quiz3`
Sign in with Wallet
Connect another wallet