# 2020q3 Homework3 (quiz3)
contributed by < `tsengsam` >
[第三週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
---
## 測驗 `1`: Arithmetic Right Shift
#### 因為負數的算數右移屬 `unspecified behavior`，表示負數在不同平台做算數右移後的最高位元不一定相同
```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));
}
```
1. 首先從第 6 行判斷，負數右移最高位元若補 `1` 時 `(fix ^ (fix >> n))` 為 0，即無調整；反之若補 `0` 時 `(fix ^ (fix >> n))` 的最高位元為 1 其他位元 0。。
2. 再來選擇一種補法來回推：若補 1, fix 為 `0`。
3. 表示第 6 行的 fixu 亦為 `0` 。
4. 第 4 行的 `-(logical & (OP2))` 亦為 `0`， 不過 `logical` 與 `OP2` 的排列組合多達三種可能，故回到上述第 2 步驟改成補 0, fix 變為 (-1)~10~。
5. 表示第 6 行的 fixu 為所有位元皆 1，也就是最大值。
6. `-(logical & (OP2))` 即可知道小括號內為最大值的二補數，即 `1`。
7. `(logical & (OP2))` 為 1 表示 & 兩邊皆為 1。
8. `OP2` 可知只有 `(c) m < 0` 一定為 1 ，其他如 (f) 當位移為 0 時會錯。
9. `logical` 為 1 時表示`((int) -1) OP1` 應為正數，故只有 `(b) >> 1` 符合。
---
## 測驗 `2`: Power Of Four
#### 計算給定的有號整數是否為 4 的次方
```cpp
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
* 解本題之前我先以慢但直覺的方式實作，思路是用迴圈計算當前數值是否為 4 的倍數，若是便將其除以 4 直到數值小於等於 1。
```cpp
bool isPowerOfFour_loop(int num)
{
if (num <= 0) return false;
for (int r = 0; num > 1; num /= 4) {
if (num % 4) return false;
}
return true;
}
```
* 從迴圈版本可以了解邊界條件為 `num > 0`，且四的次方之數值僅一個位元為 1，如此可理解本題的前兩項判斷式的用意。
* 最後一個判斷式 `!(__builtin_ctz(num) OPQ)` 用作計算 `num` 從 LSB 算起有幾個連續的 `0`並進行 `OPQ` 運算，若希望回傳 `true` 則 `(__builtin_ctz(num) OPQ)` 應為 `false`
需發現 4 的次方之數字的 trailing zero 皆為偶數個，如此可知 `OPQ` 為 `& 0x1` 時可判斷 trailing zero 是否為偶數個。
---
## 測驗 `3`: Population Count
#### 用 gcc 內建函式__builtin_popcount 與 __builtin_clz 計算 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
* 首先在 LeetCode 用慢但直覺得方式作答，若當前數值為奇數時要減一；反之則除二:
```cpp
int numberOfSteps_loop(int num)
{
int cnt=0;
while (num) {
cnt++;
if (num % 2) {
num -= 1;
}
else {
num = num >> 1;
}
}
return cnt;
}
```
如此可用以理解 bitwise 作法:
換算成二進制的數值來看可知當 LSB 為 1 時會減一 (奇數)，若為 0 則除二 (偶數)，直至數值為零
1. 所有位元皆會被檢查一次，而檢查的方式是透過右移運算並檢查 LSB 為 1 或 0
2. 只要該位元是 1 表示當其位移至 LSB 時必定會做減一
3. 可透過事先計算 leading zero 個數來避免檢查所有位元
4. 故上述步驟加總起來便是 (`計算 set bit 個數` + `最多位移次數` - `leading zero 數量`)
= `__builtin_popcount(num)` + `31` - `__builtin_clz(num)`
```cpp=
int numOfSteps(int num)
{
return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}
```
---
## 測驗 `4`: Greast Common divisor (GCD)
#### 求兩數之最大公因數
* 最直接的寫法是使用[輾轉相除法](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，將兩數相減所得的數會保留公因數，並將所得數與較小的數值重複相減動作直到較小數字變為 0。
```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;
}
```
* 本題則是先計算公因數是 2 的多少倍，算完後把仍有 2 因數的數字除以 2 直到變成奇數，最後再如同輾轉相除法相減直到有一數為 0。回傳時再將首先計算的 2 的倍數乘回即為答案。
```cpp=
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
/* for-loop will calculate 2's common divisor
* After this, at least one value is odd
*/
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
/*Let u be odd*/
while (!(u & 1))
u /= 2;
do {
/*Let v be odd*/
while (!(v & 1))
v /= 2;
/*Reduce value but common divisor will stay*/
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
/*Multiply back common divisor related to 2*/
return u << shift;
}
```
---
## 測驗 `5`: Bit Array
#### 從給定的 bitmap array 中找所有 set bit 並把其所在 index 放到 out array
* naive 寫法是**逐一**確認 bitmap 每個元素中的每個位元是否為 set bit
```cpp=
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
/* bitmap is a array of uint64_t*/
size_t pos = 0;
/* 0 <= k < bitmapsize
* k means the kth word of bitmap
*/
for (size_t k = 0; k < bitmapsize; ++k) {
/* In each loop, assign bitmap[k] to bitset */
uint64_t bitset = bitmap[k];
/* the index of first bit in each word*/
size_t p = k * 64;
/*To check whether each bit is set bit or not*/
for (int i = 0; i < 64; i++) {
/* If the ith bit is set
* then pos ++, recording number of set bits
* out[pos] stores the position of set bit in the whole array
*/
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
1. Bitmap 中的元素存放 64 bits 長度的無號整數
2. Line 6: `pos` 是 set bit 數量
3. Line 10: `k` 是 `bitmap` 的 index，也代表者存放第 `k` 個 words 的索引
4. Line 12: 將 `bitmap` 第 `k` 個元素指派給 `bitset`，以便做接下來找 set bit 的運算
5. Line 14: `p` 用來記錄 `bitmap` 第 `k` 個元素在整個 array 中屬於第幾個 bit
6. Line 16: 對第 `k` 個元素中的 64 個 bits 逐一確認是否為 set bit
7. Line 21: 透過 `>>` 運算把欲檢查的 bit 移到 LSB，與 `0x1` 做 `AND` 運算可確認是否為 set bit
8. Line 22: 將 set bit 在整個 array 中的位置指派給 `out`
9. Line 25: 最後將 set bit 的數量回傳
* 改良版透過 `__builtin_ctzll` 函式求出從 LSB 數起有幾個連續 0 bit 並可得出最低 set bit 的位置指派給 `out`
```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; /*KKK*/
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
1. Line 8: 有別於 naive 寫法的第二層 for 迴圈，因為透過第 12 行運算可避免逐一 bit 檢查
2. Line 10: 計算最低位元的 set bit 之前有幾個 0 bit
3. Line 12: `bitset ^= t` 的 `t` 可得僅最低位元的 set bit 為 1，其餘皆 0 的數值，再與原本 `bitset` 做 `XOR` 會使得最低位元 set bit 變成 0 bit，其餘位元不變。
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet