# 2020q3 Homework3 (quiz3)
contributed by < `chewei3` >

## 測驗 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));
}

### 答案
* `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

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

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, 最大公因數) 求值函式:

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

### 答案
* `XXX` = `v`
* `YYY` = `u << shift`

:::success
延伸問題:

1. 解釋上述程式運作原理;
2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
:::
### 用 __builtin_ctz 改寫 GCD

#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

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

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