# 2020q3 Homework3 (quiz3)
contributed by < `ptzling310` >
> [2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3)
## 測驗 `1` ： 有號整數的跨平台 ASR 實作
依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):
>“The result of `E1 >> E2` is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is implementation-defined.”
```c=
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));
}
```
- [x] OP1： `>> 1`
- [x] OP2： `m < 0`
### 程式解析
```c=3
const int logical = (((int) -1) OP1) > 0;
```
首先這邊先判目前所在的平台是採算數右移或是邏輯右移，藉由 `-1` 來測試。 所以 `OP1= >>1`。
1. 算術右移： (-1) >> 1 = (1111)~2~ ， logical = 0
2. 邏輯右移： (-1) >> 1 = (0111)~2~ ， logical = 1
```c=4
unsigned int fixu = -(logical & (OP2));
```
接著判斷輸入的 `m` 是否需要進行 ASR 的修正， 如果 `m > 0` ，表示 `m` 是正數，不論平台做邏輯或算數右移，其結果都是對的。
若`m < 0`，表示 `m` 是負數，若 `logical == 1`，就要對該數右移的結果進行修正。所以`OP2 = ( m < 0 )`。
故 `logical & (m < 0)` 之結果就可能為 (0000 0000)~2~ 或者 (0000 0001)~2~，為了要讓最後產生 1 在 MSB 的位置， 所以在 `logical & (m < 0)` 前面加上 `-`。 最後 `fixu` 會有兩種可能，分別為 (0000 0000)~2~ = 0 或者 (1111 1111)~2~ = (-1)。
```c=5
int fix = *(int *) &fixu;
```
就結果來看， `fix` 與 `fixu` 所存的值應該是一樣的，那為何要不要直接寫 `int fix = = -(logical & (m < 0));` ？
參照 `jserv` 在 `RinHizakura` 中的[回覆](https://hackmd.io/@RinHizakura/SkjPS8vBP#測驗-1)：避免**編譯器進行過度 (aggressive) 最佳化**
:::warning
TODO：過度最佳化會帶來的影響
:::
```c=6
return (m >> n) | (fix ^ (fix >> n));
```
在 return 這階段來做右移修正， 當`m >> n` 後， m 的二進制的最左 n 個 bit 會為 0 ， 若 m 為負數時，這些最左 n 個 bits 應為 1 ，故藉由`(fix ^ (fix >> n))` 來產生所需要的 n 個 1 補在 `m >> n` 的最左 n 個 bits。
### 數學證明和 Graphviz 製作的圖解
:::warning
Question： 會有哪一類型的圖產生？
> 可參照 [Swift: Advanced Operators](https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html) 精美的圖示，用來說明算術位移，你可搭配數學證明解釋通用 (generic) 的狀況
> :notes: jserv
:::
#### logical 變化 - 考慮平台為**邏輯右移**
```graphviz
digraph structs {
node[shape=record]
int[label="(int) -1",shape=plaintext]
struct_1 [label="<f0> 1|<f1> 1|<f2> ... | <f3>1 | <f4> 1"];
{rank=same; int struct_1}
int2[label=">>1",shape=plaintext]
struct_12 [label="<f0> 0|<f1> 1|<f2> ... | <f3>1 | <f4> 1"];
{rank=same; struct_12 int2}
struct_1:<f0>->struct_12:<f1>
struct_1:<f1>->struct_12:<f2>
struct_1:<f3>->struct_12:<f4>
}
```
所以右移後的結果 `>0` ，故 `logical = 1`
```graphviz
digraph structs {
node[shape=record]
int[label="logical",shape=plaintext]
struct_1 [label="<f0> 0|<f1> 0|<f2> ... | <f3>0 | <f4> 1"];
}
```
#### fixu 變化： 假設 m = -5
因為 `logical = 1` 且 `m = -5 < 0` ，`logical & m < 0 ` 為 `1`。
故 `fixu =` (1...1)~2~。
```graphviz
digraph structs {
node[shape=record]
int[label="input1: logical = 1",shape=plaintext]
struct_1 [label="<f0> 0|<f1> 0|<f2> ... | <f3>0 | <f4> 1"];
{rank=source; int struct_1}
int2[label="input2: m < 0 = 1",shape=plaintext];
struct_2 [label="<f0> 0|<f1> 0|<f2> ... | <f3>0 | <f4> 1"];
{rank=max ; int2; struct_2}
result [label="<f0> 0|<f1> 0|<f2> ... | <f3>0 | <f4> 1"];
res[label="logical & (m<0)",shape=plaintext];
{rank=same ; result res}
struct_1:f4 -> result:f4
struct_2:f4 -> result:f4
}
```
最後 `fixu` 是上圖結果再取 `-`。
```graphviz
digraph structs {
node[shape=record]
int2[label="fixu",shape=plaintext];
struct_2 [label="<f0> 1|<f1> 1|<f2> ... | <f3>1 | <f4> 1"];
{rank=max ; int2; struct_2}
}
```
#### fix 變化：
其實就是 `fixu` 的值，但 `fix` 為 signed。
```graphviz
digraph structs {
node[shape=record]
int2[label="fix",shape=plaintext];
struct_2 [label="<f0> 1|<f1> 1|<f2> ... | <f3> 1| <f4> 1"];
{rank=max ; int2; struct_2}
}
```
#### 求最後的結果
假設 m = -5 ， n = 1
```graphviz
digraph structs {
label="m >> n"
node[shape=record]
int[label="(int) -5",shape=plaintext]
struct_1 [label="<f0> 1| <f1> ... |<f2> 1|<f3> 0| <f4> 1 | 1"];
{rank=same; int struct_1}
int2[label="-5 >> 1",shape=plaintext]
struct_12 [label="0|<f0> 1| <f1> ...|<f2>1|<f3> 0|<f4>1"];
{rank=same; struct_12 int2}
struct_1:f0->struct_12:f0
struct_1:f1->struct_12:f1
struct_1:f2->struct_12:f2
struct_1:f3->struct_12:f3
struct_1:f4->struct_12:f4
}
```
```graphviz
digraph structs {
label="fix >> n"
node[shape=record]
int[label="fix",shape=plaintext]
struct_1 [label="<f0> 1| <f1> ... |<f2> 1|<f3> 1| <f4> 1 | 1"];
{rank=same; int struct_1}
int2[label="fix >> 1",shape=plaintext]
struct_12 [label="0|<f0> 1| <f1> ...|<f2>1|<f3> 1|<f4>1"];
{rank=same; struct_12 int2}
struct_1:f0->struct_12:f0
struct_1:f1->struct_12:f1
struct_1:f2->struct_12:f2
struct_1:f3->struct_12:f3
struct_1:f4->struct_12:f4
}
```
```graphviz
digraph structs {
label="fix ^ (fix >> n)"
node[shape=record]
int[label="input1: fix",shape=plaintext]
struct_1 [label="<f0> 1|<f1> 1|<f2> ... | <f3>1 | <f4> 1"];
{rank=source; int struct_1}
int2[label="input2: fix>>1",shape=plaintext];
struct_2 [label="<f0> 0|<f1> 1|<f2> ... | <f3>1 | <f4> 1"];
{rank=max ; int2; struct_2}
result [label="<f0> 1|<f1> 0|<f2> ... | <f3>0 | <f4> 0"];
res[label="fix ^ (fix >> 1)",shape=plaintext];
{rank=same ; result res}
struct_1:f0 -> result:f0
struct_2:f0 -> result:f0
}
```
```graphviz
digraph structs {
label="(m>>n) | fix ^ (fix >> n)"
node[shape=record]
int[label="input1: -5 >> 1",shape=plaintext]
struct_1 [label="<f0>0| <f1>1| ...|<f2>1| 0|<f3>1"];
{rank=source; int struct_1}
int2[label="input2: fix ^ (fix >> 1)",shape=plaintext];
struct_2 [label=" <f0>1| 0|... | 0 | 0|0"];
{rank=max ; int2; struct_2}
result [label=" <f0>1| <f1>1| ... | <f2>1 | 0|<f3>1"];
res[label="(-5>>1) | fix ^ (fix >> 1)",shape=plaintext];
{rank=same ; result res}
struct_2:f0 -> result:f0
struct_1:f1 -> result:f1
struct_1:f2 -> result:f2
struct_1:f3 -> result:f3
}
```
### 練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以==強化程式碼的共用程度==
::: warning
Question：其他寬度的意思？
> 指 int16, int32, int64, 等等。width 就是「資料寬度」，不要因為讀了一堆對岸文章，就忘了繁體中文怎麼書寫
> :notes: jserv
:::
- 巨集 Macro [巨集簡介](https://openhome.cc/Gossip/CGossip/Macro.html)
- 常見的前置處理器指令
1. `#include`
2. `#define`
- `#define`： `#define 巨集名稱 算式`
- 被定義的內容就是巨集( macro )
- 常用來定義一個模板，取代常用的程式片段
- `#define` 若為多行，需在每一行最後加上`\`
- 會定義在 `#include` 以及 `main()` 中間
- `\`後不可有空格，否則會出現 `warning: backslash and newline separated by space`
- 改寫
:::spoiler 此版本程式雖然使用了 Macro ，卻沒程式碼共用！(因為我把不同 data width 都分開打)
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int16_t asr_16(int16_t m, unsigned int n)
{
const int16_t logical = (((int16_t) -1) >>1 ) > 0;
uint16_t fixu = -(logical & (m<0));
int16_t fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
int32_t asr_32(int32_t m, unsigned int n)
{
const int32_t logical = (((int32_t) -1) >>1 ) > 0;
int32_t fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
int64_t asr_64(int64_t m, unsigned int n)
{
const int64_t logical = (((int64_t) -1) >>1 ) > 0;
uint64_t fixu = -(logical & (m<0));
int16_t fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
#define asr_i(m,n) \
_Generic((m), \
int16_t: asr_16, \
int32_t: asr_32, \
int64_t: asr_64 \
)(m,n)
int main() {
int16_t a = 8;
int32_t b = 64;
int64_t c = 128;
printf("asr_i(8,1)= %d\n",asr_i(a,1));
printf("asr_i(64,2)= %d\n",asr_i(b,2));
printf("asr_i(128,3)= %ld\n",asr_i(c,3));
return 0;
}
```
:::
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define asr_i(m,n) \
_Generic((m), \
int16_t: asr_16, \
int32_t: asr_32, \
int64_t: asr_64 \
)(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))
int16_t asr_16(int16_t m, unsigned int n)
{
asr(int16_t);
}
int32_t asr_32(int32_t m, unsigned int n)
{
asr(int32_t);
}
int64_t asr_64(int64_t m, unsigned int n)
{
asr(int64_t);
}
int main() {
int16_t a = 8;
int32_t b = 64;
int64_t c = 128;
printf("asr_i(8,1)= %d\n",asr_i(a,1));
printf("asr_i(64,2)= %d\n",asr_i(b,2));
printf("asr_i(128,3)= %ld\n",asr_i(c,3));
return 0;
}
```
結果
```
asr_i(8,1)= 4
asr_i(64,2)= 16
asr_i(128,3)= 16
```
---------
## 測驗 `2` ：LeetCode [342. Power of Four](https://leetcode.com/problems/power-of-four/description/)
```c
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
- [x] OPQ： `& 0x1`
分別來看 3 個判斷條件：
1. `num > 0`：因為 $4^n$ > 0
2. `(num & (num - 1))==0`：因為 $4^n = (2^2)^n = 2^{2n}$，所以若 `num` 是 4 的冪，則必為 2 的冪，其二進位必定長得像 (1xx...x)~2~，`(num - 1)` 長得會像 (011...1)~2~， 兩者在做`&`則必為 0。
4. `!(__builtin_ctz(num) OPQ)`：`__builtin_ctz(num)` 是回傳 `num` 的二進制的尾巴有幾個 `0`。
觀察下面幾個$4^n$：
| $4^n$ | 二進制 |
| -------- | -------- |
| $4^1$ | (100)~2~ |
| $4^2$ | (10000)~2~ |
| $4^3$ | (1000000)~2~ |
| $4^4$ | (100000000)~2~ |
觀察到尾數 `0` 的個數的變化是 2 → 4 → 6 → 8 … ，也就是說 0 的尾數應該要是**偶數個**。
故 `(__builtin_ctz(num) OPQ)` 判斷 `__builtin_ctz(num)` 的 0 的個數為**奇數個**。而奇數的特徵就是，其 b~0~(LSB) 為 `1`，利用 `&`(`0..01`)~2~ 來讀取 b~0~看是否為 1 。 得OPQ = `& 0x1`。
### 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
- 觀察 $4^n$
1. 只有一個 bit 1，可利用`__builtin_popcount`來確認。而且也可以排除`0`的情況，就可以不用做`num > 0`。
2. 且 bit 1 會位在 b~偶數~ 的位置(這樣後面一定跟著偶數個 0 )，所以會在 b~2~、b~4~、b~6~......等位子。利用 `0x55555555` = (`0101 0101 ... 0101`)~2~ 與 `num` 做 `AND` 來確認 bit 1 是否位在 b~偶數~。
```c
bool isPowerOfFour(int num){
return __builtin_popcount(num) == 1 && (num & 0x55555555);
}
```
### LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
- 求補數，即是把 input 二進制中的0↔1。
- 把某一個數與(`1...1`)~2~ 做`XOR`即可得 0 、 1 互換。
> input = 5 = (0101)~2~
> input ^ (1111)~2~ = (1010)~2~ = -6
> expect output = 2 = (010)~2~
所以應該是要找到最左的 bit 1 後才做`XOR`！
- 所以我們先找出由左至右有幾個 0 (利用`__builtin_clz`)，再針對這些 0 以後的 bits 做`XOR`。
```c
int bitwiseComplement(int N){
if (N==0) return 1;
unsigned int mask = 0xffffffff ;
mask = mask >> __builtin_clz(N);
return mask ^ N;
}
```
### LeetCode [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
- 若第 `i` 個元素不等於 `i+1`， `i+1` 就是要找的。
- 若第 `i` 個元素皆等於 `i+1`，則回傳 `numsSize+1`。
```c
int firstMissingPositive(int* nums, int numsSize){
if(nums==NULL || numsSize==0)
return 1;
//欲查看 nums 中的每個數字
for(int i = 0; i<numsSize; i++){
//值為正數，且未超過範圍(1~numsSize)
if(nums[i] > 0 && nums[i]<numsSize ){
//當 nums[i] != nums[nums[i] - 1
if(nums[i] != nums[nums[i] - 1]){
//交換nums[i]跟nums[nums[i]-1]
int j = nums[i]-1;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i--;
}
}
}
//值不對
for(int i = 0 ; i<numsSize; i++)
{
if(nums[i] != i+1)
return i+1;
}
//皆正確
return numsSize+1;
}
```
### 研讀 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz)，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告
:::warning
TODO
:::
-------------
## 測驗 `3`： LeetCode 1342. Number of Steps to Reduce a Number to Zero
計算出將 number 藉由 `/2` 以及 `-1` 計算至 0 的步驟數。
假設 `int` 寬度為 32 位元
```c
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
- [x] AAA = `__builtin_popcount(num)`
- [x] BBB = `__builtin_clz(num)`
假設 `num` 為 32 bits ，假設每個 bit 都會做右移(`/2`)，則至少做 32-1 次 (因為最後一個留下的 bit 並不用在右移，頂多只要 -1)，但如果在 `num` 中 b~n~ = 1 時，必須多花一個步驟做 `-1` ，所以 AAA 應為 `__builtin_popcount(num)`。
如： (00010010)~2~)，最左只會做到最左邊的那個 1 就會停止，則不用再做右移，我們就將不用右移的次數扣除，所以 BBB 為 `__builtin_clz(num)`。
---------
## 測驗 `4` ： 64-bit GCD (greatest common divisor, 最大公因數)
```c=
#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;
}
```
- [x] XXX = `v`
- [x] YYY = `u << shift`
```c=5
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
`for` 的終止條件是 `!((u | v) & 1` ，表 `u` 或 `v` 之 b~0~ 不為 1，才進入`for`迴圈，簡單來說就是否兩者皆為偶數。這邊是進行 $gcd(u,v) = 2 \times gcd(\dfrac{u} {2},\dfrac{v}{2}) = 2 \times gcd(u',v')$ 。利用 `shift` 來記錄有幾個 2 要乘在 $gcd$ 前 (可利用左移來完成！)。所以接下還的 $gcd(u',v')$ 頂多$u'$ **或** $v'$ 是偶數。
```c=8
while (!(u & 1))
u /= 2;
```
如果 $u'$ 是偶數，則一樣`/2`，進行$gcd(u',v')=gcd(\dfrac{u'}{2},v')$。
```c=10
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;
```
Line 11 如果 $v'$ 是偶數，則`/2`，進行$gcd(u',v')=gcd(u',\dfrac{v'}{2})$。
所以 line 11 後，$gcd$ 內的數**都是奇數**了！
再來又分兩種情況，一個是 `u < v` ，此時我們就不斷將 `v - u`；另一個是 `u > v`，我們利用變數 `t` 的幫助，轉換為 `u < v` 的 case 去做。而 `whiel` 的結束點就是 `v`，所以 XXX = `v` 。而 `u` 會記錄在一連串輾轉相處法的過程中所得出的最大公因數。
但在 line 5 ~ 7 中，我們有利用 `shift` 來記錄我們要補回幾次 2 ，這樣才會是正確結果。故 YYY = `u << shift`。
-----------
## 測驗 `5` ： 找 bit array (aka bit map, bit set, bit string, or bit vector) 中 b~n~=1 的位址
### 版本一
```c
#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;
}
```
參數：
- `uint64_t` *bitmap ： bitmap point to a bit array.
- `size_t bitmapsize` ： 有 bitmapsize 個 bitmap ，每一個 bitmap 有 64 bits 。
- `uint32_t *out` ： 要將結果儲存在 out 中
程式：
```
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
```
從這段可以看出來，我們每次都是去比較 1 個 bit (每次把 bitset 往右移動，在取 b~0~ 看是否為 1 )，當遇到 1 時，我們就把這個位子記錄到 out 中。
不過這樣的處方法，可以再改進，最右的 bit 0 個數如果很多，就乾脆都不要看，最快的方法是我們直接找到最右邊的 bit 1 ，且紀錄位子。 此作法及可透過 `__builtin_ctzll` 來達成。
### 版本二：透過 ctz 改寫
```c=
#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;
}
```
- [x] KKK = `bitset & -bitset`
- 程式理解
```c=4
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
```
藉由 `k` 來記錄我們應該確認的 bitmap (共 bitmapsize 個)。
`bitset` 就是一次取一個 bitmap 來看。
```c=10
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
```
`__builtin_ctzll` ： Returns the number of ==trailing 0-bits== in x, starting at the ==least significant bit== position. If x is 0, the result is undefined.
所以透過 `builti_ctzll` 我可以推算出**最右的 bit 1** 在哪個位子。
```
x = (1101 1000)
builti_ctz(x) = 3
則最右的 bit 1 會位於第 3+1=4 個位子
```
```c=12
bitset ^= t;
```
為了找到第二個 bit 1 ，那會希望可以將第一個 bit 1 先忽略掉，所以這裡會希望能夠將**目前最右的 bit 1** 設置為 `0`，而其他不變。 故 t 希望為 `(0...0 1 0..0`)~2~ 而 1 的位子正好是與目前最右 bit 1 的位子相同。
```c=9
uint64_t t = KKK;
```
所以 KKK = `bitset & -bitset` ， 因為 `-bitset` 的結果是由右至左，遇到第一個 bit 1 保留，其餘的 0 ↔ 1 。
```
bitset 1101 1000
&-bitset 0010 1000
--------------------
0000 1000
```
-----------
##### 時間表
- [x] 2020/09/28 測驗 `1`、`2`、`3` 程式理解。
- [x] 2020/09/29 測驗 `4` 程式理解、[浮點數運算](https://hackmd.io/@sysprog/c-floating-point#Uneven-density-of-the-floating-point-numbers)
- [x] 2020/09/30 測驗 `5` 程式理解、測驗 `1` 延伸問題_2
- [x] 2020/10/01 測驗 `1` 延伸問題_3、[C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)
- [x] 2020/10/02 測驗 `2` 延伸問題_1、2
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet