owned this note
owned this note
Published
Linked with GitHub
# 2020q3 Homework3 (quiz3)
contributed by < `quantabase13` >
## 程式運作原理
### 測驗 1
```c=
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) >>1/*OP1*/) > 0;
unsigned int fixu = -(logical & ( m < 0/*OP2*/));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
這題的目標是要實作跨平台算術右移(arithmetic right shift, 簡稱asr)。由於在 C 語言中對有號型態的物件(且值為負) asr 屬於 `unspecified behavior` (程式行為仰賴編譯器實作和平台特性而定)，因此實作過程中必須要對可能出現的情況做出補償。
此題思路如下：
* 對有號型態的負數算術右移後， most significat bit (MSB) 可能為 0 或 1 。
* 根據原本的有號型態物件值是否大於0，決定是否該對算術右移後的結果做出補償。
列出表格來討論：
|logical|Is signed object < 0 ?｜|MSB(the output of our implementation)|
|-|-|-|
|1|yes|1|
|0|yes|1|
|1|no|0|
|0|no|0|
發現不論 logical 值為何，只要 signed object < 0 的話，就必須讓 MSB 等於 1 。
把 logical 去掉後，程式碼如下：
```c=
int asr_i(signed int m, unsigned int n)
{
unsigned int fixu = -( m < 0/*OP2*/);
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
只要 m < 0 ，就把 (m >> n) 最左邊的 n 個 bits 設為1。
<!--
我們可以列出真值表進行分析：
|MSB(after asr in C)|Is signed object < 0 ?|MSB(the output of our implementation)|
|-|-|-|
|1|1|1|
|0|1|1|
|1|0|0|
|0|0|0| -->
### 測驗 2
```c=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) & 0x1 /*OPQ*/);
}
```
分為兩個方向討論：
* `(num & (num -1)) == 0`:
四的冪次可以寫成 $4^n$，
$$
\begin{aligned}
{4^n} &= 2^{2n}\\
&= {1\overbrace{000...000}^{共 2n 個 0}}
\end{aligned}
$$
$$
\begin{aligned}
{4^{n}-1}&=2^{2n}-1\\
&= {0\overbrace{111...111}^{共 2n 個 1}}
\end{aligned}
$$
故只要 num 為4的冪次，(num & (num -1))為0。
* `!(__builtin_ctz(num) & 0x1 /*OPQ*/)`:
$$
\begin{aligned}
{4^n} &= 2^{2n}\\
&= {1\overbrace{000...000}^{共 2n 個 0}}
\end{aligned}
$$
我們只要檢查`__builtin_ctz(num)` 是不是偶數即可，方法就是檢查其 less significant bit 是否為 1。
### 測驗 3
```c=
int numberOfSteps (int num)
{
return num ? __builtin_popcount(num)/*AAA*/ + 31 - __builtin_clz(num)/*BBB*/ : 0;
}
```
閱讀 `LeetCode` 上關於 `numberOfSteps` 的說明後，可以歸納出程式碼的運作流程：
```graphviz
digraph G {
node [fontname = "Handlee"];
edge [fontname = "Handlee"];
draw [
label = "numberOfSteps(num)";
shape = rect;
];
check [
label = "Is num odd?";
shape = diamond;
];
point [
label = "num = num >> 1;\nstep++\ngoto numberOfSetps(num)";
shape = rect;
];
point2 [
label = "num = num - 1;\nstep++\ngoto numberOfSetps(num)";
shape = rect;
];
draw:s -> check:n;
check -> point [ label = "No" ];
{
rank = same
check; point;
}
check -> point2 [label = "Yes"];
{
rank=same;
draw;
};
}
```
由此，我們其實可以發現：
* 2 進位表示的 num 中 1 的個數就是`num = num -1` 的執行次數。
* 32 - (leading zero bit 的數目) -1 就是 `num = num >> 1` 的執行次數。
### 測驗 4
```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 (v/*XXX*/);
return u << shift/*YYY*/;
}
```
這題的實作利用了 Binary GCD algorithm。參考了[維基百科](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)上的資料後，得知可以重複利用以下四條恆等式將問題化簡：
`1. gcd(0, v) = v`
`2. gcd(2u, 2v) = 2·gcd(u, v)`
`3. gcd(2u, v) = gcd(u, v)`
`4. gcd(u, v) = gcd(|u − v|, min(u, v))`
程式碼的第一部份：
```c=
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
對應到恆等式(1)，將兩數共有的 2 的冪次提出。
程式碼的第二部份中的：
```c=
while (!(u & 1))
u /= 2;
```
和
```c=
while (!(v & 1))
v /= 2;
```
對應到恆等式(3)。
另外
```c=
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
```
對應到恆等式(4)。
過程中，`v` 存的是 `| u - v |` 的值，也就是說透過 `v` 可以確定何時離開 `while` 迴圈。
另外， `u` 存的就是還沒 shift 的 gcd。
### 測驗 5
這題原始的實作如下：
```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;
}
```
`bitmap` array 裡存了 `bitmapsize` 個 類型為`uint64_t` 的 object，
```graphviz
digraph g {
graph[rankdir=LR, center=true, margin=0.2, nodesep=1, ranksep=1]
edge[arrowsize=1.0, arrowhead=vee]
node[shape = record, fontsize=14, width=1.5, height=0.5, fixedsize=false];
subgraph cluster_0 {
node1[label = "<f0> 0 |<f1> 1 |<f2>2|<f3>.\n.\n.\n|<f4>bitmapsize-1"];
label = "bitmap";
color=none;
}
subgraph cluster_1 {
node2[label = "<f0>unit64_t"];
label = "bitset";
color=none;
}
subgraph cluster_2 {
node3[label = "<f0>unit64_t"];
label = "bitset";
color=none;
}
node1:f1:e -> node2:w;
node1:f4:e -> node3:w;
}
```
`bitmap` 中的第 i 個 bitset ，其第 j 個 bit 對應到數字 $64 \cdot i + j$。往 `output[pos]` 存入數字時，如果此 bit 為 0，代表 $64 \cdot i + j$不會被存入入。存入 `output[pos]` 的將是下一個非0 bit 所對應的數。
以此作為基礎，可以試著分析使用 `clz` 改寫的程式碼：
```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 = bitset & -bitset/*KKK*/;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
改寫後的程式碼主要目的是為了去掉`判斷 bit 是否為 1` 的 for loop。
原先的程式碼必須1個 bit 1 個 bit 的檢查，直到有非 0 bit 才能將對應的數字存入 `out` ; 改良後的程式碼使用 `ctz` 一次取得非 0 bit 在 64 bits 表示中的相對位置，並將對應的數字存入 `out` 。
由於 `ctz` 是算從 least sigificant bit 向左遇到第一個 1 之前的 `0` 數量，因此若要得知下一個 1 在 64 bits 表示中的相對位置，必須利用額外的技巧才能達到目的，這就是
```c=
uint64_t t = bitset & -bitset
```
這段程式碼的作用。
分析bitset，可分為兩種 case :
1. |bitset(1~63)|bitset(0)|
|-|-|
|xxx...xxx|1|
2. |bitset(1~63)|bitset(0)|
|-|-|
|xxx...xxx|0|
* 若 bitset 屬於 case 1 ，則 -bitset 可以表示成如下：
|-bitset(1~63)|-bitset(0)|
|-|-|
|～bitset(1~63)|1|
這樣 `bitset & -bitset` 就可表示成：
|bitset & -bitset(1~63)|bitset & -bitset(0)|
|-|-|
|$\overbrace{000..000}^{63個 0}$|1|
如此 `bitset^=(bitset & -bitset)` 後就能利用 `ctz` 找出下一個 bit 1 的相對位置。
* 若 bitset 屬於 case 2 ， 則 -bitset 可以表示如下：
|-bitset(n+1~63)|-bitset(n)|-bitset(0~n-1)|
|-|-|-|
|～bitset(n+1~63)|1|$\overbrace{000...000}^{n個0}$|
由右數來第 n 個 bit 的位置就是原本的 bitset 第一個非 0 bit 所在位置。
`bitset^=(bitset & -bitset)` 一樣能利用 `ctz` 找出下一個 bit 1 的相對位置。
Google Drive
Gist
Clipboard
Sign in with Wallet
