# 2020q3 Homework3 (quiz3)
contributed by < `justapig9020` >
###### tags: `sysprog2020`
## Outline
[TOC]
## Link
[作業區](https://hackmd.io/@sysprog/2020-homework3)
[題目](https://hackmd.io/@sysprog/2020-quiz3)
[github](https://github.com/justapig9020/sysprog2020-quiz3)
## 測驗 `1`
```cpp
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) >> 1) > 0;
unsigned int fixu = -(logical & (m < 0));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
- [ ] 解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
- [ ] 練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;
### 議題 `1`
:::info
解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
:::
在 x86 組語中右移運算分為兩種，邏輯右移 (Shift Logical Right, SHR) 與算術右移 (Shift Arithmetic Right, SAR)。其中邏輯位移即為常規意義上的右移運算，將位元右移並在高位元處補上對應數量的 `0` ;而算數位移在位移後則會根據原先 `MSB` 數值，補上對應數量的相同數值。
舉例來說，一八位元數 `0x80` 在經由 `SHR 1` 與 `SAR 1` 後分別為 `0x40` 與 `0xc0` 。
而題目中所述的 ==implementation-defined== 在 `gcc` 中被實作成使用 `SAR` 。簡而言之，在 `gcc` 中對有號數進行右移時會使用 `SAR` 而無號數則為 `SHR` 。
透過簡單實驗驗證。
```cpp
#include <stdint.h>
#include <stdio.h>
#define MAX 0xFFFFFFFF
int main(void) {
int32_t sar = MAX;
uint32_t shr = MAX;
printf("SAR: %x -> %x\n", sar, sar >> 3);
printf("SHR: %x -> %x\n", shr, shr >> 3);
sar &= ~(0x80000000);
shr &= ~(0x80000000);
printf("SAR: %x -> %x\n", sar, sar >> 3);
printf("SHR: %x -> %x\n", shr, shr >> 3);
return 0;
}
```
經過 gcc 編譯我們可得
```asm
_main: ## @main
...
mov esi, dword ptr [rbp - 8]
mov eax, dword ptr [rbp - 8]
sar eax, 3
...
call _printf
mov esi, dword ptr [rbp - 12]
mov ecx, dword ptr [rbp - 12]
shr ecx, 3
...
call _printf
...
mov esi, dword ptr [rbp - 8]
mov ecx, dword ptr [rbp - 8]
sar ecx, 3
...
call _printf
mov esi, dword ptr [rbp - 12]
mov ecx, dword ptr [rbp - 12]
shr ecx, 3
...
call _printf
```
可以發現 `int32_t sar` 在位移運算上使用 `SAR` ，而 `uint32_t slr` 則是使用 `SLR` 。
由於無法肯定當前編譯器對於向右位移在有號負數上會使用 `SAR` 或是 `SLR` ，首先透過位移有號負數來檢測這件事。對應程式碼：
```cpp
const int logical = (((int) -1) >> 1) > 0;
```
考慮編譯器使用 `SHR` 的狀況。分為兩種情形
1. m 為正數，高位需補 `0`
2. m 為負數，高位需補 `1`
對應程式碼：
```cpp
unsigned int fixu = -(logical & (m < 0));
```
這段程式碼有個需要注意的地方。當原本編譯器就使用 `SAR` 的情況直接進行位移運算即可，便不再另行處理補位位元，程式碼 `logical &` 便是在處理這種情況。
由於 `-1` 為 `0xFFFFFFFF` ，因此當 `m` 為負數時 `fixu` 為 `-1` 否則為 `0` 。
透過將其轉換為
依據 [ISO/IEC 9899:TC2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 標準的 6.5.7 章第 5 節 (第 85 頁):
> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral E2 part of the quotient of E1 / 2 .
## 測驗 `2`
```cpp
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) & 0x1);
}
```
- [ ] 解釋上述程式運作原理;
- [ ] 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;
- [ ] 練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive，應善用 clz;
- [ ] 研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告;
> x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 Selecting the Golomb Parameter in Rice Coding。
### 議題 `1`
:::info
解釋上述程式運作原理;
:::
分析三組判斷式，前兩組判斷式首先判斷 `num` 需為 2 的冪次，原理如下。
$2^n$ 由 $2^0 = 1$ 起，每當 n + 1 等同於 $2^{n-1} * 2$ 。由於二進制中乘二等同於左移一位元，可知 $2^n$ 在二進制表達中永遠只會有一位元為 `1` 。判斷式
`(num & (num - 1))==0` 便是再做此一判斷，當任意數 `-1` 時，在二進制上由於借位，會呈獻成原數由右數來第一個 1 變成 0 ，而其右的所有 0 變成 1 。下表透過 8 為例展示此一特性。
| 8 | 8-1 |
|-|-|
|0b1000|0b0111|
因此透過 n & (n-1) 可以快速得知 n 是否只含有最多一位元為 1 ，進而得知其是否為 2 的冪次。然而其中有一例外 `0` ，由於 `0` 滿足最多一位元為 1 的條件，而又不屬於 2 的冪次方，需額外透過 `num > 0` 來處理。
最後一組判斷式則是透過判斷唯一的那一位元 1 的位置進一步確認 `num` 為 4 的冪次。如同 2 的冪次， 4 的冪次再二進制上也可以透過位移來實現， `n * 4 == n << 2` 。由於一次一次位移 2 位，因此可以推知 1 所在位元的位置的奇偶性會保持一致。若將最低位元視為 $b_1$ 此後第 n 為元為 $b_n$ 的話，可以斷言若 `num` 為 4 的冪次，且 `num` 的 $b_n$ 為 1 ，`n` 必為奇數。
題目中的 `num` 藉由 `__builtin_ctz` 計算 $b_n$ 右側之位元數，可以轉換為 `n - 1` 。根據剛才推論 `n` 必為奇數，則 `__builtin_ctz` 之運算結果在 `num` 為 4 的冪次時必為奇數，因此我們可以透過 `&0x1` 的運算進行奇偶性的判定。
透過以上三組判斷式，可以組合出以下邏輯並判斷是否為 4 的冪次。
1. 需為 2 的冪次
2. 額外處理特例 `0`
3. 2 的冪次 `n` 不為奇數
## 測驗 `3`
```cpp
int numberOfSteps (int num)
{
return num ?
__builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}
```
- [ ] 解釋上述程式運作原理;
- [ ] 改寫上述程式碼，提供等價功能的不同實作並解說;
>提示: [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) 中提及許多 bitwise operation 的使用，如 [bit inverse](https://hackmd.io/@sysprog/ByzoiggIb)、abs 等等，是極好的參考材料。
- [ ] 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，實作出 branchless 解法，儘量縮減程式碼行數和分支數量;
## 測驗 `4`
```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 (v);
return u << shift;
}
```
- [ ] 解釋上述程式運作原理;
- [ ] 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
## 測驗 `5`
```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;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
- [ ] 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
- [ ] 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
- [ ] 思考進一步的改進空間;
Sign in with Wallet
Connect another wallet