---
title:
image:
description:
tags: NCKU Class , 進階電腦系統理論與實作 , 2020q3
---
# 2020q3 Homework3 (quiz3)
contributed by < `TsenEN` >
> [題目](https://hackmd.io/@sysprog/2020-quiz3)
> [作業要求](https://hackmd.io/@sysprog/2020-homework3)
## 測驗 1
### 除法規範
在看題目敘述的時候看到 $\frac{-5}{2} = -3$ 這讓我很糾結答案為 $-3$ ，很想確認是否所有程式語言編出來的答案都會符合正整數除法的規範:
$if$ $\forall a,d \in \mathbb{N},d>0 , \exists! q,r \in \mathbb{Z},$ $such$ $that$ $a = qd+r,0\le r <d$
詳情可以參考[程式語言中負數取餘的問題](https://www.itread01.com/content/1544306778.html)(取餘不同商數自然不同)。
### 負數的 ASR 是否等於除法 ?
回到題目是要針對有號整數的跨平台 ASR 實作，會這樣做是因為每個平台右移補上的`bit` 可能是 0 or 1 ，補 0 的一定錯，那補 1 就一定對嗎 ? 這邊缺乏證明，如果補 1 會錯那就要找到反例 ! 找不到就要給證明。
所以我們要證明嗎 ? 不用(要)，這邊考慮一個數字 `-1 = 11111111b`(這邊用`8 bits`討論)今天我們不管對它右移幾百次它永遠都等於 -1 ，這也違反了數學定義，因為它沒有趨向$-\infty$，這是很麻煩的一件事，==負數的 ASR 是否等於除法 ?== 答案是 NO !詳情請參閱 [Wikipedia, Arithmetic shift](https://en.wikipedia.org/wiki/Arithmetic_shift) 的子標題==Non-equivalence of arithmetic right shift and division==。
### OP1 = ? & OP2 = ?
```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));
}
```
先從 return 下手可以看出 `fix` 是用來修正當 `m` 是負數的時候右移的 `n bits` 產生出來 0 的變數，所以當 `m` 是正數 `fix = 0`，這指出 `fixu` 連帶 `logical` 都要為 0，那 `logical` 啥時為 0 ，這就要讓那個 `-1 = 11111111b > 0` 不成立，所以我們要思考這個 `logical` 的用意跟這個 -1 是幹嘛的？，==今天我們要跨平台==，那我們就是要先判斷這個平台右移是補 0 or 1 ? 我們再回來注意這個 `-1 = 11111111b` 我們發現如果今天右移 -1 會得到以下兩種情況：
| Behavior | Binary | Decimal |
| -------- | -------- | ------- |
| fill 0 | 01111111 | 127 |
| fill 1 | 11111111 | -1 |
我們去右移 `1 bit` 可能會得到 1 個正數或 1 個負數，再去跟 0 比大小就可以得知這個平台的填補行為，補 1 那 `logical` 自然是 0 ，補 0 那 `logical = 1` ， `logical = 1` 之後就要繼續做修正行為。
所以我們得到 ==OP1 = (b)>>1==。
:::warning
這邊我不太懂為什麼要先用一個 `unsigned int fixu` 來接之後再用一個 `int fix` ，為什麼不直接用
```c
int fix = -(logical&(OP2));
```
:::
再來我們注意`(m >> n) | (fix ^ (fix >> n)` 看得出來右邊取 XOR 是要去辨別哪邊需要補 1 (這是利用奇同位特性來實現)，而中間的 `|` 我們可以感受到一定只有要修正的地方會是 1 其他會是 0 對吧？
所以我們帶點例子，下去操作看看：
| name | Binary | Decimal |
| ------------ | -------- | ------- |
| m | 11111011 | -5 |
| n | 00000001 | 1 |
| logical | 00000001 | |
| m>>n | 01111101 | |
| fix^(fix>>n) | 10000000 | |
| return | 11111101 | -3 |
我們可以看到 `fix^(fix>>n) = 10000000b` 這樣才能修正 `m>>n` 的錯誤，那我們就可以去猜測 `fix` 跟 `fix>>n` 的值，這邊要先看 `logical` 的值來排除不可能的狀態要討論兩種情況：
假設平台補 0 ，則 `logical = 1`，即使是補 0，當 `m` 是正數補 0 是沒差的，所以要考慮 `m<0` or `m >= 0` ，假設今天是用 `m>=0` 那得出來的 `fixu` 不會等於 `0` 那就會錯。
所以 ==OP2 = ( c ) m<0==
## 測驗 2
GCC extension 其中兩個是 ctz 和 clz:
```!
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.
```
```!
Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
```
我們可用 __builtin_ctz 來實作 [LeetCode 342. Power of Four](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，假設 int 為 32 位元寬度。實作程式碼如下:
```c
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1)) == 0 &&
!(__builtin_ctz(num) OPQ);
}
```
### num > 0：
4 的冪次必定大於 0
### (num & (num - 1)) == 0：
這邊要思考 `num & (num - 1)` 用意，我們都知道`奇數 = 偶數 + 1` 這帶來的特性轉成 Binary 會注意到(假設 8 bits , `b7 b6 b5 b4 b3 b2 b1 b0`)，奇數的 `b0` 必為 `1`，如果 `num` 為奇數再去減 1 就會變偶數那` num-1` 的`b0 = 0`。
再來思考為何 `&` 跟 `== 0` ，什麼樣的情況 `&` 會變成 0 ? 答案是當兩數的二元表示式每個位元皆不同即可達成，所以我們要使某數減 1 之後可讓它達成剛剛敘述的情況，開始觀察你會發現只有當那個數字的二元表示的 MSB = 1 其他為 0 才可能達成 !
| Name | Binary | Decimal |
| ----- | ------ | ------- |
| num | 1000 | 8 |
| num-1 | 0111 | 7 |
其他數字不可能達成嗎 ? Yes ! 先舉個例：
| Name | Binary | Decimal |
| ----- | ------ | ------- |
| num | 1110 | 14 |
| num-1 | 1101 | 13 |
證明：
假設某數 $\exists p$ 的二元表示式除了 `MSB = 1` 之外一定 $\exists bx,0\le x<7$(設系統可以處理8位元,`b7 = 1`) ,$bx$ 為位元數(e.g. `00001001b , b3 = 1, b0 = 1`),其中 $|bx|\ge1$ 且 $bx=1$，使 $p - 1$，因為除了 `MSB = 1` 還存在 `bx = 1` ，所以 `bx` 會先借位而不是 `MSB`，這樣去做 `&` 必不會 `== 0`，故此的證。
而當 `MSB = 1` 其他位元 `= 0` 時，此數必為 2^n^ ，所以 `(num & (num - 1)) == 0` 就是檢查此數次否為 2 的冪次(如果是 4 的冪次必為 2 的冪次)。
### !(__builtin_ctz(num) OPQ)
再來就剩檢查是否為 $4^n$ ，而 $4^n = 2^{2n}$ 又 $2^n$ 的二元表示 `MSB = 1` 其他位元 `= 0`，故 $2^{2n}$ 的 `MSB` 會出現在奇數位置上，相當於 `MSB` 前面的 0 個數必為偶數，所以我們可以用 __builtin_ctz(num) 來計算從 `LSB` 直到 第一個 1 的個數，再去 ==&1== 可以檢查是否為偶數，所以 ==OPQ = &1==。
## 測驗 3
建議先去看[題目](https://hackmd.io/@sysprog/2020-quiz3)的證明。
對應到 C 程式的實作:
```c
unsigned popcnt_naive(unsigned v) {
unsigned n = 0;
while (v)
v &= (v - 1), n = -(~n);
return n;
}
```
:::warning
這邊我不懂為什麼 n += 1 要實做成 n = -(~n)，是因為不用處理進位嗎？
:::
以下常數時間複雜度的實作:
```c
unsigned popcnt_branchless(unsigned v)
{
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
```
:::warning
這邊我不懂為什麼 `popcnt_branchless`實作要每 4 個位元 (nibble) 為一個單位計算 1 的個數，是因為 4 bits 剛好可以用 16 進位來裝補嗎？
:::
針對 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```c
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
先列出 1342 的要求的演算方式：
* 如果是 odd：表示 `LSB` 是 1，減 1 是把最後一個 bit 設為 0 ，這樣就變 even 。
* 如果是 even：表示`LSB` 是 0，除 2 就是將整組位元右移。
題目要求是變成 0 代表 2 進制表示為全 0 ，好所以我們再把 `num` 轉成 2 進制，我們開始思考要怎樣才能在"最少步驟變成 0"，假設系統現在只能處理 8 bits：
| Name | Binary | Decimal | |
| ---- | -------- | ------- | ----------------------- |
| num | 00110100 | 52 | b7 b6 b5 b4 b3 b2 b1 b0 |
我們 greedy 的去想會得到兩件事：
1. 最後一個 1 後面的 0 其實都不用處理。
* 像是 `num` 的 `b7、b6` 不需處理。
2. 當我有幾個 1 每當我把它右移到 `LSB` 的時候就是要做 -1 的動作。
* `num` 的 `b5、b4、b2` 每當右移到 `b0` 都會需要 -1 。
好我們如何達成 1. 很簡單 `int __builtin_clz (num)` 幫你計算前面 0 的個數，好我們如何達成 2. `__builtin_popcount(num)` ，很好這樣答案是 `__builtin_popcount(num)+32-int __builtin_clz (num)`，抱歉答錯，你多算一個！因為最後一步必是" 00000001b " (1 減 1 變成 0)，所以當我們在計算 `__builtin_popcount(num)` 就算在裡面了，所以答案會是 `__builtin_popcount(num) + 32 - __builtin_clz(num) - 1 = __builtin_popcount(num) + 31 - __builtin_clz(num) 。`
==AAA = (a) __builtin_popcount(num)==
==BBB = __builtin_clz(num)==
Sign in with Wallet
Connect another wallet