# 2020q3 Homework3 (quiz3)
contributed by < `iamchiawei` >
> [2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
###### tags: `sysprog2020`
## 測驗一
### 題目解析
```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));
}
```
程式碼中，為實作跨平台 ASR，首先須分辨當前環境的 ASR 為邏輯 / 算數右移，而有效處理方式即在當前環境測試並利用其判斷結果計算。因此此處利用一個全部位元皆為 1 的有號負數 -1，向右位移一個 bit，
1. 若預設為算數位移，sign bit 應為 1，因此結果應仍 < 0
2. 若預設為邏輯位移，sign bit 應為 0，因此結果應 > 0
```cpp
const int logical = (((int) -1) OP1) > 0;
```
因此 **OP1 應選擇 `(b)` `>> 1`**，向右位移一個 bit。
```cpp
unsigned int fixu = -(logical & (OP2));
```
在此行中，由於 `logical` 值應為 0 或 1，取決於系統預設為算數或邏輯位移，因此 `-(logical & (OP2))` 則應會是 0 或 -1 (0xffffffff)。再看到回傳值對 `(fix ^ (fix >> n))` 做 OR 運算，可推測應是欲利用此數，當系統預設為邏輯位移時可以將負數位移所需的每個 1 補回去。
若 `logical` 為 0，表示預設為算數位移，則 `m >> n` 即已正確，且此時 `fix` 為 0，不影響結果。
若 `logical` 為 1，表示預設為邏輯位移，此時當 `m` 為正，`fixu` 須為 0x00000000，反之則為 0xffffffff。因此 **OP2 應選擇 `(c)` `m < 0`**，使 `fixu` 在 `m` 為負數時為 0xffffffff。
### 實作其他資料寬度的 ASR
實作程式碼：
```cpp
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#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 ^ (fix >> n));
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); }
```
參照 [你所不知道的 C 語言：前置處理器應用篇](/@sysprog/c-preprocessor) 中 `_Generic` 用法撰寫 `asr_i` 函式的通用巨集，並分別使用依照各資料寬度的版本。為精簡程式碼，再定義一 `asr` 替代共用程式碼，並利用 `type` 即 `##` 做字串連接及轉換。
## 測驗二
### 題目解析
[ 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) OPQ);
}
```
* `num > 0` ：檢查 `num` 是否大於 0，若否則不可能為 $4^n$
* `(num & (num - 1)) == 0` ： 檢查 `num` 是否為 $2^n$，若否則不可能為 $4^n$
因此 `!(__builtin_ctz(num) OPQ)`，必為檢查 `num` 是否為 $4^n$，首先先觀察 $4^n$ 的二進位編碼：
| Decimal | Binary |
|---------------|--------------|
|$4^0$ |0b1 |
|$4^1$ |0b100 |
|$4^2$ |0b10000 |
|$4^3$ |0b1000000 |
由上表可看出 `__builtin_ctz(num)` 若為 2 的倍數，則 `num` 即是 $4^n$。
因此 **OPQ 應選擇 `(f)` `& 0x1`**，
若是尾部 0 的數量為 2 的倍數，則 `!(__builtin_ctz(num) & 0x1)` 為 1，否則為 0。
### 改寫程式碼
重新釐清判斷所需條件，可簡化為以下兩項：
* 僅有一個 1-bit
* 右側 0-bits 為偶數個
因此可換成以下等價寫法：
```cpp
bool isPowerOfFour(int num){
return !(__builtin_popcount(num) ^ 0x1) && (__builtin_ffs(num) & 0x1);
}
```
* `!(__builtin_popcount(num) ^ 0x1)` 為確認僅有 1 個 1-bit。
* `__builtin_ffs(num) & 0x1` 為確認右側 0-bit 共偶數個，
此式即等價於題目中提供的 `!(__builtin_ctz(num) & 0x1)`。
附上在 leetcode 的執行結果：
### 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
```cpp
int bitwiseComplement(int N){
return N ? ~N ^ (0xFFFFFFFF << (32 - __builtin_clz(N))) : 1;
}
```
* 首先須確認當前數字的長度，因此先計算出左側 0-bits 的數量 `(32 - __builtin_clz(N))`
* 製作 bitmask `(0xFFFFFFFF << (32 - __builtin_clz(N)))`，
對其做 XOR 運算則將可保持數字長度以外的位元皆為 0，而長度內則保持其原值。
* 接著將 N 反轉並對 XOR bitmask，即可得正解。
附上在 leetcode 的執行結果：
### 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/first-missing-positive/)
```cpp
#define XOR_SWAP(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
int firstMissingPositive(int* nums, int numsSize){
for (int i = 0; i < numsSize; ++i) {
if (nums[i] > 0 && nums[i] <= numsSize) {
int pos = nums[i] - 1;
if (nums[i] != nums[pos] && i != pos) {
XOR_SWAP(nums[pos], nums[i]);
i--;
}
}
}
for (int i = 1; i <= numsSize; ++i) {
if (nums[i - 1] != i) return i;
}
return numsSize + 1;
}
```
附上在 leetcode 的執行結果：
## 測驗三
### 題目解析
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
* `__builtin_popcount(num)` 為 `num` 中 1-bits 的數量。
* `__builtin_clz(num)` 為 `num` 由左至最左 1-bit 的 0-bit 數量。
* 由演算法中可看出將有兩種情況：
1. `num` 為偶數 (last bit is 0)：`num >>= 1`
2. `num` 為奇數（last bit is 1)：`num -= 1`
* 而若遇情況 2 後，必須接續一次情況 1，且情況二正好為偵測到一次 1-bit，此組合發生次數會是 1-bit 的數量，因此可知道至少須 (`__builtin_popcount(num)` * 2) steps。
* 而獨立情況 1 發生次數會是 0-bit 的數量，因此需要 (31 - `__builtin_popcount(num)`) steps，由於是非負有號整數，最左 bit 必為 0 而不採計。
* 最後若左側已有數個 0-bit，則當 1-bit 已消耗完則可提早結束，即少了 `__builtin_clz(num)` steps。
* 因此將以上條件加總，可得最終所需步數為：
`__builtin_popcount(num)` + 31 - `__builtin_clz(num)`
* **AAA 應選擇 `(a)` `__builtin_popcount(num)`**
* **BBB 應選擇 `(b)` `__builtin_clz(num)`**
## 測驗四
### 題目解析
原程式碼：
```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;
}
```
* 考慮若兩數若具公因數 $2^n$，直接移除尾部相同數量的 0-bits 將快過原程式碼中兩數交互餘除的方式，因此首先逐一確認兩數尾部是否皆為零，並將其數量儲存為 `shift` 變數。
```cpp
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
* 若 `u` 仍為 2 的倍數，可先除去因數 2 減少運算量，$gcd(u', v') = gcd(u' / 2, v')$。
* 若 `v` 仍為 2 的倍數，可先除去因數 2 減少運算量，$gcd(u', v') = gcd(u', v' / 2)$。
* 接著即是輾轉相除法，且迴圈中判斷式可確保每次運算完 `v` 皆是較小數。
* 根據輾轉相除法，當一數為零時，另一非零數即為最大公因數，由上一敘述可知 `v` 微較小數，因此此迴圈判斷式 **XXX 應是 `(b)` `v`**。
* 最後可得去除公因數 $2^n$ 後的 $gcd(u', v')$，即 `u` 值，因此再將其乘以先前所得 $2^n$ 即為正解，**YYY 應選擇 `e` `u << shift`**。
### 透過 __builtin_ctz 改寫 GCD
實作程式碼：
```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;
}
```
* 使用 __builtin_ctz 取代並加速 0-bits 數量計算，並且 bits 的右移僅需執行一次。
## 測驗五
### 題目解析
原程式碼：
```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 = KKK;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
* 由 `naive` 可看出功能為逐一比對 `bitmap` 中各元素的每一個 bit，將 bit 為 1 的位置紀錄至 `out` 中，並且 `pos` 最終即為 1-bits 的數量。
* 而 `improved` 中則是利用 `__builtin_ctzll` 直接得到尾部 0-bits 的個數，藉此省去逐一比對的時間。
* 依迴圈內容，`bitset` 更新只依賴 `bitset ^= t`，並應**將由右第一個 1-bit 改為 0**，`__builtin_ctzll(bitset)` 才可依序算出每一個 1-bit 的位置。
* 看到選項中的 `bitset & -bitset`，`-bitset` 等同於 `~bitset + 1`，即是原最右 1-bit 變為 0，及其右方所有 0-bits 全部替換為 1，此時再加 1 則會進位至原最右的 1-bit，而其左方其餘 bits 則皆與原數相反，接著做 AND 運算後則僅留下原數由右至左第一個 1-bit。
> ex.
> x = 0b01011000
> ~x = 0b10100111
> -x = ~x + 1 = 0b10101000
> x & -x = 0b00001000
* 因此 **KKK 應選擇 `(e)` `bitset & -bitset`**
Sign in with Wallet
Connect another wallet