# 2020q3 Homework3(quiz3)
contributed by < `fennecJ` >
### 題目連結
> [2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
## 測驗 `1`
```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));
}
```
`OP1` = `>> 1`
這裡的作用是在判斷系統在進行右移運算時會補 1 或是補 0 ，若補 1 ，則表示系統進行 ASR 運算，此時 `logical` = 0 ，反之 `logical` = 1
只有負數的右移運算是未定義行為，因此要判斷輸入進來的數字是否為負數，所以
`OP2` = `m < 0`
所以 `logical` & `(m < 0)` 只會有四種狀態
| logical | m < 0 |fixu = -logical & (m < 0) |
| -------- | -------- | -------- |
| 0 |0 |0 |
| 0 | 1 |0 |
| 1 | 0 | 0 |
| 1 | 1 | -1 |
其中，只有當程式偵測到系統並非使用 ASR 運算右移且輸入的數值 m 為負數時 fixu 才會是 -1 ， fix 也是 -1 。而 -1 的二進位為 :
`1111 1111 1111 1111 1111 1111 1111 1111`
而若 m 原本的二進位為 :
`mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm`
經過右移 n 位之後 ( 假設 n = 8 ) 會變成 :
`0000 0000 mmmm mmmm mmmm mmmm mmmm mmmm`
fix 右移 n 位為
`0000 0000 1111 1111 1111 1111 1111 1111`
fix^(fix>>n) 為
`1111 1111 0000 0000 0000 0000 0000 0000`
觀察可發現此時 fix^(fix>>n) 恰能補足 m>>n 使其成為 ASR 運算。
而若 logical 和 m < 0 中有任何一個條件不滿足，則不需要去補足 m>>n ， fix 的值也剛好會是 0 ，此時只有三種可能 :
1. 系統進行 ASR 右移運算，輸入負數：本來就是 ASR 運算，不需要調整
2. 系統進行 ASR 右移運算，輸入正數：本來就是 ASR 運算，且正數為已定義行為，不需要調整
3. 系統不進行 ASR 右移運算，輸入正數：正數為已定義行為，不需要調整
## 測驗 `2`
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
OPQ = ?
`& 0x1`
逐步檢視程式的運作邏輯：
```cpp
(num & (num - 1))
```
此行確保數字轉為二進位只會有一個 1 ，即數字必為 2 的 n 次方
而要如何區隔 2 的次方和 4 的次方？觀察以下：
| 次方 (n) | 2^n | 右起第一個1之後的0個數 |
| ------------------------ | ------------------------- |:------------------------- |
| <font color="#f00">**0** | <font color="#f00">**1** | <font color="#f00">**0** |
| 1 | 2 | 1 |
| <font color="#f00">**2** | <font color="#f00">**4** | <font color="#f00">**2** |
| 3 | 8 | 3 |
| <font color="#f00">**4** | <font color="#f00">**16** | <font color="#f00">**4** |
| 5 | 32 | 5 |
| <font color="#f00">**6** | <font color="#f00">**64** | <font color="#f00">**6** |
| 7 | 128 | 7 |
可以發現 4 的次方以二進位表示後，右起第一個1之後的0個數一定會是偶數，因此最右邊的 bit 必為 0 ，以
```cpp
!(__builtin_ctz(num) & 0x1);
```
排除掉 least bit 為１的結果
接下來嘗試降低 branch 的數量
觀察以下：
| 次方 (n) | 2^n | leading zeros |
| ------------------------ | ------------------------- |:------------------------- |
| <font color="#f00">**0** | <font color="#f00">**1** | <font color="#f00">**31** |
| 1 | 2 | 30 |
| <font color="#f00">**2** | <font color="#f00">**4** | <font color="#f00">**29** |
| 3 | 8 | 28 |
| <font color="#f00">**4** | <font color="#f00">**16** | <font color="#f00">**27** |
| 5 | 32 | 26 |
| <font color="#f00">**6** | <font color="#f00">**64** | <font color="#f00">**25** |
| 7 | 128 | 24 |
可以發現 4 的次方以二進位表示後，其 leading zeros 的個數為奇數，因此我們可以改以
```cpp
(__builtin_clz(num) & 0x1);
```
取代
```cpp
!(__builtin_ctz(num) & 0x1);
```
這樣做的好處是
```cpp
(__builtin_clz(num) & 0x1);
```
要成立的話， num 必定為正數，因此可以把 num > 0 這個 branch 拔掉
最後程式變成：
```cpp=
bool isPowerOfFour(int num)
{
return (num & (num - 1)) == 0 && (__builtin_clz(num) & 0x1);
}
```
Leetcode 1009 ：
```cpp=
int bitwiseComplement(int N){
return N ? (0xFFFFFFFF >> __builtin_clz(N)) ^ N : 1;
}
```
由於本題限制輸入的 N 在 0~10^9 之間，因此可以直接使用右移，不用擔心系統是使用算術右移和邏輯右移。先做出一個和 N 的二進位表示時所需的最小長度等長，全為 1 的 mask ，在讓 N 和這個 mask 做 XOR 運算即可。只要對 0xFFFFFF 進行 __builtin_clz(N) 的右移就能得到這個 mask 。
Leetcode 41 ：
```cpp=
void swap(int* a,int* b){
(*a) ^= (*b);
(*b) ^= (*a);
(*a) ^= (*b);
}
int firstMissingPositive(int* nums, int numsSize){
for(int i = 0; i < numsSize; i++){
if(nums[i] < numsSize){
if(nums[i] != i+1 && nums[i] > 0){
int t = nums[i] - 1;
swap(&(nums[i]),&(nums[t]));
i--;
}
}
}
for(int i = 0; i < numsSize; i++){
if(nums[i] != i+1)
return i+1;
}
return numsSize+1;
}
```
遍歷整個陣列，把遇到的數字依序放入陣列的位置 ( 1 放在 nums[0] ， 2 放在 nums[1] 依此類推 ... ) ，最後再遍歷整個陣列一次，若遇到 nums[i] != nums[i+1] 則 i+1 即為題目所求。這題目前想不到用 clz 減少分支的做法。
## 測驗 `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/)
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
我們可以把題目理解為:
若 LSB = 0 則右移一位，否則減一使 LSB = 0
對任意數字，若其有 x 個位元是 1 ，則要有 x 步用來減 1 ，剩下的步數則用來右移。
我們可以用 __builtin_popcount(num) 求得 x 。
因為我們要右移的次數洽為使 MSB 移到 LSB 的步數。
對任意非零整數，使其 MSB 移到 LSB 所需的步數為 31 - __builtin_clz(num) 。
若 num 為 0 則 return 0 。
因此本題答案為
AAA = `__builtin_popcount(num)`
BBB = `__builtin_clz(num)`
以其他程式碼實作，避免用到編譯器的擴充功能實現 branchless 之等價實作:
```cpp=
const int tab32[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
int round_down_log2(uint32_t value) {
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[((uint32_t)((value - (value >> 1))*0x077CB531U)) >> 27];
}
int pct(uint32_t i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
int numberOfSteps (int num){
return pct(num) + round_down_log2(num);
}
```
參考 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz) ，我們可用 De Bruijn sequence 實作出無條件捨去的 log2 運算，其中對 x 進行無條件捨去的 log2 運算可視為使 x MSB 移到 LSB 所需的步數。
參考 [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) 中的 Counting bits set, in parallel ，我們可以實作出 popcnt 。(原理可參考 [the bit twiddler](https://bits.stephan-brumme.com/countBits.html) )
而所求為要減幾次 1 的次數 + MSB 移到 LSB 所需的步數，因此答案為 pct(num) + round_down_log2(num)
## 測驗 `4`
答案為
XXX = `(b)` `v`
YYY = `(a)` `u << shift`
```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 (v);
return u << shift;
}
```
### 解釋程式運作原理
$$gcd(a,b)=2^{shift}*gcd(c,d) \\where \ a=2^{shift}*c\ ,b=2^{shift}*d$$
程式先將兩數中 2 的 shift 次方的共同因數提出來，然後把任一邊的 2 的因數消掉，之後就是進行一般的輾轉相除法，再把最後的結果乘上 2 的 shift 次方。
### 以 __builtin_ctz 改寫 GCD :
```cpp=
#define min(x,y,r) \
r = y ^ ((x ^ y) & -(x < y))
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
min(__builtin_ctz(u),__builtin_ctz(v),shift);
u >>= __builtin_ctz(u);
v >>= __builtin_ctz(v);
do {
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
### 效能比較
我先用亂數產生 100000 筆數據並使用 perf 觀察 gcd 程式的運作情形
其中 1 2 3 分別為題目原來的 gcd ， 提出 2 的 shift 次方的 gcd 和 以 __builtin_ctz 改寫的 gcd ，以 -O3 編譯
1.
2.
3.
可以看到，以 __builtin_ctz 改寫的 gcd (3) 相較提出 2 的 shift 次方的 gcd (2) 在時間上快了約 28.6% ， cycles 也少了約 4270 萬
而相較於題目原本的 gcd 寫法 (1) 則在時間上快了約 21.6% ， cycles 也少了約 2978 萬
:::info
在使用不同數量的亂數測資時發生了一個現象，當測資的數量足夠大時，程式會產生大量的 cache-misses ，目前不知道該怎麼減少因為測資數量產生的 cache-misses
:::
## 測驗 `5`
### bit array 的應用:
- 影像處理
- bloom filter
- linux kernal(allocation of memory pages, inodes, disk sectors, etc.)
### 程式原理解釋
先看題目原本給的程式碼:
```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;
}
```
這個程式在做的事情就是計算 bitmap 中有幾個 bit 是 1 ，把計算出來的總數存入 pos ，並把每個是 1 的 bit 的 index 存到 out 中。其中第 9 行的判斷式可改為先把 trailing zero 跳過，直接從第一個非零的 bit 開始記錄 index :
```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;
}
```
當我們把第一個非零 bit 算出來之後，就把那個 bit 變成 0 ，接下來繼續往下算。
數字總共只有偶數和奇數兩種，而我們知道電腦的二補數運算為 (假設 N 為整數)
$$N = NOT(-N) + 1$$
這個特性使得
$$ N \ AND\ (-N) $$
所得的 binary 數必為除了 N 的第一個非 0 bit 為 1 外其餘皆為 0
因此當我們讓
$$ N \oplus (N\ AND \ -N) $$
就能只把第一個非 0 bit 變成 0 其餘保持不變了。
因此本題答案為
KKK = `e` `bitset & -bitset`
設計實驗測試效能 :
首先我設了三個長度為 10000 的陣列 data0 data1 data2並用 perf 測試，其中 data0 所有元素皆為 0 ， data1 所有元素皆為 0xffffffffffffffff ， data2 則為亂數產生的 64 位整數
為了方便 perf 使用，我利用 argv 讀取外部傳入的參數
以下簡述參數的定義 :
執行時輸入兩個參數 [模式] [資料]
第一個參數 :
0 表示使用 naive 處理資料
1 表示使用 improved 處理
第二個參數 :
0 表示使用 data0 作為資料
1 表示使用 data1 作為資料
2 表示使用 data2 作為資料
程式本身以 O1 編譯
先測試 data0 ( 全元素為 0 ) :
naive :
improved :
可以看到 improved 相較 naive 約快了 49.4%
接著測試 data1 ( 全元素為 0xffffffffffffffff ) :
naive :
improved :
可以看到這時 naive 相較 improved 快了約 20% ，推測是因為一開始每個 bit 都是 1 ，用 ctz 不但不會省時間反而還多耗了一些時間成本。
最後測試 data2 :
naive :
improved :
可以看到 improved 相較 naive 約快了 50.5%
因此除非確定所用的資料中的 1 密度非常高，大多時候用 ctz 的寫法應能更有效率。
Sign in with Wallet
Connect another wallet