# [2020q3 Homework2 (quiz3)](https://hackmd.io/@sysprog/2020-quiz3)
contributed by < `zhu849` >
## 測驗 `1`
> 依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):
> > “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.”
>
> 在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR 或 asr) 歸屬於 unspecified behavior，包含 Cppcheck 在內的靜態分析器會嘗試找出 C 程式中這項 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:
> $-5 >> ^{arith}1 = -3$
> 上述 $-3$正是$\frac{-5}{2}$ 的輸出，並向$−∞$進位 (rounding)。
> 針對有號整數的跨平台 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));
}
```
> 提示: 透過 gcc/clang 編譯程式碼時，可加上 -fsanitize=undefined 編譯參數，在執行時期若遇到未定義行為，會得到以下錯誤訊息:
> > runtime error: load of misaligned address 0x7ffd8a89be8f for type ‘int’, which requires 4 byte alignment
==OP1==
`(a)` `<< 1`
***`(b)` `>> 1`***
`(c)` `* m + n`
`(d)` `+ m`
`(e)` `+ n`
`(f)` `- m`
`(g)` `- n`
* 預期的算數位移
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
C[label="{1|1|1|1|1|0}"];
D[shape=plaintext,fontcolor=black,label = "Arithmetic Shift Right 2 bits"];
D->C[style=invisible,dir=none]
A[label="{1|1|1|0|0|1}"];
B[shape=plaintext,fontcolor=black,label = "原本的內容"];
B->A[style=invisible,dir=none]
}
```
* 在某些平台可能出現不符合預期的算術位移，由觀察可知這會導致結果錯誤
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
C[label="{0|0|1|1|1|0}"];
D[shape=plaintext,fontcolor=black,label = "Arithmetic Shift Right 2 bits"];
D->C[style=invisible,dir=none]
A[label="{1|1|1|0|0|1}"];
B[shape=plaintext,fontcolor=black,label = "原本的內容"];
B->A[style=invisible,dir=none]
}
```
* 首先觀察到 line 3 的 `logical` 變數，從 assign 值 `(((int) -1) OP1) > 0` 得知這個值非0即1，可以猜想是在判斷某件事
* 再往下觀看， line 6 中可以看到除了 `m >> n` 之外還有和 `(fix ^ (fix >> n))` 做 or 運算，所以可以猜想 `(fix ^ (fix >> n))` 這段程式是用來清晰算數位移後 MSB 該為 1 或 0的操作
* 其中 line 5 可知 `fix` 是`(int *) &fixu` 記憶體內的值
:::warning
line 5 的操作看不懂，為何要多此一舉？
因為程式碼看起來 line 5 等價於 `int fix = -(logical & (OP2));`
關鍵可能在 `*(int *)` 的使用？
:::
* 再往回到 line 4 觀察，可以得知 `fixu` 的值是 `-(logical & (OP2))` ，那這樣代表如果 `logical` 或 `OP2` 其中一者為 0 時，fixu 會為 -0 = 0，往下迭代的話會使 `(fix ^ (fix >> n))` = 0，即算數位移後的 MSB 皆補 0
* 所以由上述的考慮和題目得知：僅有在有號負數時需要考慮將 MSB 補 1，那考慮 line 3 的 `logical` 應該是判斷該平台做「有號負數的算數右移的 MSB 補齊狀況」
* 若 `logical` 為 1:則代表 MSB 補0才會使 `(((int) -1) OP1) > 0` 為 true
* 若 `logical` 為 1:則代表 MSB 補1會使 `(((int) -1) OP1) > 0` 為 false
* 所以已知 $-1 = 0$ x $ffffffff_{16}$，要確認在有號負數的算數右移的情況使 `(((int) -1) OP1) > 0` 為 true 的選項為 (b)
==OP2==
`(a)` `m`
`(b)` `n`
`(c)` ***`m < 0`***
`(d)` `m == 0`
`(e)` `m > 0`
`(f)` `n < 0`
`(g)` `n == 0`
`(h)` `n > 0`
* 根據以上的敘述能夠猜出 line 4 中 `logical & OP2` 的目的了，就是檢查輸入的 `m` 是正數或是負數，所以選 \(c\)
> 提示: 透過 gcc/clang 編譯程式碼時，可加上 -fsanitize=undefined 編譯參數，在執行時期若遇到未定義行為，會得到以下錯誤訊息:
> > runtime error: load of misaligned address 0x7ffd8a89be8f for type ‘int’, which requires 4 byte alignment
>
>補充資訊:
>* Arm Assembly Language Programming: Arithmetic Shift Operations
:::success
延伸問題://TODO
1. 解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
2. 練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;
:::
## 測驗 `2`
> 在 C 語言：數值系統篇 中，我們介紹過 power of 2 (漢字可寫作「二的冪」)。
>
> >女星楊冪的名字裡，也有一個「冪」字。且，她取這個名字，就有「次方」的意義，因為她一家三口都姓楊，所以是「楊的三次方」。
> GCC extension 其中兩個是 ctz 和 clz:
>
> 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.
>
>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.
>
> 我們可用 __builtin_ctz 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 && !(__builtin_ctz(num) OPQ);
}
```
==OPQ==
* `(a)` `> 0`
* `(b)` `> 31`
* `(c)` `>> 0x2`
* `(d)` `>> 0x1`
* `(e)` `| 0x1`
* ***`(f)` `& 0x1`***
* `(g)` `^ 0x1`
* 判斷分成三個部分來看
1. `num > 0` : 其中輸入的數字必須為正數才有可能為 4 的冪次
2. `num & (num-1)`:用來判斷輸入的數是否為 2 的冪次
| $(num)_{10}$ | $(num)_{2}$ | $(num-1)_{2}$ |$(num)_{2}$ & $(num-1)_{2}$ |
| -------- | -------- | -------- |-------- |
| 1 | 00000001 | 00000000 |00000000 |
| 2 | 00000010 | 00000001 |00000000 |
| 3 | 00000011 | 00000010 |00000010 |
| 4 | 00000100 | 00000011 |00000000 |
| 5 | 00000101 | 00000100 |00000100 |
| 6 | 00000110 | 00000101 |00000100 |
| 7 | 00000111 | 00000110 |00000110 |
| 127 | 01111111 | 01111110 |01111110 |
| 128 | 10000000 | 01111111 |00000000 |
3. `!(__builtin_ctz(num) OPQ)`：判斷是否為 4 的冪次，如果是 4 的冪次則 `__builtin_ctz(num)` 的結果會是 2 的倍數，所以 `builtin_ctz(num)` 的 LSB 應該會是 0 ，如果 LSB 是 1 則這個數不為 4 的冪次。所以我們可以使用 `&0x1` 去判斷，所以選 (f)
| $(num)_{10}$ | $(num)_{2}$ | builtin_ctz(num)_{10} |builtin_ctz(num)_{2} |
| -------- | -------- | -------- |-------- |
| 4 | 00000100 | 2 | 00000010 |
| 16 | 00010000 | 4 | 00000100 |
| 64 | 01000000 | 6 | 00000110 |
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;
3. 練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive，應善用 clz;
4. 研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告;
> x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 Selecting the Golomb Parameter in Rice Coding。
:::
## 測驗 `3`
> LeetCode 1342. Number of Steps to Reduce a Number to Zero：
> > 題目：
> > 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.
>
> 我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
* `builtin_clz(num)` 可以知道二進位表示法從左邊數來第一個 1 之前有多少個 0 leading，已知最差狀況我們會需要執行 divide it by 2 總共 31 次，利用 `builtin_clz(num)` 可以減少 divide 次數的操作
* 又因為題目敘述說如果是奇數則要多一次 subtract 的操作：所以要計算二進位表示法數字內有多少個 1 ，代表 subtract 的操作需要有多少次
* 這有一個問題：雖然速度很快，但是記憶體明顯消耗得比其他寫法消耗的多
==AAA==
***`(a)` `__builtin_popcount(num)`***
`(b)` `__builtin_clz(num)`
==BBB==
`(a)` `__builtin_popcount(num)`
***`(b)` `__builtin_clz(num)`***
## 測驗 `4`
* `popcnt_naive()` 常數時間實作需要花時間詳細想過一次
> 考慮以下 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;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
* 程式就是一般輾轉相除法的實作
* line 3 用於判斷 `u` 或 `v` 是否有一者為 0 ，若是則回傳 `u` 或 `v` 較大的數字
* line 4 - line 8：使 `u` 為較大的數，使 `v` 為較小的數(若初始值反過來是 `v` 較大則經過一輪 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;
}
```
* line 3 和原本功能相同
* line 4：新增 `shift` 變數存放 `u` 和 `v` 兩個數公因數的2因子個數，也就是右移的 bit 個數
* line 5 - 6：判斷式 `!((u | v) & 1)` 用於判斷 `u` 和 `v` 是否兩數皆為偶數，若是則繼續執行，否則離開迴圈
* line 8 - 9：由 [Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/) 得知「一數為奇數另一數為偶數，則無 2 因子」，使 `u` 一定為奇數
* line 11 - 12：和 line 8 - 9 同理
* line 13 - 14 ：使 `v` 必須要小於 `u`
* line 16 - 18 ：若 `v` 已經小於 `u` 了，則不斷將 `u` 減去 `v`
* line 20：可知道 XXX = `v` ，因為 `v` 的值會比 `u` 值更快接近 0
* line 21：從 line 20 知道若 `v == 0` 跳出 while 迴圈，則 `u` 儲存值為剩餘的最大公因數，將此數 left shift 回去變數 `shift` 的量可以得到真正的最大公因數
==XXX==
`(a)` `u`
***`(b)` `v`***
`(c)` `u + v`
`(d)` `u - v`
`(e)` `u >> 1`
`(f)` `v >> 1`
==YYY==
`(a)` `u`
`(b)` `v`
`(c)` `u << v`
`(d)` `v << u`
`(e)` `u << shift`
***`(f)` `v << shift`***
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
:::
## 測驗 `5`
> 影像處理中，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;
}
```
* line 5 - 12：64 bits 為一組，總共有 k 組，並且對每組的內容的每個 bit 做判斷，若 LSB 為 1 則記錄在 out 陣列中
可用 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;
}
```
* line 10：加入 function `__builtin_ctzll` 可以讓本來 64bits 每輪都要判斷的問題改善(從尾部開始數直到遇到1才紀錄)
* `bitset & -bitset` 的效果是將從尾部數來第一個 1 從 `bitset` 中取出，在利用 `bitset ^= t` 的操作就能將 `bitset` 中的最末個 1 從 `bitset` 中去除
==KKK==
`(a)` `bitset`
`(b)` `bitset & 0x1`
`(c)` `bitset | 0x1`
`(d)` `bitset ^ 0x1`
***`(e)` `bitset & -bitset`***
:::success
延伸問題:
1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
2. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
3. 思考進一步的改進空間;
:::
Sign in with Wallet
Connect another wallet