# 2020q3 Homework3 (quiz3)
contributed by < `grb72t3yde` >
###### tags: `sysprog2020`
---
## Links
* [第三週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
* [作業區](https://hackmd.io/@sysprog/2020-homework3)
## 測驗 `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\gg^{arith}1=-3$
上述 $-3$ 正是 $\dfrac{-5}{2}$ 的輸出, 並向 $-\infty$ 進位(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));
}
```
### 解題思路
OP1 = ? OP2 = ?
首先看題目給的資訊 :
* 參考 [Unspecified_behavior](https://en.wikipedia.org/wiki/Unspecified_behavior), 得知此種行為是 `source code` 在基於使用不同的`編譯器`或是`編譯器設定`會有不同的表現。
* 以 `ASR` 來說, 當我們欲對`負數`進行`算數右移`卻沒有補入對應個數的 `1` sign bits 時, 這種 `Unspecified_behavior` 就會產生 "錯 (不如預期) 的結果"; 因此, 我們需要對其手動補入對應個數的 `1`。
開始看程式碼 :
1. 我看到 `line 6` 的 `return value`, 判斷 `| (fix ^ (fix >> n)` 為修正操作
2. 繼續往 `(fix ^ (fix >> n)` 來想, 作為修正值, 必須要是 :
* $\overbrace{
\underbrace{11...11}_\text{n bit(s)}
\underbrace{00...00}_\text{32-n bit(s)}
}^\text{32 bits}$ 或是 `0` (不用修正的情況下)。
3. 回推至 `line 4`, 這邊製作出修正值 `fixu`, 已知 `logical` 和 `OP2` 都為 `equality-expression`, 所以 `fixu` 非 `-1` 即 `0`, 這應証了修正值的結果 (如 2. 提到的形式或是 `0`)
4. 考慮我們必須同時滿足 `logical` 和 `OP2` 才需要修正, 我從選項判斷 `OP2` 應為 `m < 0` (即 `m` 為一個負數)
5. 回頭檢視此程式對 "跨平台" 的需求, `OP1` 選擇 `>> 1`
(在不支援 `ASR` 的環境下, 使 `0xffffffff` 做"算數右移"將得到 `0x7fffffff`, 此數在被視為 `signed int type` 的情況下, 大於 `0`; 反之, 支援 `ASR` 的平台仍給我們 `0xffffffff`)
:::warning
line 5 和使用 `int fix = (int) fixu` 有何差別？
:::
### 延伸問題
- [ ] 練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;
* char, unsigned long
## 測驗 `2`
在 [C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 中，我們介紹過 power of 2 (漢字可寫作「二的冪」)。
> 女星楊冪的名字裡，也有一個「冪」字。且，她取這個名字，就有「次方」的意義，因為她一家三口都姓楊，所以是「楊的三次方」。
[GCC extension](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 其中兩個是 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](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 = ?
* 思考如果一個正整數能被表示成 $4^n$, 其二進位應該是
* ${
\underbrace{00...00}_\text{32 - (2n+1) bits}
\underbrace{1}_\text{1 bit}
\underbrace{00...00}_\text{2n個0}
}$
也就是它能被`算術右移` n 次後得到 `1`
* 觀察 line 3 的 `return` 判斷了三件事情, 分別為 :
1. `num > 0` : `0` 和 `負數` 不可能是 `power of 4`
2. `(num & (num - 1) == 0` : 判斷 `1-bit` 的個數, 在只有一個 `1-bit` 下此條件成立
3. `!(__builtin_ctz(num) OPQ)` : 有了前兩個條件成立, 此條件必須是要判斷 `trailing 0-bits` 是否為偶數個, 因此選擇 `& 0x1`
### 延伸問題
- [ ] 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;
- [x] 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) 和 [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)，應善用 clz;
- [ ] 研讀 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz)，理解 clz 的實作方式，並舉出 [Exponential Golomb coding](https://en.wikipedia.org/wiki/Exponential-Golomb_coding) 的案例說明，需要有對應的 C 原始程式碼和測試報告;
> [x-compressor](https://hackmd.io/@sysprog/2020-quiz3) 是個以 [Golomb-Rice coding](https://en.wikipedia.org/wiki/Golomb_coding) 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 [Selecting the Golomb Parameter in Rice Coding](https://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf)。
## 測驗 `3`
[population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `POPCNT` 指令，`POPCNT` 可處理 16-bit, 32-bit, 64-bit 整數。
針對 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 = ?
* 根據題目敘述, 我們想知道給定的 `int` type 輸入 `num` 最少可以透過幾個 `steps` 來變成 `0`, 其中:
* 我們透過 `devide by 2` 以及 `subtract 1` 兩種操作使 `num` 逐步變成 `0`
* 以上兩種操作都稱為一個 `step`
* 當我們遇到 `LSB` 為 `1` 的數字(此數字為奇數)時, 我們必須施以 `subtract 1` 的操作, 則我們需要使用 `__builtin_popcount(num)` 次的 `subtract 1` 操作, 可判斷 `AAA` 為`__builtin_popcount(num)`
BBB = ?
* 除去 `1`, 剩下的 `0` 我們可利用 `>>` 操作處理, 然而, 我們需要知道最左邊的 `1` 位於何處
* 因為最後一次的 `subtract 1` 已被算在 `__builtin_popcount(num)` 內, 我們先將 32 減一, 接著透過減掉 `leading zero` 的個數, 可以知道我們需要施以 `>>` 多少次, 因此判斷 `BBB` 為 `__builtin_clz(num)`
### 延伸問題
- [ ] 改寫上述程式碼，提供等價功能的不同實作並解說
> 提示: [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) 中提及許多 bitwise operation 的使用，如 [bit inverse](https://hackmd.io/@sysprog/ByzoiggIb)、abs 等等，是極好的參考材料。
- [ ] 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，實作出 branchless 解法，儘量縮減程式碼行數和分支數量
## 測驗 `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;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
改寫為以下等價實作:
```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 = ?
1. 觀察 `line5` 的 `for loop`, 當 `u` 與 `v` 的 `LSB` 同時為 `0` 時, 迴圈將繼續執行, 得知此迴圈計算的 `shift` 為 `u`, `v` 共同的 `tailing zero` 個數
2. 觀察到 `line8`, 的 `while loop`, 在做把 `tailing zero` 全部除去, 這也相當於 "將 `u` 的 `2` 因數全部除去"
3. 因為我們已記錄下共同的 `2` 質因數個數, 接下來在做`輾轉相除法時`就不需考慮 `2`, 而終止條件一樣選 `v`
YYY = ?
* 此動作補回 `tailing zero` 的個數, 因此選 `u << shift`
### 延伸問題
1. 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升
---
## 測驗 `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 = ?
TODO
### 延伸問題
1. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
2. 思考進一步的改進空間;
Sign in with Wallet
Connect another wallet