# 2020q3 Homework3 (quiz3)
contributed by < `jonec76` >
###### tags: `sysprog-2020`
> [作業說明](https://hackmd.io/@sysprog/B1zAbkAEP)
> [題目](https://hackmd.io/@sysprog/2020-quiz3)
## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```
## 參考解答
OP1 = >> 1
OP2 = m < 0
OPQ = & 0x1
AAA = __builtin_popcount(num)
BBB = __builtin_clz(num)
XXX = v
YYY = u << shift
KKK = bitset & -bitset
## 作業
- 重新回答 [第 3 周測驗題](https://hackmd.io/@sysprog/2020-quiz3)，連同附帶的「延伸問題」。
- 將你的共筆加到 [2020q3 Homework3 (作業區)](https://hackmd.io/@sysprog/2020-homework3)
### Q1
```c=1
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));
}
```
- 解題想法
在 [undefined behavior](https://en.wikipedia.org/wiki/Undefined_behavior) 中提到
> In C/C++ bitwise shifting a value by a number of bits which is either a negative number or is greater than or equal to the total number of bits in this value results in undefined behavior.
可以知道對一個負數做 shift 時，是 undefined behavior。，因為第 3 行後面是個判斷式，程式碼中變數 `logical` 應只為 0 或者 1。此判斷式希望知道 `-1>>1` 後，編譯器會執行邏輯右移，還是算數右移。若右移後值 >0，表示最左邊的 sign bit 是補 0，藉此判斷出是邏輯右移。
OP2 的選項在課堂答題時想不出來，有了提示後才知道，此行是用在
1. 負數右移，但是最左邊卻補 0
2. m 為負數 (所以 OP2=m<0)
負數右移後卻變成正的，這樣並不合理。而這行在做的事情，就是幫忙在右移後補 0 的位置，改成 1，使得負數右移後仍是負數。
倒著來想的話
```c=1
| (fix ^ (fix >> n)
```
因為右移的特性在上述的 case 是補 0，再搭配 XOR 之後，此行應該要產生類似 0x11110000 的結果，其中 1 的位置跟 `m>>n` 做 or 後剛好能夠把 0 的位置改成 1。
第 5 行參考了 [RinHizakura 筆記](https://hackmd.io/@RinHizakura/SkjPS8vBP) 中老師的評語，是為了避免編譯器進行過度 (aggressive) 最佳化，但這部分還在研究。
### Q2
```c=1
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
- 解題想法
此題需要找出 num 是否是 4 的冪次方，首先先探討
```c=1
(num & (num - 1))==0
```
當此條件要成立，就表示 num 是 2 的冪次方（$num=2^n, where\ n=1,2,...$），因為若是 2 的冪次方，則會是只有一個 1 跟後續全部都是 0，例如 `0x100000`，該數減 1 後會變成原本 0 的地方變成 1，1 變成 0，剛好能滿足此式。
接著，觀察一下 $num=4^n, where\ n=1,2,...$，這樣的數字執行 `__builtin_ctz` 後，得到的都是偶數，`!__builtin_ctz(num) & 0x1` 即成立。
### Q3
```c=1
int numberOfSteps (int num)
{
return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}
```
- 解題想法
此題希望能夠將一個數字，用特定的步驟方法使之變為 0。步驟如下
1. divide it by 2
2. subtract 1 from it
一個數字只要知道它在二進制時候的最高位，就可以知道要除以多少次 2 後會變成 0，因為可以當作是右移直到為 0。那何時需要減 1 呢？就是當該數目前是奇數時，或者除以 2 後是奇數時。
那這題可以以二進制的方法來想，如果最低位是 1（表示是奇數），那要算一步減 1，如果是 0 且該數還不為 0，那就也要算一步（右移）。而這題的選項 `__builtin_popcount(num)`，為的是要找出該數有多少個 1 需要被減去，而 `31 - __builtin_clz(num)` 為的是要找出最高位是第幾位。如此一來將兩者相加，所得到的就是這題題目要的總步驟數了。
### Q4
```c=1
#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);
}
```
- 分析提示程式碼
```c=1
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
```
可以先看到主要做輾轉相除法的部分，在這段程式碼中以例子來看，u=10 v=8 ，那執行一輪之後希望得到 u=8 v=2，也就依據輾轉相除法的方式做。
- 解題方向
下面程式碼在做的事情，是檢查 u, v 是否都是偶數，若是則同時除 2，並且讓 shift +1。
```c=1
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
而下面的程式碼，如果執行了，表示 u 是偶數且 v 是奇數。可以知道偶數跟奇數並不會有 2 冪次方的公因數，所以下方就是要將 u 再做調整，將 2 的因數都拿掉
```c=1
while (!(u & 1))
u /= 2;
```
上方所做的為的都是希望使 u, v 的值越小越好，這樣做輾轉相除法的次數就會越少。進入輾轉相除法的回圈中能看到，因為 u 一定是奇數，但 v 有可能在減去 u 的過程變成偶數，所以對 v 做調整（原理同上）。
```c=1
while (!(v & 1))
v /= 2;
```
第一個選項 XXX 跟提示程式碼的中止條件是相同的，而回傳的 YYY=(u << shift)，是因為在一開始若兩數 u, v 都是偶數，會被提出公因數 2 直到沒辦法再提，此步驟就是將這公因數乘回去最後的答案。
### Q5
```c=1
#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;
}
```
- 分析提示程式碼
```c=1
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
```
在看到此段程式碼時，其實並不知道其背後的物理意義為何。但是單就閱讀程式碼時可以發現，在上面的這行是要找出 `bitset` 中，bit=1 的 index ，並且將這些 index 都加起來。
- 解題方向
老師在上課時提到，這段程式碼是用來降噪用的，此部分還沒深入理解。但是還是可以依據上面的分析，將這題的答案找出來。
倒著分析來看此題，知道這函式的目的是要找出 1 的 index 並且加起來後，又看到了 `__builtin_ctzll`。表示可以透過計算後面有多少個 0，得到不同 1 的 index。但是要如何讓最低位的 1 在算完這次的 `__builtin_ctzll` 後，變成 0 使得能計算出第二低的 1 的 index 呢？看到
```c=1
bitset ^= t;
```
既然要透過 XOR，那表示最低位的 1 要對應到 t 相對應位置也是 1，且 t 的其他位置應為 0。此時可以發現
```c=1
bitset & -bitset
```
可以透過二補數的特性，剛好在做完了 `&` 之後，只會剩下最低位 1 的位置是 1，其餘都是 0。
Sign in with Wallet
Connect another wallet