# 2020q3 Homework3 (quiz3)
###### tags: `sysprog2020` `homework`
contributed by < `JKChun` >
> [第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3)

## 測驗 `1`

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));
}

### 延伸問題 1
>解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
- answer：
- OP1 : >> 1
- OP2 : m < 0
- 第 3 行：這段是為了確認編譯器在對負數實作右移時，會不會自動補齊 `sign bit`( Sign Extension )，`-1` 為 `0xFFFFFFFF`
- 如果編譯器會自動補齊 `sign bit`，則 `-1` 右移後還是 `0xFFFFFFFF`，會小於0，`logical` 為0，代表我們**不用**幫右移後的數補齊1
- 如果編譯器不會自動補齊 `sign bit`，則 `-1` 右移後會是 `0x7FFFFFFF`，會大於0， `logical` 為1，代表我們**要**幫右移後的數補齊1
- 第四行：只有在沒有 Sign Extension 且 `m` 為負數時，才需要自己補齊 `sign bit`，所以只有在此情況 `unsigned int fixu` 為 `0xFFFFFFFF`，其他情況都是0
- 第五行：還不知道
- 第六行：在不需要自己補齊 sign bit 的情況就 `return (m >> n)` 就行，如果需要自己補齊 sign bit ，就需要補齊從 MSB ( Most Significant Bit ) 開始往後數的 n 個 bit 為1， `(fix ^ (fix >> n))` 就可以滿足這樣的結果，假如 n 等於 6，則 `(fix ^ (fix >> n))` 為 `0xFC000000`，就是 `11111100000000000000000000000000`，再讓 `(m >> n)` 跟 `(fix ^ (fix >> n))` 做 `OR 運算` 就可以補齊

### 延伸問題2
>2.練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度;

---

## 測驗 `2`

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);  
}

### 延伸問題 1
>解釋上述程式運作原理;
- answer：
- OPQ ： & 0x1
- `num > 0`：放這段的原因在於 `num` 在 $\leq0$ 的情況不會是 power of four，所以 `num` 如果不大於 0 就可以直接 return false
- `(num & (num - 1))==0`：這段是在判斷 `num` 是否為 2 的 n 次方
- 如果 `num` 不是 $2^n$，那絕不可能是 power of four
- `!(__builtin_ctz(num) & 0x1)`：如果 `num` 為 power of four，則它的 trailing 0-bits 一定是偶數個(0, 2, 4,....)，`__builtin_ctz(num)` 的結果最後一個 bit 絕對不是 1，以此區分 $2^n$ 和 $4^n$
- | __builtin_ctz(num) | Binary |
| -------- | -------- |
| $0$ | 00000000 |
| $2$ | 00000010 |
| $4$ | 00000100 |

### 延伸問題 2
>改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;

### 延伸問題 3
>練習 [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;

### 延伸問題 4
>研讀 [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/Golomb_coding) 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 [Selecting the Golomb Parameter in Rice Coding](https://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf)。

---

## 測驗 `3`

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}

### 延伸問題 1
>解釋上述程式運作原理;
- answer：
- AAA ： __builtin_popcount(num)
- BBB ： __builtin_clz(num)
- 根據題目給的 example 可以發現整個運算就是：
- 遇到奇數就減 1 變偶數
- 遇到偶數就除以 2，就是向右 shift 1 位
- 以題目的 14 (1110) 為例：
1. 1110 為偶數，shift 1位，變 111 (7)
2. 111 為奇數，先減 1 變 110 (6)
3. 110 為偶數，shift 1位，變 11 (3)
4. 11 為奇數，先減 1 變 10 (2)
5. 10 為偶數，shift 1位，變 1 (1)
6. 1 為奇數，先減 1 變 0 (0)
- 總共 six step
- 以上面的例子可以發現：
- 計算 shift step：
- 在考慮 32 位元且是正數的情況，從最靠近 MSB 的 1 開始算到 LSB，看有幾個 bit，再減 1 就是幾個 shift step，以上面的例子：`0x0000000E` (1110) 中，最左側的 1 到 0 有 4 個 bit ( 32 - __builtin_clz(num) )，所以有 3 個 shift step，因為最左側的 1 不 shift 只減 1
- 計算 減 1 step：
- 有幾個 1 bit 就要減幾次 1，以上面的例子：`0x0000000E` (1110) 中有3個 1 所以有 3 個減 1 step

- 總結：
- `32 - __builtin_clz(num) - 1` 計算 shift step
- ` __builtin_popcount(num)` 計算 減 1 的 step
### 延伸問題 2
>改寫上述程式碼，提供等價功能的不同實作並解說;
>>提示: [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) 中提及許多 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, 最大公因數) 求值函式:

#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;
}

改寫為以下等價實作:

#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;
}

### 延伸問題 1
>解釋上述程式運作原理;
- GCD性質：[Greatest Common Divisor 特性和實作考量](https://hackmd.io/@sysprog/gcd-impl#fn1)
- GCD演算法：[Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/)
- answer：
- XXX：v
- YYY：u << shift
- 第 3 行：考慮了 gcd(x, 0) = x 和 gcd(0, y) = y 以及 gcd(0, 0) = 0 這三種情況
- 第 4 ~ 7 行：
- `!((u | v) & 1)` 這個判斷式是在 `u` 與 `v` 皆為偶數的情況 ( LSB 為 0 ) 才會成立 ( 0 與 1 AND 等於 0，再 NOT 則為 1 )
- 此迴圈就是計算兩個數字有幾個 2 的共同因數，用 `shift` 存數量，用在最後 shift ( 左移、乘以 2 ) 結果
- 第 8 ~ 9 行：
- 在經過前面的 for 迴圈後，只會有三種情況：
1. u 為偶數，v 為奇數
2. v 為偶數，u 為奇數
3. u 為奇數，v 為奇數
- 在上述三種情況中，2 並不是共同因數，所以對 GCD 的結果沒有影響，因此在 while 迴圈裡把 u 的因數 2 拿掉，GCD 的性質：$gcd(u,v)=gcd(\frac{u}{2},v)$
- 第 10 ~ 21 行：
- 這裡用 $gcd(u,v)=gcd(u-v,v), u > v$，不停讓 u 與 v 越變越小，直到 v 變為 0，$gcd(u,0)=u$；經過前面的 for and while loop，u 為奇數，而 v 在一開始及將減去 u 後 ( or $u - v$ ) 可能為偶數，所以在 11 ~ 12 行會把 v 除以 2 變成奇數，確保 u 為奇數且 u > v
- 最後 `u << shift` 將 u 乘上之前除掉的共同因數並 return 結束
### 延伸問題 2
>在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;

---

## 測驗 `5`

>在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#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 改寫為效率更高且等價的程式碼:

#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;
}

### 延伸問題 1
>解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
### 延伸問題 2
>設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
### 延伸問題 3
>思考進一步的改進空間;

---