2020q3 Homework2 (quiz2)
===
###### tags: `(2020q3)進階電腦系統理論與實作`
contributed by < `jeremy3951` >
開始日期:2020/09/20
## 測驗`1`
2020/09/26
要填補的程式碼 :
```cpp
bool is_ascii(const char str[], size_t size)
{
if (size == 0)
return false;
int i = 0;
while ((i + 8) <= size) {
uint64_t payload;
memcpy(&payload, str + i, 8);
if (payload & MMM)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
根據要改寫的程式碼可以看出想要一次比8個字,剩下不到8個字的就一一比對,所以payload內容如下:
```graphviz
digraph struct{
rankdir=LR;
word[shape="record",label="{第1個字|第2個字|第3個字|第4個字|第5個字|第6個字|第7個字|第8個字}"]
}
```
再觀察前面的範例:
```cpp
bool is_ascii(const char str[], size_t size)
{
if (size == 0)
return false;
for (int i = 0; i < size; i++)
if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
return false;
return true;
}
```
得知判斷的敘述為`if (str[i] & 0x80)` , 把它用成8份放在64bits裡面就是0x8080808080808080
```graphviz
digraph struct{
rankdir=LR;
word[shape="record",label="{80|80|80|80|80|80|80|80}"]
}
```
故這題選 ( d )
## 測驗`2`
2020/09/20
第二題題目:
```cpp
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
第二題分析:
目前對這題目的理解是有一個函式可以把輸入的字元轉成16進位中所代表的10進位數字.
1. in就是我們的input,然後它會跟MASK進行and運算並寫入letter.
2. letter分別會向右移AAA個bits和BBB個bits,再把結果or起來寫入shift.
3. 最後return(in+shift)和0xf的作and的結果.
觀念更新: 我一直以為 `& 0xf`是取前4個bits,但後來看網路上的範例發現好像是取最後4個bits,那這樣就說得通了.
藉由ASC表格觀察,若是字元0~9,可以對應到第二個碼.( 0對應到0x3**0**,1對應到0x3*1* )
若是字元a~f,可以發現第二個碼加上9就是相對應的10進位數字了. 舉例:(a對應到0x61 , 1+9=10)
最後從程式碼最後面開始倒推 : & 0xf就是取(in+shift)的最右邊四個bits.
根據我們上面的觀察得知,如果是字元0 ~ 9其實就直接找到答案了(最右邊4個bits),但是字元a ~ f是對應的第二個碼 " +9 ", 9轉成2進位就是1001,由此可推得最右邊4個bits一定是 "原來的bits" + "1001" , 對應程式碼最後一行可得知shift的最右邊4個bits一定是"1001",再往前一行程式碼觀察得知,shift被letter的兩種位移做完or運算後寫入,所以要觀察letter的樣子,我們再看第一行
`const uint8_t letter = in & MASK;`
第一行可得知要把input跟某種mask做and運算,已知最右邊四個不能被改變,所以mask最右邊4個bits一定是0,至於左邊4個bits就要看回來碼表了,
0~9: 0x3開頭, 3對應的2進位是:0011
a~f and A~F : 0x6 和 0x4開頭 ,對應到的分別是 0110 , 0100
由此得知mask的第3第4個bit一定要是0,這樣才能保持shift全0,若為0x1000,那mask等於沒用,所以推定一定是0x0100,這樣做完mask後,
舉例： a
0110 0001
& 0100 0000
--------------------------
0100 0000
剩下一個bit來生成1001可得知bit位移分別為3和6
2020/09/21
## 測驗`3`
2020/09/21
此題的想法:想要算出餘數,先算出商數後再做簡單的*-運算就好
把分子分母同乘 $2^n$ :
$\dfrac{n}{d} * \dfrac{2^n}{2^n}$ = $n * \dfrac{2^n}{2^n*d}$ = $n* \dfrac{2^n}{d} * \dfrac{1}{2^n}$
\
input =n , M = $\dfrac{2^y}{d=3}$ , $\dfrac{1}{2^y}$= >>64 , y=64.
\
xxx = (M-1)*3 = (2^64^/3-1)*3=2^64^-3(答案像(f))
2020/09/23:
發現一件事: *M代表$\dfrac{1}{D}$在二進位中的表示法!!*
疑問1: 為什麼 0xFFFFFFFFFFFFFFFF/(D)會等於$\dfrac{1}{D}$?
疑問2: 為什麼要位移64個bits?
對於疑問1的思考:
我參考了 [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 裡面的程式碼
`uint64_t two_to_k = ((uint64_t)1 << 32);`
發現他們得到(1/D)的方式是把我們的答案加1(127~0bits只有第64個bits是1),
再用此答案去除D,竟然得到一樣的結果,這讓我想到如果一半的bits是拿來裝小數(1/D),另一半的bits拿來裝商數,這樣就是用1去除D了!
這也就順便回答了我的第二個疑問,位移64bits後剩下的就是商數了,把商數return回去就好算餘數了
## 測驗`4`
我的分析:
依照題目的(D=3),
M=(1/D)的二進位表示法,但是題目是用n * M和M來做比較看是否整除,其實我真的不懂為什麼拿M來跟n * M做比較就能看得出來否整除.
最後我拿出紙筆trace後,發現一些奇特的事:
1. 整除的狀況:運算結果後面的bits有一些非0但是中間的幾乎都是0,這導致n*M很明顯 ~~(用看得就知道)~~ 小於M
2. 沒整除的狀況:運算結果很多bits都是1,但經過比對後發現總是比M本身還大
這時我突然想到無限循環小數!
無限循環小數本應是無止盡的,但是在有限的bits裡面要表示會表示不完(所以尾端+1).
所以若n能整除D的話,中間無限循環的部分會很完美的進位(只留下0),最後進位到算商數的地方,所以才會有中間一堆bits為0的狀況,因此n*M的運算結果一定會小於M.
後來我又把D帶4進去算過一遍,發現其實觀念是差不多的,只是循環小數比較難想而已,後面我就歸納出了一個結論:
### 把n/D後的餘數想成一個裝有刻度的的水杯
**我要找一個可以衡量是否整除的刻度!**
```graphviz
digraph struct{
m[shape = "plaintext",label = "M"]
rankdir=LR;
subgraph struct1{
node1 [
shape = record
label = "D-1/D|...|3/D |2/D |1/D "
]
}
m->node1
}
```
理想狀態 :
M= (1/D),
若n能整除D,代表沒有餘數,(n*M=0)<M, (杯子裡沒有水)
若n不能整除D,代表有餘數,而且至少>=(1/D). (杯子裡的水至少一個刻度)
例外狀況 :
如果(1/D)為循環小數,當n能整除M的時候,餘數不會是0,只會剩最後4個bits乘上n的結果(因為中間都被完美的進位了),可以把此狀態想成杯子裡裝一點點水而已(一定小於1/D).
所以對於水杯刻度的挑選,刻度最好是在接近1/D但又比它小一點,也就是M-1,但M>>1也可以,由此可知YYY的範圍 :
$0<YYY<=M$ , 故這題選( c ) ,( d )都可
2020/09/23
## 測驗`5`
2020/09/26
要填補的程式碼如下 :
```cpp
#define PACKED_BYTE(b) (((uint64_t)(b)&(0xff))*0x0101010101010101u)
/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
size_t k = n / 8;
for (size_t i = 0; i < k; i++, s += 8) {
uint64_t *chunk = (uint64_t *) s;
if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
*chunk ^= mask;
} else
strlower(s, 8);
}
k = n % 8;
if (k)
strlower(s, k);
}
```
疑問一 : 為什麼 PACKED_BYTE() 裡面要`*0x0101010101010101u`?
觀察此行程式碼可以發現開頭是 0x 代表後面接的是16進位數字 , 又因為`(b) & (0xff)` 這行代表只留 b 的最右邊 8 個 bits , 然後再跟上述的 0x0101... 相乘 :
||||0x0101010101010101|
| ---- | ---- | ---- | ---- |
|x|||0x80|
|||||
||||0000000000000000|
|+||0|808080808080808|
|||||
|=|| ~~0~~ |8080808080808080|
這結果就跟第一題的判斷式一樣同樣為判斷是否為 ASCII , 所以 VV1 選 ( e ) 0x80 .
透過 VV1 可以看出 PACKED_BYTE() 這個 function 是把傳入的數最右邊 8 個 bits 以循環的方式放進 64 bits 裡面 .
知道這個訊息後就直接跳到 VVV4 , 觀察程式碼 `(A ^ Z) & PACKED_BYTE(VV4)` 可得知 , 等等要做 & 運算 , 又 `PACKED_BYTE(VV4)` 運算出來的值都是 101010.... , 202020.... , 404040.... 這種的.
**所以 & 運算出來的目的就是只看某些 bits 而已其他bits不重要.**
再往下看程式碼 `*chunk ^= mask;` , 看到這邊我就猜想這個 XOR 運算就是想要針對某些 bits 反轉而已 , 想到這邊我就去查 [ASCII 表](https://www.cs.cmu.edu/~pattis/15-1XX/common/handouts/ascii.html)
觀察 A(65) 和 a(97) 且各自轉成16進位表示(0x41 , 0x61) , 最後再看 4(0100) 和 6(0110) 只差 1 個 bits 而已 , 所以 mask 值就是 "0x0010 0000"
得到這個資訊後回推 , 先把 mask 往左位移 2 個 bits 得"0x1000 0000" , 再拿回去對照 `PACKED_BYTE(VV4)` 就可得知 VV4 就是 0x80 了! 所以這題選 ( e )
接下來的 VV2 和 VV3 要做的事我猜就是判斷這個字元是大寫還是小寫?
由 A^Z 就可得知字元是否大小寫 :
* 大寫的話 , A^Z 的第 8 個 bit 就是 1 (這樣跟 0x8080808...做 & 後對應的 mask 才有值可以去轉換成小寫)
* 小寫的話 , A^Z 的第 8 個 bit 就是 0 (這樣跟 0x8080808...做 & 後對應的 mask 會等於 0 就不用轉換了)
由此可知 , A 和 Z 著重在第 8 個 bit 是否相同(因為要做 XOR 運算)
計算 `PACKED_BYTE(128 - 'A' + VV2 )`
A 在 ASCII 表中代表的 10 進位數字是 65 , 換算成 16 進位是 0x41 , 128-65=63 , 換算成 16 進位是 0x3F.
再來看 Z : `PACKED_BYTE(128 - 'Z' + -1)`
Z 在 ASCII 表中代表的 10 進位數字是 90 , 換算成 16 進位是 0x5A , 128-90=38 , 換算成 16 進位是 0x26.
接下來我把 *chunk 分別用一些值帶下去算後才了解了 A 和 Z 就是負責把大寫字母給區分出來 , 只要 *chunk 的 ASCII 碼超過這個區間 A^Z 的第 8 個 bit 就會等於 0 .
接下來觀察 A : 0011 1111+c 和 Z : 0010 0110+c
要讓 A 和 Z 形成緊繃的區間 , A 要盡量小 , B 要盡量大
接下來把 A 的 ASCII 碼和 Z 的 ASCII 碼分別帶入:
A 帶入
0011 1111 + 0100 0001 = 1000 0000(最高 bit 已進位)
0010 0110 + 0100 0001 = 0110 0111(最高 bit 未進位)
這區間目前符合最小的限制
Z 帶入
0011 1111 + 0101 1010 = 1001 1001(最高 bit 已進位)
0010 0110 + 0101 1010 = 1000 1000(最高 bit 已進位)
代表現在這個區間沒有把 Z 當作大寫字母 , 所以 Z 這個界限要再小一點 : 0010 0110 (-1) = 0010 0101
再用 Z 帶入 :
0011 1111 + 0101 1010 = 1001 1001(最高 bit 已進位)
0010 0101 + 0101 1010 = 0111 1111(最高 bit 未進位)
剛好符合區間 , 所以 VV2 和 VV3 就是 0 , -1 了
2020/09/27
## 測驗`6`
2020/9/24
題目的限制:
`
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
`
程式碼如下:
```cpp
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
lower ^= nums[i];
lower &= KKK;
higher ^= nums[i];
higher &= JJJ;
}
return lower;
}
```
**這題我嘗試不看答案想 , 但是想不出來 , 看了答案後 , 又拿出紙和筆trace我還是看不懂解答作法 , 於是我去參考其他同學的作法 , 還是很難理解其意義 , 我想這題的解法應該是超過我原本的知識範圍 , 所以我只能記錄我的理解路線來說明我看了什麼後懂了什麼.**
### 理解路線:
還沒看答案的時候,就是想著如何記錄元素的重複次數,用這個方法來偵測誰是烙單的元素,後來一直想都想不出來覺得好像想錯這題的解題方向了.
看完了解答,一開始還是不太了解這個程式碼的運作原理,於是我開始用了最原始的方法(紙筆大法)來[trace](https://hackmd.io/BrYYVHHhQD2xKN84xHBMwg).
trace的過程我學到了Xor運算可以把不同的數字藏在一個數字裡面,像是 `int num=a XOR b XOR c...`
不過,即使我trace了程式碼,lower和higher裡面的值還是很玄 . 後來 , 我參考了 [joey3639570](https://hackmd.io/@joey3639570/Hkoajm0Vw#%E5%BB%B6%E4%BC%B8%E5%95%8F%E9%A1%8C4) 的說法了解到原來是lower和higher就像是狀態轉移的暫存點 , 第一次出現放在lower , 第二次出現放在higher , 第三次出現就要讓它消失在higher和lower .
但我還是覺得怪怪的 , 因為我沒辦法理解程式執行到一半時的lower值和higher值所代表的意義.
後來我看到了[leetcode 之 Single Number II](https://blog.csdn.net/yutianzuijin/article/details/50597413?fbclid=IwAR3eyt8_83wh1Zat21hEBf1C_T3X1Mw_ZYyP2Wvu2Pm4ym_1cGXbPleQu4w) 這篇文章中的其中一句最關鍵的話讓我終於懂了這程式的操作!
**`一个32位int型整数可以看成32个独立的位，每一位都可以独立考虑，所以后面的描述都单指一个位。当一个数最多出现两次时，我们可以只用1 bit来描述，但是当一个数最多出现三次时，我们必须要用2 bit来描述。`**
原來是針對input的每一個 " **bit** " 來做狀態轉移 !
### 操作如下:
欲插入的數字依序為{3,2,3,3}
| 輸入數字 | bit2 | bit1 | bit0 |
| ---- | ---- | ---- | ---- |
| 3 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 3 | 0 | 1 | 1 |
| lower= | 0 | 1 | 0 |
從上面的表格可得知: bit1的1出現4次 , 然而bit0的1出現3次而已.
所以最後的lower值就是裝只出現1次的bit值分別為0 , 1 , 0
至於higher值就是裝出現兩次的bits值此例沒有所以higher為0
得到的結果:
* **lower裝只出現過1次的bit**
* **higher裝出現過2次的bit**
插入過程操作如下:
| 輸入數字 | bit2 | bit1 | bit0 |
| ---- | ---- | ---- | ---- |
| 3 | 0 | 1 | 1 |
| lower= | 0 | 1 | 1 |
| higher= | 0 | 0 | 0 |
| 輸入數字 | bit2 | bit1 | bit0 |
| ---- | ---- | ---- | ---- |
| 3 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 |
| lower= | 0 | 0 | 1 |
| higher= | 0 | 1 | 0 |
| 輸入數字 | bit2 | bit1 | bit0 |
| ---- | ---- | ---- | ---- |
| 3 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| lower= | 0 | 0 | 0 |
| higher= | 0 | 0 | 1 |
| 輸入數字 | bit2 | bit1 | bit0 |
| ---- | ---- | ---- | ---- |
| 3 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 3 | 0 | 1 | 1 |
| lower= | 0 | 1 | 0 |
| higher= | 0 | 0 | 0 |
為了做到對1個bit有3種狀態轉移 , 所以我們要用**2個bits**來記錄 , 如下圖 :
```graphviz
digraph struct{
a[shape="record",label="num|<1>1|<2>2|<3>3|<4>4"]
lower[shape="record",label="lower|<1>1|<2>2|<3>3|<4>4"]
higher[shape="record",label="higher|<1>1|<2>2|<3>3|<4>4"]
lower:1->a:1
higher:1->a:1
}
```
接下來把狀態轉移的真值表畫出來並從該真值表的運算式推出程式碼 .
### 程式碼解析:
狀態轉移的真值表如下：
| higher | lower | input | higher_output | lower_output |
| ---- | ---- | ---- | ---- | ---- |
|0|0|0|0|0|
|0|0|1|0|1|
|0|1|0|0|1|
|0|1|1|1|0|
|1|0|0|1|0|
|1|0|1|0|0|
假設input是正要插入的數字 , 則higher 和 lower就是上一個bit的 higher_output 和 lower_output.
higher_output 和 lower_output就是根據input,higher,lower所更新的值.
由上述真值表推得:
lower_output
$=\overline{higher}\times\overline{lower}\times input +\overline{higher}\times lower\times\overline{input}$
$=\overline{higher}\times (\overline{lower}\times input +lower\times\overline{input})$
=$\overline{higher}\times(lower \oplus\ input)$
故 KKK 為 ( c ) `~higher`
higher_output:
依照程式碼的敘述,higher_output是用lower_output當作input而不是lower,算式如下:
$=\overline{higher}\times\overline{lower\_output}\times input +higher\times\overline{output\_lower}\times\overline{input}$
$=\overline{output\_lower}\times(\overline{higher}\times input +higher\times\overline{input})$
$=\overline{output\_lower}\times(higher\oplus input)$
故 JJJ 為 ( d ) `~lower`
09/26
Sign in with Wallet
Connect another wallet