# 2020q3 Homework3 (quiz3)
contributed by < `chewei3` >
## 測驗 1
```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`
* `logical` 用來判斷 `>>` 是 logical right shift 還是 arithmetic right shift ，如果 `m < 0` 且是 logical right shift ，則 fixu 為 `-1u` ，`fix ^ (fix >> n)`用來將 `m` shift 後的左邊 `n` bits 補 1
:::success
延伸問題:
1. 解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
2. 練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度;
:::
## 測驗 2
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
### 答案
* `OPQ` = `0x1`
* `__builtin_ctz` 回傳從 LSB 到第 1 個 1 之前有幾個 0，`!(__builtin_ctz(num) 0x1)` 判斷是不是偶數個， 所以 0x1、0x4、0x16... ，都會return 1， `num & (num - 1)` 用來判斷 `num` 是不是偶數，也就是判斷 LSB 是不是 1，所以可以去掉 0x1
:::success
延伸問題:
1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;
2. 練習 [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;
3. 研讀 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz)，理解 clz 的實作方式，並舉出 [Exponential Golomb coding](https://en.wikipedia.org/wiki/Exponential-Golomb_coding) 的案例說明，需要有對應的 C 原始程式碼和測試報告;
>[x-compressor](https://github.com/jserv/x-compressor) 是個以 [Golomb-Rice coding](https://en.wikipedia.org/wiki/Exponential-Golomb_coding) 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 [Selecting the Golomb Parameter in Rice Coding](https://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf)。
:::
## 測驗 3
```cpp=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
### 答案
* `AAA` = `__builtin_popcount(num)`
* `BBB` = `__builtin_clz(num)`
* 一個 step 包含
* divide by 2
* subtract 1, if LSB is 1
* 因此 `numberOfSteps` 計算最高位有效位的 bit position( `31 - __builtin_clz(num)` )，加上 1 的個數( subtract 次數)
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 改寫上述程式碼，提供等價功能的不同實作並解說;
>提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用，如 [bit inverse](https://hackmd.io/@sysprog/ByzoiggIb)、abs 等等，是極好的參考材料。
3. 避免用到編譯器的擴充功能，只用 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` = `v`
* `YYY` = `u << shift`
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
:::
### 用 __builtin_ctz 改寫 GCD
```cpp=
#ifndef min
#define min(x, y) ((x) < (y) ? (x) : (y))
#endif
uint64_t gcd64(uint64_t u, uint64_t v){
if (!u || !v)
return u | v;
int shift = min(__builtin_ctz(u), __builtin_ctz(v));
u >>= shift; v>>= shift;
while (!(u & 1))
u >>= 1;
do {
while (!(v & 1))
v >>= 1;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
## 測驗 5
```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;
}
```
可用 ctz 改寫為效率更高且等價的程式碼:
```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`
* `naive` 的做法是一次只檢查 bitset 的某 1 bit 是不是 1，並且把bit position 放到 `out[pos]` ，每一個 bitmap 都要做 64 次效率不夠好
* `improved` 用 ctz 找出 bit position ，並且用 `bitset & -bitset` 將 bitset 的最低有效位的 1 設為 t ，用 xor 將之設為 0
:::success
延伸問題:
1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
2. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
3. 思考進一步的改進空間;
:::
Sign in with Wallet
Connect another wallet