---
tags: Linux2020
---
# 2020q3 Homework3 (quiz3)
contributed by < `YLowy` >
> [GitHub](https://github.com/YLowy/quiz3)
## 測驗 1
有號整數的跨平台 ASR (arithmetic right shift) 實作
```cpp=
#include <stdio.h>
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) >> 1) > 0;
unsigned int fixu = -(logical & (m < 0));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
int main(){
int shift = 4;
unsigned int x = 0xFFFFFFF0;
// undefined behavior
printf("%x >> %d = %x \n",x,shift,x>>shift);
printf("%x >> %d = %x \n",x,shift,asr_i(x,shift));
}
```
#### 想法:
最主要就是希望能知道針對此 unspecific behavior 行為中，補入最高位元是 0 或者 1
##### 第一行
`const int logical = (((int) -1) >> 1) > 0;`
(int) -1 = 0xFFFFFFFF
所以可以透過 >>1 判斷右移動後補入是 0 或者 1
如果 系統會補入 0 :
logical = 0x0111..1u > 0 = true = 0x00000001
如果 系統會補入 1 :
logical = 0x1111..1u > 0 = false = 0x00000000
###### 第二行
`unsigned int fixu = -(logical & (m < 0));`
如果 系統會補入 0 :
fixu = -(0x00000001 & m < 0) =0x000000001
如果 系統會補入 1 :
fixu = -(0x00000000 & m < 0) = 0x00000000
所以如果在 " 系統會補入0 " & " m 為負數 " 時候， fixu = 0x11111111
其餘情況 fixu = 0x00000000
###### 第三行
`int fix = *(int *) &fixu;`
如果在 " 系統會補入0 " & " m 為負數 " 時候， fix = -1 其餘時候為 0
###### 第四行
`return (m >> n) | (fix ^ (fix >> n));`
在 " 系統會補入0 " & " m 為負數 " 透過 " | " 讓前面補的 0 變成 1 ;
### 延伸問題
1. 練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度
## 測驗 2
找四的冪
LeetCode 342. [Power of Four](https://leetcode.com/problems/power-of-four)
先觀察 `(num & (num - 1)` :
0x0001101 & 0x0001100 = 0x0001100
0x0001000 & 0x0000111 = 0x0000000
此操作是讓最後一個 1 bit 轉成為 0
再來觀察 4 的次方數:
$4^{0}$ = 0x00000001
$4^{1}$ = 0x00000100
$4^{2}$ = 0x00010000
$4^{3}$ = 0x01000000
可以觀察到這些次方數表示成 2 進位 :
1. 只存在一個bit 1
2. bit 1 後面的 0 的數量為 2 的倍數
3. $4^{n}$ > 0
上述整理:
1. ` (num & (num - 1) == 0 `
2. ` __builtin_ctz(num) ` 得到該數後面 0 bits 數量
又因為要為2的倍數，最後的 bit 要為 0
可以透過 該數 & 0x00000001 的結果判斷，如果輸出為 0 則代表該數為2的倍數
3. ` num > 0 `
整理上述可以得到結果 :
```c=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) & 0x1);
}
```
### 延伸問題
1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
2. 練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive，應善用 clz
3. 研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告
## 測驗 3
__builtin_popcount(x) 實作有點厲害
LeetCode 1342. [Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
也就是說給定一個數，只能透過 " -1 " 以及 " /2 " 讓該數變成 0
而這兩項操作都可以透過 bit operator 完成
可以想成 : 在二進位表示中要把多少 1 轉成 0 以及 總共要多少次右移
1. 有多少個 1 :
`__builtin_popcount(num)`
2. 總共要多少次右移 :
最高位元的 1 要 shift 到最低 bit ,可以想成 32 - 最高位元位置
=> 32 - " 為 1 的最高位元前面有多少個 0 " + 1
=> `31 - __builtin_clz(num)`
以上兩個為總動作數
```c=
int numberOfSteps (int num)
{
return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}
```
### 延伸問題
1. 改寫上述程式碼，提供等價功能的不同實作並解說
2. 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode 1342. Number of Steps to Reduce a Number to Zero，實作出 branchless 解法，儘量縮減程式碼行數和分支數量
## 測驗 4
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 (v);
return u << shift;
}
```
兩個演算法之間其實只多了一個觀念:
在 2 進位表示法中可以簡單快速的判斷數字是 $2^n$ 的倍數，所以先把 $2^n$ 先行提出再做輾轉相除法
```
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
這裡就是找出 n 最大的 $2^n$ 公因數，n 紀錄再 shift 中並且之後可以對結果直接進行左移操作
```
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
```
再來由於 2 的 因數都判斷完成，我們可以把2的因數從兩邊先行抽離，運用比較小的數進行輾轉相除
注意 : `(v & 1)` 是第 2 題使用到判斷2的倍數的技巧
```
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
```
接下來就是普通的輾轉相除法
回傳的值要左移第一階段的 shift
### 延伸問題
1. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
## 測驗 5
先從最原本題目開始理解
```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;
}
```
輸入為一個 unit64_t Array
假設我們該陣列設定為:
```c =
bitmap[0] = 0x0000000f;
bitmap[1] = 0x00001000;
bitmap[2] = 0x00000000;
bitmap[3] = 0x00000000;
bitmap[4] = 0x00000000;
bitmap[5] = 0x00000000;
bitmap[6] = 0x00000000;
bitmap[7] = 0x00000000;
```
輸出 pos 為該 bitmap 中有多少的 "1"
out 為一個陣列紀錄該陣列中第幾個位置為 "1"
也就是說 out[pos] 為該 bitmap 中 最後的 "1" 的位置
:::danger
文字訊息不要用圖片展現
:notes: jserv
:::
以這次所設定範例其輸出:
```
$ ./quiz3Q5_2
pos = 5
-------------------------
output[0] = 0
output[1] = 1
output[2] = 2
output[3] = 3
output[4] = 76
```
再來透過 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 = bitset & -bitset;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
其實在觀察改寫前的程式碼中我們可以發現他是對於每一個 bit 進行觀察，在做 branch 時候可能會造成 flush 成本
整合一下我們所在課堂中提到的部分:
`(num & (num - 1)` 最後一位 1 轉為 0
` __builtin_ctzll()` 計算有多少 tail 0
我們可以透過上述兩個方式以另一種方式得到相同結果，先找到第一個 1 的位置，再將其轉成為 0 再找下一個
這樣有機會達到更快的效果
### 延伸問題
1. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density
2. 思考進一步的改進空間
Sign in with Wallet
Connect another wallet