2020q3 Homework3 (quiz3)
===
contribute by `Liao712148`
* 1.從新回答[第3周測驗題](https://hackmd.io/@sysprog/2020-quiz3)
###### tags: `進階電腦系統理論與實作`
### 測驗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));
}
```
>“The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is ==implementation-defined==.”
因為在 C 語言中，對有號型態的物件進行算術右移，歸屬於==unspecified behavior==所以要先判斷，此環境在對有號數作算是右移時，是會根據`most significant bit`補充，還是會補0。
* 若是會根據`most significant bit`補充，則`m>>n`即為答案。
* 若是僅會補充0，
* 如果`m>0`則`m>>n`即為答案。
* 如果`m<0`則要將`m>>n`補充的0改為`1`才行
由第`3`行可以確認，此環境對於有號數算數右移是否會根據`most significant bit`補充
`logical=1`表示僅會補充0，`logical=0`表示會根據`most significant bit`補充
所以`OP1`要選擇`>>1`
如果`m>0`則不用考慮有號數為移的==undefined havior==
如果`m<0`且算數右移僅會補充0，則要對補充的0轉換成1
所以`OP2`要選擇`m<0`
所以在需要做修正的時候，`fixu`會是0x11111111，否則為0x00000000，再透過```| (fix ^ (fix >> n))```，就可以把右移的位元都補成`1`，以符合所求。
#### 延伸問題
* 練習實作其他資料寬度的 `ASR`，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度;
參考[RinHizakura](https://hackmd.io/@RinHizakura/SkjPS8vBP#%E6%B8%AC%E9%A9%97-1)
C11 提供了 _Generic 選擇，用來模擬泛型程式，其本質是類似 switch 的選擇陳述，不過是編譯時期根據型態來選擇展開的對象。並且減少相似的程式
```cpp=
#define asr_i(m,n) \
_Generic((m), \
int8_t : asr_i8, \
int16_t : asr_i16, \
int32_t : asr_i32, \
int64_t : asr_i64 \
)(m,n)
#define asr(type) \
const type logical = (((type) -1) >> 1) > 0; \
u##type fixu = -(logical & (m < 0)); \
type fix = *(type *) &fixu; \
return (m >> n) | ((fix >> n) ^ fix)
int8_t asr_i8(int8_t m, unsigned int n)
{
asr(int8_t);
}
int16_t asr_i16(int16_t m, unsigned int n)
{
asr(int16_t);
}
int32_t asr_i32(int32_t m, unsigned int n)
{
asr(int32_t);
}
int64_t asr_i64(int64_t m, unsigned int n)
{
asr(int64_t);
}
```
### 測驗2
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
此題要判斷輸入的數是否是4的冪次($4^n$)可以看成$2^{2n}$，其中==n為正整數==，所以我們先從數字是不是2^{2n}下手，透過觀察可以發現$2^{2n}$在其數值的most significant bit position之後必須全為才有可能會是$2^{2n}$。
所以透過``(num & (num - 1))==0``可以判斷是我們上述的假設，舉例來說:
若``num=16``
$num=0010\ 0000_2$ $num-1=0001\ 1111_2$兩者作`&`可以滿足上述的判斷式
若``num=17``
$num=0010\ 0001_2$ $num-1=0010\ 0000_2$兩者作`&`不會滿足上述的判斷式
現在已經確定數字會是2的冪次，再來判斷是否是4的冪次，由數學式可以得知$2n$必須要是$>0$的偶數。利用`__builtin_ctz(num)`算出數字尾端0的個數如果是奇數則不會是4的冪次，例如``num=8``
`__builtin_ctz(num)會回傳3`
如果是偶數則會是4的冪次`num=16`則`__builtin_ctz(num)會回傳4`
所以``OPQ``要選可以判斷奇偶數的`&0x1`
#### 延伸問題
* 改寫上述程式碼，提供等價功能的不同實作，盡量降低branch的數量
在return的表示式，要先判斷`num`是否大於0，以及`(num & (num - 1))==0`是否成立，如果可以利用`int __builtin_popcount (unsigned int x)`來判斷`1`的個數，則可以透過以下的方式將上面檢查2個條件的判斷式縮減為以下
```cpp=
bool isPowerOfFour(int num)
{
return __builtin_popcount(num) == 1 &&
!(__builtin_ctz(num) & 01);
}
```
這樣就只要判斷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;
* 針對[1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
我的想法是利用`XOR`將數字0，1進行翻轉，舉例如下:
以`int`8位元舉例，`N=5`轉成2進位後
`00000101`和`11111111`作`XOR`可以得到`11111010`，再對`11111000`作`XOR`將bit轉成0即可
```cpp=
int bitwiseComplement(int N){
return N ? ((1 << (32 - __builtin_clz(N))) - 1) ^ N : 1;
}
```
因為當`N=0`時`__builtin_clz(N)`是`undefined`所以將`N=0`獨立出來處理
>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==.
*針對[41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
以下提供一個簡單粗暴的方法，我們可以宣告一個陣列`array`，來記錄`nums`中存在哪一些元素，將`nums`中的正數，依照其數值大小存放入`array`陣列中的相應為位子，並且將`nums`中大於`numsSize`的正數捨棄，因為比`numsSize`大的正數一定不會是我們要找的`nums`中缺失的最小正數。`array`完成後就可以快速地找出`nums`中缺失的最小正數。
```cpp=
int firstMissingPositive(int* nums, int numsSize){
int array[300] = {0};
for (int i = 0; i < numsSize; i++) {
if (nums[i] > 0 && nums[i] <= numsSize)
array[nums[i] - 1] = 1;
}
int i;
for (i = 0; i < numsSize; i++) {
if (array[i] == 0)
break;
}
return ++i;
}
```
附上在 leetcode 中執行正確且通過的證明：
:::warning
需要設法減少`array`的儲存空間
:::
---
### 測驗3
```cpp=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
以下是參考`Noahnut`同學的想法
根據題目的規定，我們可以發現將一個不為0的偶數不斷作算數右移，最後
`least siginificant bit oisition`會是`1`(奇數)，所以要多作一個`-1`的動作，使得該數值變成`0`則運算結束，或是不為0的偶數則回到上一步驟。
所以一個數字要完成題目的規定，可以簡化成`1`的個數(可以計算出要作幾次`-1`的動作)+將最高位的`1`作運算右移，推至`least significant bit position`所需要的次數。
因為題目規定`num`不為負數，所以`num`>`0x80000000`,可以將最高位的`1`作運算右移，推至`least significant bit position`所需要的次數，改成`31-__builtin_clz(num)`
`AAA`選擇`__builtin_popcount(num)`
`BBB`選擇`__builtin_clz(num)`
#### 延伸問題
* 改寫上述程式碼，提供等價功能的不同實作並解說
* 避免用到編譯器的擴充功能，只用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`解法，盡量縮減程式碼行數和分支數量
利用測驗3提供的方法可以避免使用編譯器擴充功能，來計算數值在二進位制中`1`的個數。
```cpp=
unsigned popcnt_branchless(unsigned v) {
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
int naive(unsigned v) {
int i = 0;
while (v >> i)
++i;
return i;
}
int numberOfSteps (int num) {
int temp = popcnt_branchless(num);
temp += naive(num);
return num ? --temp : 0;
}
```
附上在 leetcode 中執行正確且通過的證明：
---
### 測驗4
```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;
}
```
* **Binary GCD**
>binary gcd 的精神就是，當兩數是偶數時，必有2的因子
$gcd(x,y)=2\times\gcd(\dfrac{x}{2},\dfrac{y}{2})$
且一數為奇數，一數為偶數($y$)，則無2因子
$gcd(x,y)=2\times\gcd(x,\dfrac{y}{2})$
如果兩數皆是奇數則
$gcd(x,y)=2\times\gcd(\dfrac{|x-y|}{2},y)$
直到$x=y$或$x=0$，此時GCD為$2^k\times y$, k為兩個偶數出現的次數
將觀念帶入此題，因為如果兩個數都是偶數，則他們會有2的因式，所以透過`5,6,7`行，將兩個數2的因式取出。執行完`5,6,7`行後會是一奇一偶，或兩個奇數，因為一奇一偶不會有2的因式所以要將偶數2的因數除掉。
`10~20`行是輾轉相除法，將大數不斷減去小數，直到有一個數先為`0`則停止。所以`XXX`選`v`
,再將兩奇數的因式提出，並乘上`5,6,7`行算出的2的因式，即為所求。所以`YYY`選`u<<shift`。
#### 延伸問題
* 在`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;
}
```
由`8,9,10`行的expression可以知道，我們要把bitset中數值為1的位子找到
```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;
}
```
此題`8~13`實現上面`8,9,10`的功能，所以我們利用不斷的將最靠近`least significant bit`的$1$消掉，這樣就可以透過`__builtin_ctzll`算出下一個$1$的位子。
根據[statck overflow](https://stackoverflow.com/questions/12818978/meaning-of-number-number)
可以知道
>Assuming $2's$ complement (or that $i$ is unsigned), $-i$ is equal to $~i+1$. $\ i$ & $\ (~i + 1)$is a trick to extract the lowest set bit of $i$.
所以`KKK`要選擇`bitset&-bitset`
#### 延伸問題
* 設計實驗，檢驗`clz`改寫的程式碼相較原本的實作有多少改進?應考慮到不同的[bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html)
* 思考進一步的改進空間
Sign in with Wallet
Connect another wallet