# 2020q3 Homework3 (quiz3)
contributed by < `RainbowEye0486` ＞
## 目錄
[TOC]
## 作業區
### 測驗一
在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR 或 asr) 歸屬於 unspecified behavior，包含 Cppcheck 在內的靜態分析器會嘗試找出 C 程式中這項 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:$−5≫^{arith1}=−3$
上述$−3$ 正是$\dfrac{−5}{2}$ 的輸出，並向$−∞$ 進位(rounding)。
針對有號整數的跨平台 ASR 實作如下:
```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));
}
```
解讀程式碼，我們的程式碼中可以知道目的是要==實做出不會造成unspecified behavior的算術右移==。為什麼說有號數的算術右移會是 **unspecified behavior** 呢？因為在算術右移的時候， Microsoft c++ 編譯器會使用正負號來填補空出的位位置，但並不保證其他的編譯器也會這麼做。所以會根據平台及編譯器產生不一樣的結果。
回到函式的開頭，我們先來看傳入參數：`signed int m` 、 `unsigned int n` ， m 代表的是我們想要位移的==有號數==，而 n 代表的是想要右移幾個 bit ，因此是 unsigned 的。
```cpp=3
const int logical = (((int) -1) OP1) > 0;
```
選項中，我們可以先刪除 `(c)` 到 `(g)` 的選項，因為這些操作不具有任何意義，基於 m 是原本想要位移的數字，-1這個操作判斷正負性其實沒有什麼意義，而 n-1 或是 -n-1 得到的除了在 n=0時會有不一樣的值，其他的並沒有特殊意義。所以選項剩下 `(a) << 1` 和 `(b) >> 1 ` ，今天我們想要探討的是對於不同的編譯器來說，算術右移會是補0還是1，所以對於-1來說(0xffffffff)，右移任何一個大於1的 bit ，如果是正負號都補0的編譯器，會變成一個正的有號數;如果是正數補0負數補1的編譯器，則右移後得到的數字仍為負數(因為仍然是0xffffffff，也就是-1)。
而 `logical` 在===第一種編譯器===的情形會是1，===第二種編譯器===是0，當作一個辨識用的數字。
OP1 = ?
`(a)` << 1
**`(b)` >> 1**
`(c)` * m + n
`(d)` + m
`(e)` + n
`(f)` - m
`(g)` - n
```cpp=4
unsigned int fixu = -(logical & (OP2));
```
我們先看下面幾行的意思是什麼， `fixu` 的意思很可能是用來修正會正負數右移都補0的編譯器，將其轉變成補1，而 `fix` 只是將 `fixu` 的變數型態從無號數變成有號數。得到的數字推測只會有兩種: `0x00000000` 、 `0xffffffff` ，因為後面 `(fix ^ (fix >> n))` 的操作會將後半部的 bit 變成是 0。我們稍後會證明
看看最後的回傳值:
```cpp=6
return (m >> n) | (fix ^ (fix >> n));
```
左邊的 `(m >> n)` 明顯是"對 m 右移 n bit "這個操作，右邊的我們暫時不理他，先看對於==編譯器1(算術右移都是補0)==，或是 ==編譯器2(正數補0負數補1)== 來說正負數對於 `fix` 的影響。
==**編譯器1**==
**正數:**
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>0|<f1>0|<f2>0|<f3>0|<f4>1|<f5>1|<f6>1|<f7>..."]
struct2 [label="<f0>0|<f1>0|<f2>0|<f3>0|<f4>0|<f5>0|<f6>1|<f7>..."]
struct1:f4->struct2:f4[label="右移2bit"]
}
```
回傳值中 `return (m >> n) | (fix ^ (fix >> n));` 中 `(m >> n)` 得到的答案已是正確答案， `(fix ^ (fix >> n)` 如果不是0可能會造成得到的答案有錯，故回推 `fix` 亦會是 `0x00000000`
**負數**
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>1|<f1>1|<f2>1|<f3>1|<f4>0|<f5>0|<f6>1|<f7>..."]
struct2 [label="<f0>1|<f1>1|<f2>1|<f3>1|<f4>1|<f5>1|<f6>0|<f7>..."]
struct1:f4->struct2:f4[label="右移2bit"]
}
```
這種情況也不需要被修正，由於 `(fix >> n)` 按照這種編譯器的做法，右移是能夠正確去補1的，所以 `(fix >> n)` 還是得到全部是1的結果，造成 `(fix ^ (fix >> n)` 依舊是0
==**編譯器2**==
**正數:**
得到的答案跟編譯器1一模一樣，`fix` 仍會是0
**負數:**
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>1|<f1>1|<f2>1|<f3>1|<f4>0|<f5>0|<f6>1|<f7>..."]
struct2 [label="<f0>0|<f1>0|<f2>1|<f3>1|<f4>1|<f5>1|<f6>0|<f7>..."]
struct1:f4->struct2:f4[label="右移2bit"]
}
```
只有這種情況是必須要被修正的。在這種情況，我們假定 `fix` 是 `0xffffffff`
原先的 `fix`
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>1|<f1>1|<f2>1|<f3>1|<f4>1|<f5>1|<f6>1|<f7>..."]
}
```
`(fix >> n)`假設 n=2 :
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>0|<f1>0|<f2>1|<f3>1|<f4>1|<f5>1|<f6>1|<f7>..."]
}
```
得到 `(fix ^ (fix >> n)`
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>1|<f1>1|<f2>0|<f3>0|<f4>0|<f5>0|<f6>0|<f7>..."]
}
```
這樣將 `(fix ^ (fix >> n)` 和 `(m >> n)` OR 起來就可以補齊前面右移編譯器自動補零的部分，將其再次設定為1。
所以回到當初判斷 `fixu` 的判斷條件，我們知道滿足兩種情況才需要將 `fix` 設定為 `0xffffffff` ，第一個就是**它是編譯器2** ，第二個就是 **m 是負數**，答案選`(c)` m < 0
OP2 = ?
`(a)` m
`(b)` n
**`(c)` m < 0**
`(d)` m == 0
`(e)` m > 0
`(f)` n < 0
`(g)` n == 0
`(h)` n > 0
### 測驗二
```cpp=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
判斷次方前，我們必須確定定義域範圍是正整數
```cpp
num > 0
```
接著我們要確保這個數是2的冪次，對於2的冪次來說，滿足條件:
1. 只會有1個1在32 bit 中
2. &自己減一會是零
```graphviz
digraph SR{
node[shape=record]
struct1 [label="<f0>0|<f1>0|<f2>1|<f3>0|<f4>0|<f5>0|<f6>0|<f7>..."]
struct2 [label="<f0>0|<f1>0|<f2>0|<f3>1|<f4>1|<f5>1|<f6>1|<f7>..."]
struct1:f4->struct2:f4[label="-1"]
}
```
```cpp
(num & (num - 1))==0
```
最後一個條件，我們猜測我們要排除掉只是2的冪次，但是不是4的冪次。
>Built-in Function: int __builtin_ctz (unsigned int x)
>- Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
根據函式說明，我們知道回傳的會是從 LSB 數來碰見第一個1的 bit 數，觀察4的冪次:
| num | Binary |
| -------- | -------- |
| $4$ | 00000100 |
| $4^2$ | 00010000 |
| $4^3$ | 01000000 |
`__builtin_ctz(num)` 回傳的值分別會是2、4、6、8...。特徵是，他們都是偶數，所以只要將偶數和1做 AND 運算，就必定會得到0，加上!運算後得到1，反之如果只是2的冪次，但是不是4的冪次的數， `__builtin_ctz(num)` 回傳的數字會是奇數而 `!(__builtin_ctz(num) & 0x1)` 得到的會是0。
```cpp
!(__builtin_ctz(num) OPQ)
```
OPQ = ?
`(a)` > 0
`(b)` > 31
`(c)` >> 0x2
`(d)` >> 0x1
`(e)` | 0x1
**`(f)` & 0x1**
`(g)` ^ 0x1
### 測驗三
population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 CRC32 和 POPCNT 指令，POPCNT 可處理 16-bit, 32-bit, 64-bit 整數。
GCC 提供對應的內建函式:
>__builtin_popcount(x): 計算 `x` 的二進位表示中，總共有幾個 `1`
```cpp=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
>Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
除2這個動作相當於右移一個 bit ，但是碰到 LSB 是1的情況，必須先減一才能繼續除2所以遇到1我們的 `step` 還會需要再多加1，所以多加的運算次數即為這串數字內所有1的總數，也就是 **` __builtin_popcount(num)`** 。
考慮 `num` ，假設
```graphviz
digraph SR{
node[shape=record]
a [label="0x"]
struct1 [label="0|0|c|5|0|4|0|0"]
}
```
我們注意到，當所有的1已經右移出去後， `num` 已經是0，也就是開頭的8 bits 其實根本沒有位移到，所以計算總位移的 bit 數要用32-1扣掉從 MSB 數過來的第一個 1 ，才是我們真正位移的次數。所以用 **` __builtin_clz(num)`**
AAA = ?
**`(a)` __builtin_popcount(num)**
`(b)`__builtin_clz(num)
BBB = ?
`(a)` __builtin_popcount(num)
**`(b)` __builtin_clz(num)**
### 測驗四
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
```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=3
if (!u || !v) return u | v;
```
這行的意思是其中一個如果是0就回傳另一個，如果兩個都是0就回傳0
```cpp=4
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
```
>根據輾轉相除法，兩個整數的最大公因數等於其中較小的數和兩數相除餘數的最大公因數。例如，252和105的最大公因數是21$（{\displaystyle 252=21\times 12;105=21\times 5}{\displaystyle 252=21\times 12;105=21\times 5}）$因為 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公因數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公因數。
所以 `v` 會是兩者中較小的那個，我們持續取餘數直到其中一個等於0。
改寫為以下等價實作:
```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;
}
```
前面一樣，直到
```cpp=5
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
判斷是否 `v` 和 `u` 都是偶數，如果是，紀錄要右移的位數並且同時除以2，因為右移運算比較快，而當兩個數字較大時，為了使運算效能降低，我們可以利用一點右移運算使要處理的數字小一點，提出2公因數後再進行輾轉相除法，可以大幅度降低 `％` 的運算次數。運算後，我們可能得到
1. `v` 是偶數、 `u` 是奇數
2. `v` 是奇數、 `u` 是偶數
3. `v` 是奇數、 `u` 是奇數
三種可能性，由於2已經不會是 `v` 和 `u` 的共同因數了(因為前面都已經提取出來了)，所以我們可以先把 `u` 的2因數全部提出，因為這裡的2因數已經不會是我們需要紀錄的"**公因數**"，所以先提出讓數字變小，提出後 `u` 變成奇數
```cpp=8
while (!(u & 1))
u /= 2;
```
先看迴圈內部，是我們熟悉的輾轉相除法，相減之後，對數字的大小進行調換，確保 `v` 會是比較小的那個，從原本的方法改寫而來，迴圈的進入條件是判斷是否較小的數字是不是還大於零，所以 `XXX` 是 `v` 。而所剩下的還沒有變成零的數就是兩數的最大公因數，也就是 `u` 。這邊我們還需要將 `u` 進行左移 `shift` bit 的動作，因為我們一開始的時候先將兩者有2的公因數都先提出來了，所以我們要將其加回去。
```cpp=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;
```
XXX = ?
`(a)` u
**`(b)` v**
`(c)` u + v
`(d)` u - v
`(e)` u >> 1
`(f)` v >> 1
YYY = ?
`(a)` u
`(b)` v
`(c)` u << v
`(d)` v << u
**`(e)` u << shift**
`(f)` v << shift
### 測驗五
```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;
}
```
這邊可以視為對一個 `bitmap` 進行掃描，大小為 `bitmapsize` ，總共占用記憶體空間 bitmapsize\*64 bits。而 `out` 則用來記錄對於這個 `bitmap` 相對起始指標來說值為1的 bit 位置。外層迴圈目的是掃過整個 `bitmap` 內部的每一個元素，內部的迴圈則是針對每一個64 bit 的 `bitmap` 元素紀錄。可以把它想像成是64行、 `bitmapsize` 列的二維陣列。
***可用 clz 改寫為效率更高且等價的程式碼:***
```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;
}
```
前面到第一個迴圈的部分都是一樣的，一樣是掃過整個 `bitmap` 內部的每一個元素，裡面的部分我們先看到
```cpp=8
while (bitset != 0) {
uint64_t t = KKK;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
```
我們先不管 `t` 是甚麼，後面 `__builtin_ctzll(bitset)` 能夠直接幫我們回傳LSB數過來第一個1，所以接下來我們應該是要消掉已經記錄完的這個1。
`bitset ^= t` ，我們知道這個 `t` 有個特性，就是在想要保留的 bit 位置會是0，唯一一個需要消除的位置(也就是LSB數來遇到的第一個1)會是1。當中只有 `(e)` bitset & -bitset 可能做到，因為對於二補數系統，加上負號代表作一次 NOT 操作後加一，這個加一的動作會造成進位並翻轉低位 bit ，這時候和自己 AND ，能夠保留LSB數來遇到的第一個1也上全部翻轉。例如原本是 `0x10011100` 二補數負數是 `0x01100100`， `bitset & -bitset` 操作後變成 `0x00000100`。
KKK = ?
`(a)` bitset
`(b)` bitset & 0x1
`(c)` bitset | 0x1
`(d)` bitset ^ 0x1
**`(e)` bitset & -bitset**
Sign in with Wallet
Connect another wallet