# 2020q3 Homework3 (quiz3)
contributed by < `ccs100203` >
###### tags: `linux2020`
> [第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
:::info
TODO 延伸問題 5
:::
## 測驗 1
```cpp=
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));
}
```
- 第三行的 `logical` 是用來判斷現在的 shift 屬於 arithmetic 還是 logical 的 shift，如果 -1 >> 1 過後會大於 0，代表這個系統的 shift 屬於 logical，反之為 arithmetic。
- 第四行的 `fixu` 判斷是否需要進行 signed bit 的修正，如果需要的話就會產生出 -1，也就是 0xffffffff，反之則會產生 0。
- 第六行可以看到先做 m >> n，然後使用 `fix` 來修正 signed bit。
- 原理是當 `fixu` 為 -1 時，代表現在是 logical shift，且需要進行修正
在 fix >> n 過後會產生出 n 個 0 以及 32 - n 個 1，假設 ==n = 3== 即為 000111...11
此時會變成 (只舉出前 8 bit)
| | 0<br>(MSB) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| -------- | - | - | - | - | - | - | - | - |
| fix >> 3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| fix | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
這時將兩者做 XOR 就會產生前面為 n 個 1 後面是 32 - n 個 0 的數字
| | 0<br>(MSB) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| -------- | - | - | - | - | - | - | - | - |
| after xor | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
這樣就能利用 `(m >> n) | (fix ^ (fix >> n))` ，將前面理應為 1 卻被改成 0 的 bits 改回 1。
- 如果 `fixu` 是 0，那麼不論是做 shift 或是 xor 的結果都會是 0
這樣在 `(m >> n) | (fix ^ (fix >> n))` 就等同於 `(m >> n) | 0`，不需要對正確的 `(m >> n)` 做出任何修改。
:::warning
int fix = *(int *) &fixu;
不懂為什麼要這麼做
:::
:::danger
去觀察產生的機械碼，在 gcc 記得對照 `-O0` (抑制最佳化) 和 `-Os` (對空間使用最佳化) 的輸出，找出關聯。
:notes: jserv
:::
:::warning
比較機械碼後尚未理解原因
:::
## 測驗 2
[Leetcode 342. Power of Four](https://leetcode.com/problems/power-of-four/)
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) & 0x1);
}
```
這題我們要判斷 num 是否為 power of 4
1. `num > 0` 過濾掉所有負數
2. `(num & (num - 1))==0` 這可以用來判斷是否為 power of 2，下面解釋原理
如果一個數字屬於 power of 2，那他在二進位表示下必定只有一個 1，代表他是 2 的某個次方。
以 $2^n$ 來看，就會是 1 加上 n 個 0。那麼在 num - 1 之後必然會變成 0 + n 個 1。
100...00 & 011...11 的結果就會是 0。其餘的情況都不會是 0
3. 到這裡我們已經可以判斷出是不是 power of 2，再來要藉由 `!(__builtin_ctz(num) & 0x1)` 萃取出 power of 4。
先了解 power of 4 跟 power of 2 比起來會有什麼限制，power of 4 不僅只能有一個 1，他的 1 還必須要在偶數的位置。因為 $2^{2n}$ 等同於 $4^n$，所以這邊要找出 num 是偶數還是奇數個 0。所以在做 `__builtin_ctz(num) & 0x1` 之後，偶數個 0 就會得到 0，奇數個 0 就會得到 1，因為只有奇數與 0x1 做 AND 可以得到 1。這時經過 `!1` 就會得到 0， `!0` 就會得到 1，就能得出結果。
### 延伸問題
#### 1. 提供等價功能的不同實作
```cpp
bool isPowerOfFour(int num){
return (__builtin_popcount(num) == 1) && !(__builtin_ctz(num) & 0x1);
}
```
除去了 branch，利用 power of 4 只有一個 1 的特性，藉由 `__builtin_popcount(num) == 1)` 去計算。 `!(__builtin_ctz(num) & 0x1)` 的部份一樣用來判斷 1 的位置是否為奇數。
#### 2. [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
```cpp
int bitwiseComplement(int N){
return N ? ~N & ((unsigned int)-1 >> __builtin_clz(N)) : 1;
}
```
- 利用 `__builtin_clz` 算出前面有 m 個 0，那麼答案的前面 m 個 bits 也該是 0
- `(unsigned int)-1` 需要轉換是因為 unsigned 的時候是 logical right shift，左邊才會補 0 而不是 1
- 這樣就得到一個 mask，利用這個 mask 與 `~N` 做 and 就是答案
:::warning
1009\. 尚未想出不用 branch 的方法
:::
#### 3. [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
```cpp=
#define swap(a, b) (a^=b, b^=a, a^=b)
int firstMissingPositive(int* nums, int numsSize){
for(int i=0; i<numsSize; ++i){
int tmp = nums[i] - 1;
if( nums[i] > 0 && nums[i] <= numsSize && tmp != i && nums[i] != nums[tmp]){
swap(nums[i], nums[tmp]);
i--;
}
}
for(int i=0; i<numsSize; ++i){
if( nums[i] != i+1)
return i+1;
}
return numsSize + 1;
}
```
題目要我們找出給定數列中所缺少的正整數值
一開始想利用 conunting sort 的方式，做一個利用 index 去紀錄數量的 array，但後來想起他只需要判斷數值是否存在，不需要紀錄數量，所以就不用額外創造 array 去紀錄。方法就變成說當我遇到一個範圍內的數字 n，我就把他放到 n-1 的位置，最後只要巡遍 array 就可以知道缺少什麼數字。
解釋程式碼
- for 迴圈的運作
- `nums[i] > 0` 只處理正整數
- `nums[i] <= numsSize` 避免 index out of bound
- `tmp != i` 如果 n 已經在他該在的位置 (n - 1)，那麼不做 swap，因為進行 swap 會讓他變成 0
- `nums[i] != nums[tmp]` 如果目標位置已經是正確的數值的話則不更換。在提交時遇到測資 [1, 1] 而新增的，避免程式無窮迴圈不結束
- 解釋 swap 原理： 使用 XOR SWAP 的技巧，好處是不需要使用額外的空間
- 下表是解釋 xor swap 如何運作
- | | A | B |
| :------: | :------: | :------: |
| a ^= b | A xor B | B |
| b ^= a | A xor B | A |
| a ^= b | B | A |
- `int tmp = nums[i] - 1;` 使用 tmp 是因為直接做 `nums[nums[i] - 1]` 會遇到 Heap-buffer-overflow 的問題，查了一下發現是 leetcode 使用 AddressSanitizer 的關係。
:::warning
41\. 尚未想出使用 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/)
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.
```cpp=
int numberOfSteps (int num)
{
return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}
```
這題要計算幾個步驟可以變成 0，遇到偶數會直接除 2，奇數則會減 1。
1. `__builtin_popcount(num)` 可以知道有多少 1，每一個 1 需要用 -1 的方式來消除他，所以算出有多少 1 就可以知道總共需要 ==-1== 幾次。
2. `31 - __builtin_clz(num)` 的部分，藉由用 32 - 前面有幾個 0，來算出總共有多少位數。
假設 num = 3 就會得到 2，代表總共用到 2 個 bits，前面都是 0。
因為我們需要把最高的 bit 不斷除 2 往右推，直到剩下 LSB 是 1 為止，算出有多少位數可以得知總共需要做幾次的 ==/ 2==。所以就可以知道為什麼是用 31 而不是用 32 去做減法，因為 MSB - LSB 是 31，他最多往右推 31 次，於是用 31 去減前面有多少 0 得到想要的結果。
假設 num = 75，那他總共有 4 個 1，而==最高的 bit== 減去 LSB 為 6，所以答案就是 4 + 6 = 10
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7<br>(LSB) |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:----------:|
| 75 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
### 延伸問題
1. 提供等價功能的不同實作
```cpp
int numberOfSteps (int num)
{
return __builtin_popcount(num) + 31 - __builtin_clz(num | 1);
}
```
會需要 branch 是因為 `__builtin_clz` 的參數不能為 0，所以我在做 `(num | 1` 之後就能讓他不會是 0。因為 leading zero 不會被這個 1 所影響所以這方法可行。
2. 避免用到編譯器的擴充功能
TODO
## 測驗 4
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;
}
```
可以看出這個就是基本的利用輾轉相除法去找 GCD
測驗中需要改為以下的方式
```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;
}
```
- 第 5~6 行的地方是先讓 u,v 同除 2，直到不能整除，同除多少次會記錄到 shift 裡。經過這邊之後 2 就不再會是 GCD 裡的數字了，所以不論是在第 8 行或第 11 行，都是在把 2 提前移除掉。因為在一個偶數一個奇數的情況下 $gcd(u,v) == gcd(\frac{u}{2}, v)$。
- 剩下的部分其實就是輾轉相除法，只是不用 `%` 去做，利用 $gcd(u-v,v) == gcd(u,v)$。輾轉相除法中止條件為 $gcd(u,0)$，代表 `while(0)` 會中止。那就是 v = 0 的時候。
~~- `u << shift` 則是因為一開始兩者同除 shift 次的 2，需要在最後把他補回來。~~
:::danger
避免說「把他補回來」。第一，這不是「擬人法」風格的書寫，而該是技術報告。第二，你到底「補」什麼呢？說清楚！
:notes: jserv
:::
:::success
hotfix in 9/30
:::
- 因為在第 5~6 行的時候同除 2 並把次數記錄到 shift 裡面，代表真實的答案應為 $2^{shift} * u$，所以最後需要做 `u << shift`，把之前先除掉的 $2^{shift}$ 乘回來。
### 延伸問題
```cpp
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift = 0;
shift = __builtin_ctz(u | v);
u >>= shift;
v >>= shift;
if (!(u & 1))
u >>= __builtin_ctz(u);
do {
if (!(v & 1))
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
利用 `__builtin_ctz` 改寫程式，將原本程式碼需要除 n 次 2 的地方全部使用 `__builtin_ctz` 改寫，原本需要用 while 去做除 2 直到不能除，使用 `__builtin_ctz` 就可以一次 shift 好，把右邊的 0 全部除掉。
## 測驗 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;
}
```
將上述程式碼轉換為以下程式
```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;
}
```
雖然不清楚整個程式想做什麼，但老師上課說會應用在訊號處理中判斷單位內的訊號量。
:::danger
何不找訊號處理的材料來研讀呢？
:notes: jserv
:::
我們需要釐清程式想做什麼，通過 `naive` 可以看出他想要藉由 `bitset` 與 `bitmap` 去計算出有多少 1 (有多少資訊量)，將結果儲存在 `out`。
#### 解析 `improved` 的版本
1. 在 `naive` 中需要一次檢查一個 bit 並全部檢查完，沒有效率。
2. 在 `improved` 中使用 `__builtin_ctzll(bitset)` 來找最右邊的 1，然後就可以直接把資訊放進去 `out` 裡面。
3. 這時會遇到一個問題，我們避免逐一走訪所有的 bit (在 `naive` 中用 for 去處理)，但又使用 `__builtin_ctzll(bitset)` 去找 1。**解決方法是當我們每次找到 1 時，我們就把最右邊的 1 設為 0。**
4. 可以看到 `bitset ^= t`，我們要透過 xor 把最右邊的 1 設成 0，但卻又不能動到其他 bits，很明顯就是要把對應到的 bit 在 `t` 設成 1，而其他全為 0。
5. 使用 `bitset & -bitset` 我們就可以得到想要的 `t`，通過二補數的轉換可以知道這個結果。 (不知道怎麼解釋原理，<s>不過就是這樣子</s>)
:::danger
務必使用精準詞彙，不要說「就是這樣子」，及早脫離文組^TM^
:notes: jserv
:::
:::success
hotfix in 9/30
:::
從補數系統可以知道，`num & ~num == 0`。而 `-num` 是使用二補數轉換，可以想成 `~num + 1`，做了這個 +1 之後，會根據二進位的加法把最右邊的 1 一路往左進位，直到遇見第一個 0。
而根據一補數的特性 `~bitset` 中最右邊的 0，就會剛好是 `bitset` 中最右邊的 1。代表通過 `-bitset`，我們可以得到一個與 `bitset` ，在其最右邊的 1 左邊的每個 bit 都相反，其餘都相同的數字。(二補數的特性)
於是我們就能利用 `bitset & -bitset` 製作出理想的 mask。
最後做 `bitset ^= t`，就能把最右邊的 1 clear，避免重複計算。
從下面的範例看會比較清楚
- 範例
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7<br>(LSB) |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:----------:|
| bitset | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| ~bitset| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| -bitset| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| t | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
Sign in with Wallet
Connect another wallet