# 2020q3 Homework3 (quiz3)
contributed by < `Sisker1111` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz3)
>
## 1. ASR
考慮到程式碼的相容性，目的是實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:
`-3 是 (-5) / 2 的輸出，並往負無限大的方向前進`
```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));
}
```
* logical 是用來判斷 compiler 的 >> 是 logical shift 還是 arithmetic shift.
* 若是 arithmetic shift ， logical 會是 0 且 fixu = 0，第 6 行的`fix ^ (fix >> n)`會變成`2b'000.....0 ^ 2b'000.....0 = 2b'000.....0`(不影響結果)
* 若是 logical shift ， logical 會是 1 且 fixu = 111.....1( 32 個 1)，第 6 行的`fix ^ (fix >> n)`會變成`2b'111.....1 ^ 2b'000.....1 = 2b'111.....0`( 1 的數量等同 n)
## 2. int __builtin_ctz & int __builtin_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](https://leetcode.com/problems/power-of-four/)，假設 int 為 32 位元寬度。實作程式碼如下:
```c=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
此題是要確認該數字是否為 4 的冪次方，若該數為 4 的冪次方 32bits 中只會有 1 個 bit 為 1 且該 bit 右邊的 bits 數量應該偶數個，`num > 0 && num & (num-1)`首先確認該數是否為正數且只有 1 個 bit 為 1，`!(__builtin_ctz(num) & 0x1)`則是在判斷右邊0的數量是否為偶數個.
### 不同的實作
`(num & (num - 1))==0`的部分可以使用`!(__builtin_popcount(num) ^ 1)`來代替，原本想用 `__builtin_clz(num)` 來代替`num > 0`，但會因為 undefined behavior <s>噴 compiler error</s>.
:::danger
避免說「噴 compiler error」這樣不精準的話，因為
1. 閱讀者無法區分是 internal compiler error (ICE，在 gcc 開發過程中常見)，抑或是你遇到編譯器拋出的一般錯誤訊息;
2. 漢語的「[噴](http://dict.revised.moe.edu.tw/cgi-bin/cbdic/gsweb.cgi?ccd=it446W&o=e0&sec=sec1&op=v&view=0-1)」意義和上述的編譯器行為無涉;
你可額外加上 `num > 0` 的檢查條件，置於 clz 呼叫之前
:notes: jserv
:::
### 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/submissions/)
```c=
int bitwiseComplement(int N) {
if(!N)
return 1;
int offset = (1 << (32-__builtin_clz(N)) ) - 1;
return N ^ offset ;
}
```
* Runtime : 0 ms, faster than 100.00% of C++ online submissions.
Memory Usage : 6.1 MB, less than 40.99% of ...
### 練習 LeetCode [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
```c=
int firstMissingPositive(vector<int>& nums) {
if(nums.size()==0) return 1;
for(int i=0; i<nums.size(); i++){
if(nums[i] > 0 && nums[i] <= nums.size()){
int pos = nums[i]-1;
if( nums[pos] != nums[i]){
nums[pos] ^= nums[i];
nums[i] ^= nums[pos];
nums[pos] ^= nums[i];
i--;
}
}
}
for(int i=0; i<nums.size(); i++){
if(nums[i]!=(i+1))
return i+1;
}
return nums.size()+1;
}
```
* Runtime : 4 ms, faster than 79.63% of C++ online submissions.
Memory Usage : 9.9 MB, less than 49.44% of ...
## 3. __builtin_popcount
針對 LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```cpp=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
32 bits 內的 bit = 1 的數量等同要執行 subtract 的次數，因此可以很容易之道`AAA`的答案應為`__builtin_popcount(num)`，執行完`__builtin_popcount(num)`後我們還需要向右移動 1 個 bit，透過`__builtin_clz(num)`我們可以找到最左邊的 1 在哪個位置，找到後用
`31-__builtin_clz(num)`就可以知道應該向右 shift 幾次，所以 `BBB`為`__builtin_clz(num)`.
## 4. 64-bit GCD
考慮以下 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;
}
```
1. 5~7 行檢查 u、v 是否皆為偶數(或是講是否能一起除以2)，因為`gcd(u,v) = 2*gcd(u/2,v/2)`
2. 8~10 行檢查 u 是否為偶數，如果 u 為偶數則 v 為奇數，所以`gcd(u,v) = gcd(u/2,v)`
3. 11~12 行檢查 v 是否為偶數，如果 v 為偶數則 u 為奇數，所以`gcd(u,v) = gcd(u,v/2)`
4. 然後剩下的其實就是輾轉相除法，並且會確保進入下一個迴圈的 v 是比較小的那個值，重複直到進入這次輾轉相除時的 u 和 v 相同，因此 `XXX = v`
5. 最後 return 要把 gcd 往左邊 shift 最開始除以2的次數，才能得到正確的值，固`YYY = u << shift`.
### 透過 __builtin_ctz 改寫
注意到下面的實驗中會將 quiz3 中題目的作法命名為 fast gcd，使用 __builtin_ctz 調整後的版本則稱為 faster gcd 以方便解釋。
前面的 `for (shift = 0; !((u | v) & 1); shift++)` 迴圈可以使用 __builtin_ctz 來改寫為如下:
```cpp=
#ifndef min
#define min(x, y) ((x) < (y) ? (x) : (y))
#endif
uint64_t faster_gcd64(uint64_t u, uint64_t v){
if (!u || !v)
return u | v;
int shift = min(__builtin_ctz(u), __builtin_ctz(v));
u >>= shift; v>>= shift;
while (!(u & 1))
u >>= 1;
do {
while (!(v & 1))
v >>= 1;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
## 5. bit array
在影像處理中，[bit array](https://en.wikipedia.org/wiki/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;
}
```
看向原 Code 第 9 行，目的是要從最右邊的 bit 開始 check 是否為 1，下面改寫的版本把 for 改成 while，`bitset & -bitset`是把 `bitset` 與 `-bitset` 的 2 的補數做 & ，這樣即可得到最右邊 bit 數為 1 且其他 bits 皆為 0 的 bitmap，最後第 12 行是用來將最右邊 1 改為 0，這樣下次`__builtin_ctzll(bitset)`就不會找到錯誤的 bit .
Sign in with Wallet
Connect another wallet