# 2020q3 Homework3 (quiz3)
contributed by < `JimmyLiu530` ＞
###### tags: `進階電腦系統理論與實作`
> [題目](https://hackmd.io/@sysprog/2020-quiz3)
## 測驗1: Arithmetic right shift for signed integers
在 C 語言中，對有號型態的物件進行算術右移(簡稱 ASR)歸屬於 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:
$-5>>^{arith}1$ $= -3$
上述 $-3$ 即為 $\dfrac{-5}{2}$ 向 $-\infty$ 進位的輸出
```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));
}
```
### 程式說明
算術右移一個正數其最左邊的 bit 必定是補 0 ，而算術右移一個負數有可能是補 0 或是補 1，而根據題目的意思，顯然是後者，因此需要知道 compiler 是補 0 還是 1。若是補 1，則符合我們的要求不需修補；否則需要修補。而這個修補會在 line 6 的`| (fix ^ (fix >> n))`。
line 3 的用意就是在看此 compiler 對一個負數算術右移後會補 0 還是 1，若補 1，則右移後的結果為負 (<0)，因此 logical 為 0；否則 logical 為 1。所以 `OP1 = >> 1`。
接著，考慮算術右移一個負數補 0 的情況，因為 line 6 的修補項是要用來修補的，所以 `(fix ^ (fix >> n))` 的最高的 n 個位數一定要是 1，也就代表 `fix` 會是 `0xffffffff`，最後可推得 `OP2 = m < 0`。
此結果也符合一開始說的條件: 除了原本 compiler 右移負數補 1 不用修補之外，正數也不需要 (即只有`右移補 0` 且 `為負數`才需要修補)。
:::info
已解問題:
`int fix = *(int *) &fixu;` 這樣寫的用意?
`int fix = (int) fixu;` 以及可以改成這樣嗎?
> 雖然此程式看似可互換，但這兩行程式碼的意義不太相同，前者為 `interpret`，後者為 `cast`。看下面的例子:
> ```c=
> float a = 0.5;
> int b = (int)a;
> int c = *(int*)&a;
> printf("%f 0x%08x 0x%08x\n", a, b, c);
> ```
> 會得到:
> ```c=
> 0.500000 0x00000000 0x3f000000
> ```
> 也就是說前者以 整數 的角度去詮釋(interpret) 浮點數，好讓我們去對其中的某幾個位元做操作。
>
> 而後者是直接把 浮點數 強制轉型(cast)成 整數。
:::
### 延伸問題
#### 1. 數學證明和 Graphviz 製作的圖解
#### 2. 練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度;
-------------------------------------
## 測驗2: Leetcode [342. Power of Four](https://leetcode.com/problems/power-of-four/)
GCC extension 其中包含兩個函式: ctz 和 clz:
> Built-in Function: `int __builtin_ctz (unsigned int x)`
> - Returns the number of ==trailing== 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
> Built-in Function: int __builtin_clz (unsigned int x)
> - Returns the number of ==leading== 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
我們可用 `__builtin_ctz` 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:
```c=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
### 程式說明
line 3 的第二個條件 `(num & (num - 1))==0` 其實就區分出 2 的冪次方的數了，像是 $2^3 =1000_{(2)}$ 減1後，$7 = 0111_{(2)}$，因此接下來只要排除掉 2 的冪次方($2^n$)中，n 為奇數的數即可。一樣可以透過觀察:
| decimal | binary | # of trailing zero |
| ------- | ------ | ------------- |
| 2 | 10 | 1 |
| **4** = $4^1$ | 100 | **2** |
| 8 | 1000 | 3 |
| **16** = $4^2$ | 10000 | **4** |
| 32 | 100000 | 5 |
| **64** = $4^3$ | 1000000 | **6** |
發現 n 為奇數的數，其 trailing zero 也會是奇數個，因此 `OPQ = & 0x1`。
### 延伸問題
#### 1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
```c=
bool isPowerOfFour(int num)
{
return num > 0 && __builtin_popcount(num) == 1 &&
!(__builtin_ctz(num) & 0x1);
}
```
將原本的 `(num & (num - 1))==0` 改成 `__builtin_popcount(num) == 1`，兩者都可以過濾掉非 2 的冪次方的數。
又或是可以改寫成:
```c=
bool isPowerOfFour(int num)
{
return num > 0 && !(__builtin_popcount(num) ^ 0x1) &&
__builtin_ffs(num) & 0x1);
}
```
`__builtin_popcount(num) == 1` 等價於 `!(__builtin_popcount(num) ^ 0x1)`，且
4 的冪次方的數其 first set bit 的位置會是奇數。
> Built-in Function: int __builtin_ffs (int x)
> - Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
#### 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
**Complement of Base 10 Integer**:
```c=
int bitwiseComplement(int N){
if (N == 0)
return 1;
uint32_t mask = 0xffffffff >> __builtin_clz(N);
return N ^ mask;
}
```
- 位元反轉 -> 想到 `^ 1111...1111`
- 只需要反轉最低 `32 - (N 的 leading zero)` 個位元
**First Missing Positive**:
```c=
// TODO
```
----------------------------------------------
## 測驗3: LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
給定一個非負整數 `num`，回傳將此數依照下面的規則變成 0 需要幾步。而規則就是:
> 當目前的數為偶數，則將它除以 2；否則將它減 1。
我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```c=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
### 程式說明
因為在正整數中，除以 2 即為右移 1 位元，所以總共要除幾次就等於 MSB 移到最低位需要移幾次，MSB 移至最低位需 `31 - __builtin_clz(num)` 步，因此也需要除那麼多次。
再者，當 `num` 的二進位表示法中有 k 個 1 時，代表總共需要做 k 次的減 1，因為這些 1 總會被移到最低位元的位置，而最低位元為 1 代表是奇數需要減 1 ，所以共需 `__builtin_popcount(num)` 次減 1
因此最後答案就會是 `AAA = __builtin_popcount(num)` 及 `BBB = __builtin_clz(num)`
### 延伸問題
#### 1. 改寫上述程式碼，提供等價功能的不同實作並解說
```c=
// TODO
```
#### 2. 避免用到編譯器的擴充功能，只用 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 解法，儘量縮減程式碼行數和分支數量
```c=
// TODO
```
---------------------------------------
## 測驗4: 64-bit GCD
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
```c=
#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;
}
```
改寫為以下等價實作:
```c=
#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;
}
```
### 程式說明
此改寫後的程式與最原本單純利用輾轉相除法不同的點在於，做輾轉相除法之前，先做了以下的步驟:
- 先將兩數中所有 2 的因數都提出來，最後再將結果**左移**對應的位數即可
- 當其中一數不存在 2 因數時，代表 2 就不會是他們的公因數，因此將另一個仍含有 2 因數的數除以 2 直到變成奇數, e.g. gcd(24,9) = gcd(6,9)
line 5-6 其實就是在做上述的第一點，總共提出`shift` 個 2。line 8-9 及 11-12就是做上述的第二點。而程式中的 do-while 其實就是輾轉相除法，只是是用減法去實現，因此 `XXX = v`。最後，再將原本的結果 u 左移 shift 個 bit(即 x$2^{shift}$)，所以 `BBB = u << shift`。
### 延伸問題
#### 1. 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升
```c=
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
int ctz_u = __builtin_ctz(u);
int ctz_v = __builtin_ctz(v);
if (ctz_u < ctz_v)
shift = ctz_u;
else
shift = ctz_v;
u = u >> ctz_u;
v = v >> ctz_v;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
// TODO分析
_____________________________________
## 測驗5: Positions of set bits in bit array
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼:
```c=
#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 改寫為效率更高且等價的程式碼:
```c=
#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;
}
```
### 程式說明
第一個程式的作用在於看 `bitmap` 中哪些 bit 為 1，並將其位置記錄在 `out` 中。第一與第二個程式只有 line 8 的那個 while 的不同而已，因此聚焦在此。
透過觀察第一個程式碼，可知其脈絡為一個位元一個位元地去檢查 `bitset` 是否為 1，即 若要檢查第 k 個位元，需將 `bitset` 右移 k 位元，再與 1 比較。
而第二個程式也是 follow 這個脈絡，只是在 line 10 計算了 `bitset` 的 trailing zero，可以減少傻傻地去檢查為 0 的位元的時間，來提升效率。最後，line 12 需將把檢查過的位元變成 0，因此 `KKK = bitset & -bitset`，這是因為 `x & -x = x & (~x + 1) = 保留其 LSB，其餘設為 0`，所以 x ^ (x & -x) 會將原本 x 的 LSB 變成 0。
### 延伸問題
#### 1. 舉出這樣的程式碼用在哪些真實案例中
- 在 linux kernel 中有使用這種資料結構 - 第 k 位被設成 1 若且唯若 k 在佇列裡時，可提升從硬體中找到「首位 0」操作的效率
- 也會用在記憶體頁、inode、磁碟分割區等的分配上，去看哪些記憶體已被使用
#### 2. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html)
#### 3. 思考進一步的改進空間
Sign in with Wallet
Connect another wallet