---
# System prepended metadata

title: 2020q3 Homework3 (quiz3)
tags: [sysprog2020]

---

# 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 的執行結果：

![](https://i.imgur.com/csMzZeZ.png =600x)

### 練習 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 的執行結果：

![](https://i.imgur.com/9zUOmdF.png =600x)

### 練習 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 的執行結果：

![](https://i.imgur.com/l7btNVZ.png =600x)


## 測驗三
### 題目解析
```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`**