# 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 語言規格書的章節)，以及==進行相關實驗==。
---
### `測驗一`
```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));
}
```
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
```graphviz
digraph {
m [shape = plaintext]
intm [label = "1|1|1|0|0|1|1|0" shape = record]
}
```
```graphviz
digraph {
m_shift [label = "m >> n" shape = plaintext]
intm_shift [label = "0|0|0|0|1|1|1|0" shape = record]
}
```
```graphviz
digraph {
fix [shape = plaintext]
intfix [label = "1|1|1|1|1|1|1|1" shape = record]
}
```
```graphviz
digraph {
fix_shift [label = "fix ^ (fix >> n)" shape = plaintext]
intfix_shift [label = "1|1|1|1|0|0|0|0" shape = record]
}
```
```graphviz
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 位元寬度。實作程式碼如下:
```cpp=
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 整數。
```cpp=
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, 最大公因數) 求值函式:
```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;
}
```
---
### `測驗五`
在影像處理中，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;
}
```
兩段程式碼互相比對後，用 `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`。
Sign in with Wallet
Connect another wallet