---
# System prepended metadata

title: '[2020q3 Homework2 (quiz3)](https://hackmd.io/@sysprog/2020-quiz3)'

---

# [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 的操作需要有多少次
* 這有一個問題：雖然速度很快，但是記憶體明顯消耗得比其他寫法消耗的多
![](https://i.imgur.com/av08kdx.jpg)

==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. 思考進一步的改進空間;
:::