# 2020q3 Homework3 (quiz3)
contributed by < `chi-ming5566` >
> [測驗題](https://hackmd.io/@sysprog/2020-quiz3)

## 作業要求
* 重新回答[第 3 周測驗題](https://hackmd.io/@sysprog/2020-quiz3)，連同附帶的「延伸問題」。
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb)的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
---

### `測驗一`

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

ars 在右移後，會依照原本首位的 bit 補回值，也就是正數補 0，負數補 1。

一開始的 `logical` 判斷環境是不是 logical right shift (一律補 0)，所以對 -1 右移 1(`OP1 = >> 1`)，如果是 logical right shift，會變成 0b011...111 > 0 = true = 1，反之則是 0b111...111 < 0 = false = 0。

而fixu 用來判斷被除數 m 是不是負數(`OP2 = m < 0`)，當 `logical` = 1 與 m < 0 時，`fixu` = -(1 & 1) = 0b111...111，否則 `fixu` = 0b000...000。

return 的結果，如果在 `logical` = 1 以及 m < 0 都成立時，`fix ^ (fix >> n)` 會是前 n 個 bits 為 1，其餘為 0。所以和 `(fix ^ (fix >> n))` 做 OR 運算就可以把 logical right shift 吃掉的 1 補回來。

* Example :

m = 0b11100110, n = 4, system = logical

digraph {
    m [shape = plaintext]
    intm [label = "1|1|1|0|0|1|1|0" shape = record] 
    
}

digraph {
    m_shift [label = "m >> n" shape = plaintext]
    intm_shift [label = "0|0|0|0|1|1|1|0" shape = record]
}

digraph {
    fix [shape = plaintext]
    intfix [label = "1|1|1|1|1|1|1|1" shape = record]
}

digraph {
    fix_shift [label = "fix ^ (fix >> n)" shape = plaintext]
    intfix_shift [label = "1|1|1|1|0|0|0|0" shape = record]
}

digraph {
    return [shape = plaintext]
    intreturn [label = "1|1|1|1|1|1|1|0" shape = record]
}

---
### `測驗二`

我們可用 __builtin_ctz 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:

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

要判斷輸入的數字是否為 4 的次方，4 的二進位表示是 0100，也就是說 4 的次方是 1 後面接著偶數個 0 (每次乘以 4， 1 就會向左位移 2 位元)。

一開始 `num > 0` 判斷是否為正整數，`(num & (num - 1)) == 0` 判斷是否為 2 的次方
($1{\overbrace{000...000}^{n個}}$ & $0{\overbrace{111...111}^{n個}} = 0$) ，所以可以知道 `!(__builtin_ctz(num) OPQ` 是在判斷後面的 0 的個數是否為偶數。而任一偶數 & 1 = 0 (偶數最後一項 bit 為 0)，所以 `OPQ = & 0x1`。

---
### `測驗三`

popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 CRC32 和 POPCNT 指令，POPCNT 可處理 16-bit, 32-bit, 64-bit 整數。

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

這題計算一個數經過多少次計算可以變為零，而計算有分兩種 : >> 1 (當前是偶數)以及 - 1 (當前是奇數)。

int 寬度為 32 bits，因此將最左邊的 bit 移到最右邊要做 31 次 >> 1，有一個 1 就需要做一次 - 1，而起始 1 的位置每往右一個位元就能少做一次 >> 1。

所以 `AAA = __builtin_popcount(num)`, `BBB = __builtin_clz(num)` 。

---
### `測驗四`

考慮以下 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;
}

---
### `測驗五`

在影像處理中，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;
}

兩段程式碼互相比對後，用 `int r = __builtin_ctzll` 取代 `if ((bitset >> i) & 0x1)` 的功能，但改寫後的程式碼對 `out[pos++]` 賦值後還必須 clear bitset 的 LSB 以確保下個 Loop 的正確運行。

> 根據題三提到 $-n=∼n+1$

利用 `bitset & -bitset` 留下 LSB 再於 `bitset ^= t` 清除 LSB
因此 KKK = `(e) bitset & -bitset`。