# D03: assessment
contributed by <`rex662624`>
## 第二周測驗題 第2題
這題是要實作 float number * 0.5 的code。以下為題目
```clike=
typedef unsigned int float_bits;
float_bits float_x0_5(float_bits f) {
unsigned sig = f >> 31;
unsigned rest = f & 0x7FFFFFFF;
unsigned exp = f >> 23 & 0xFF;
unsigned frac = f & 0x7FFFFF;
/* NaN or INF */
if (exp == A0) return f;
/* round to even. Last 2 bits of frac are considered:
* 00 => 0 just >> 1
* 01 => 0 (round to even) just >> 1
* 10 => 1 just >> 1
* 11 => 1 + 1 (round to even) just >> 1 and plus 1
*/
int addition = (frac & 0x3) == 0x3;
/* Denormalized */
if (exp == 0) {
frac >>= A1;
frac += addition;
/* Normalized to denormalized */
} else if (exp == 1) {
rest >>= A2;
rest += addition;
exp = rest >> A3 & A4;
frac = rest & 0x7FFFFF;
/* Normalized */
} else {
exp -= A5;
}
return sig << A6 | exp << 23 | frac;
}
```
#### 解題
首先4~7行分別把正負號、除了正負號剩下來的數字、次方項、數字部分離出來。注意到 & 在這裡都是 mask 的功能。 例如 f & 0x7FFFFF;就是把後23位保留，正好是IEEE-754 單精度的 mantissa 部分。
第10行的部分，NaN 和 INF 乘上 0.5 分別就是 return NaN 和 INF ，而他們的次方部分為==11111111(=A0)==。
第18行的addition是 round to even 作用。([CS:APP 3/e](http://csapp.cs.cmu.edu/) 第83頁有講述 round to even) 也就是乘上0.5後，要是有動到 mantissa ，就必須要考慮捨入問題。而這裡只有最後2 bit 是11時要+1，(frac & 0x3)是先把最後3位 mask 出來 ，而後會做 (最後三位)==0x3 ;如果最後兩位是11，addition才=1 。
而除了上面的 Nan 和 INF ，我們可以分3種狀況 : Denormalized 的數字， Normalized 的數字做完運算後成為 Denormalized ， 還有運算前後皆為 Normalized 。 分別為圖上的if 、 else if 、else 。
首先第一種狀況，因為 Denormalized 的數字 exp 部分為0，所以要乘上0.5，直接在 mantissa 的部分向右移一位(==A1=1==)。最後注意要加上捨入部分。
第二種狀況，因為 exp=1 ，因此由正規數變為非正規數。而26 27行跟第一種狀況做的動作相同(==A2=1==)。第28行的部分，我則是覺得可以改寫成 exp = rest >> A3 ，因為rest本來就是扣掉sign之後的數字，再右移後一定前面的位數都會是0 。甚至可以寫exp = 0就好，因為只有 exp為1 狀況會進入，而做完後一定是 denormalized ，也就是 0 。而這裡的答案是==A3=23 A4=0XFF==，意義是先右移使 exp 在最低位，再用 mask 保證只保留末8位。
:::success
是的！解法有很多種，你可嘗試用其他方法來做，看能否讓程式碼更精簡。
:notes: jserv
:::
最後的else為正規數的部分，只要將次方-1(==A5=1==)就是答案。而下面的==A6=31==，是把他們移到自己應該要放的位置，例如 sig 應該放在最高位。而後用 logic or 就能拚起完整的32bit。
## 第一周測驗題 第5題
考慮以下整數乘法的實作程式碼:
```clike=
int mul(int n, int m)
{
int ret = 0;
for (int c = 0; m; c++, m /= 2)
if (!(m % 2 - 1)) OP
return ret;
}
```
#### 解題
在此題中， c 是用來計算目前跑了幾次 loop ， m 每次都除以2，就是每次都往右 shift 1 bit 。
而 if 內判斷的是若是目前的 m 最後一個 bit 為 1 就要做後面的 OP 。因為 m%2 是把最後的 bit 為何找出來，不是1就是0。而後-1會變成0或-1。再加上一個 !，因為 !0= 1 、 !(-1)=0 ，因此原本 m 最後一個 bit 為 1，if內才會為1。
然後以乘法直式的想法，就可以想出 OP = ret += n << c 。
#### 延伸問題 : 解釋為何乘法可運作？
此處的演算法，與計算機組織學到的二進位乘法器電路相同。
(圖片出自於計算機組織上課投影片Ch3_Arithmetic_1)
這邊的演算法就是數學直式的規則。試想一般二進位直式乘法，若乘數尾數是1，我們會把1乘上被乘數寫下來，之後往左一位看(對應到 m/2 )。而後我們看倒數第二個 bit 時，若又是 1 ，我們會把乘數寫下來，但這時候要寫的位置是在左移 1bit 的位置 (對應n<<c) 。
舉例: 若是 15 X 16 換成二進位是 01111(n) X 10000(m) 。第一次進入 for 迴圈後， m 的最後一位不為0，因此會不做 if 繼續下個迴圈，直到 c=4 ，此時 m=00001 ，才會做 ret+=(01111)<<4 。下次 m/2 後 m 已經=0，所以跳出迴圈，算出答案為11110000，也就是240。
#### * 實驗 : 是否適用於 signed 和 unsigned 狀況
| 測試| 輸出 |
| ---| --- |
|`printf("%d\n",mul(85,16));`|1360|
|`printf("%d\n",mul(-85,16));`|-1360|
|`printf("%d\n",mul(85,-16));`|0|
|`printf("%d\n",mul(-85,-16));`|0|
觀察到: 只適用於兩者皆為 unsigned ，但 n 若是為負號也可運作。 m 若是為負號會使答案為0 。
* 為何 m 為負，此演算法就失效 ?
根據[ Modulo operator with negative values ](https://stackoverflow.com/questions/7594508/modulo-operator-with-negative-values) 得知，若要算`x%y` ，電腦其實是做`x-(x/y)*y` 因此在這裡的狀況，若 m 是負數， if 內需要做 `m%2` ，就等於是做 `m-(m/2)*2` ，因此 if 內的 m % 2 不是0就是 -1 ， 會導致 ==if 永遠不成立，因此最後的 ret 永遠都是0== 。
而會造成上述這個原因是因為我們預測餘數不是0就是1，所以用`m % 2 - 1`來判斷，但是若 m 是負數，餘數就會是0或是-1，因而使演算法失效。
因此，根據上面的觀察，只要把 code 改為以下，就能支援 signed number。
```clike=
int mul(int n, int m)
{
int ret = 0;
for (int c = 0; m; c++, m /= 2)
{
if (!(m % 2 - 1)) ret += n << c;
else if ((m % 2)!=0) ret -= n << c;
}
return ret;
}
```
以上程式碼多加了 else if ，是 m 為負的狀況。因為 m 為負數 ，`m%2` 不是0就是-1，所以若m%2==-1，就要做ret -= n<<c 。用減的原因是因為 m 是負數，因此要用減法而非加法。
而上面的演算法也不會影響到本來的運算。因為若 m 為正數，只分為 m%2 ==1 和 m%2 ==0 ，而 m%2 ==1 會跑進上面的 if ， m%2 ==0 也不會跑進下面的 else if ，與原來的行為相同。
| 測試| 輸出 |
| ---| --- |
|`printf("%d\n",mul(17,8));`|136|
|`printf("%d\n",mul(-17,8));`|-136|
|`printf("%d\n",mul(17,-8));`|-136|
|`printf("%d\n",mul(-17,-8));`|136|
## 第三周測驗題 第2題
考慮到下方函式 `shift_right_arith` 和 `shift_right_logical` 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，而位移量 `k` 的有效範圍在 0 到 `w - 1`。
```clike=
#include <stdio.h>
int shift_right_arith(int x, int k) {
int xsrl = (unsigned) x >> k;
int w = sizeof(int) << P1;
int mask = (int) -1 << (P2);
if (x < 0)
return xsrl P3 mask;
return xsrl;
}
unsigned shift_right_logical(unsigned x, int k) {
unsigned xsra = (int) x >> k;
int w = sizeof(int) << P4;
int mask = (int) -1 << (P5);
return xsra P6 P7;
}
```
#### 解題
首先要釐清何謂[邏輯位移 (Logical shift) ](https://en.wikipedia.org/wiki/Logical_shift)與[算術位移 (Arithmetic shift) ](https://en.wikipedia.org/wiki/Arithmetic_shift) ，以 shift right 來說，邏輯位移不論是正數還是負數，左邊都會補0，而算術位移則是需要補上數字的 MSB(most significant bit) 。因此若是負數就會補1，正數則補0。
題目上的第4、5行，是在第7行做使用。 w 的意義是先得到 int 的 bit 數，因為 1byte = 8 bits ，因此需要左移 3 bits ，`P1=3`。而 mask 是利用 int 總 bit 數，也就是 w ，減去要位移的 bit 數 ，因此`P2=w-k`，而因為邏輯右移需要在前面補上MSB， 而剛才的 mask 除了最低的 w-k bits 會全部都是 1 ，因此要用 or (`P3=|`)，才能使 x 為負數的狀況時，前面補上的 bit 都將是1。
而下面的 function ，也就是算術位移，P4與P5作用都與上面相同(`P4=3` `P5=w-k`)，因為 P5=w-k 是之後要保留下來的bit 數，其他在左邊的bit全部都要填成0。因此為了要保留這些 bits 清空前面的 bits， 因此要用 and 而非 or(` P6= &`)，P7 要改成 ~mask ， 讓前面的 bit 變成0 ，後面 w-k bits 全部都為 1 。
#### 延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
首先查資料時，有查到Java本身就已經有把邏輯位移與算術位移分開，分別是`>>>`(logical shift right )、`>>`( arithmetic shift right)。
##### X86_64
參考[ x86 Assembly Language Reference Manual ](https://docs.oracle.com/cd/E19641-01/802-1948/802-1948.pdf)與[ X86 Assembly/Shift and Rotate ](https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate)
* Arithmetic shift
`sal` `sar` ，分別代表 shift arithmetic left 、 shift arithmetic right 。
語法:`sal dest,CL` `sar dest,CL`，把 dest 算數左/右移 CL 個 bit ，特性是最後一個被移走的 bit 會在 carry flag 當中。
* Logical shift
`shl` `shr` ，分別代表shift logical left 、 shift logical right 。
語法:`sal dest,CL` `sar dest,CL`，把 dest 邏輯左/右移 CL 個 bit ，特性與算術位移相同，最後一個被移走的 bit 會在 carry flag 當中。
* Double Precision shift
`shld` `shrd`，代表double-precision left shifts 與 double-precision right shifts 。
語法:`shld dest, src, cnt` , `shrd dest, src, cnt` 。 src 與 cnt 可適用於 16- or 32-bit register value 。在 64 bits的環境下也支援 64-bit register vale 。 其cnt 可以是 immediate byte value 或是 CL register 。 而src 限定要是 register ， dest 則可以是 register ，或是 memory location 。
##### ARMv8架構 (Aarch32/Aarch64)
參考[ ARM Compiler toolchain Assembler Reference ](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489g/Cjacbgca.html)
* Arithmetic shift
`ASR`
* Logical shift
`LSR` `LSL`
可以發現在算術位移並沒有左移這個指令，推測是因為算術左移其實是和邏輯左移作的動作相同，所以沒有必要再特地創造另一個 instructin 。
:::info
TODO: 參照 [ARM-Assembly: Arithmetic Shift / Logical Shift](https://stackoverflow.com/questions/14565444/arm-assembly-arithmetic-shift-logical-shift) 以及討論中提到的材料，用圖和案例解說
:notes: jserv
:::
而以上三者的功效則與 X86_64 相似，都會把最後一個移走的 bit 存進carry當中。
#### 同樣的 shift operator (<< , >>)在不同架構的差異
除了上面提到的在不同架構， shift 有不同的 assembly 指令外，同樣的 << operator , 在不同架構也會有差異。參考[ Visual C++ Team Blog ](https://blogs.msdn.microsoft.com/vcblog/2012/10/25/hello-arm-exploring-undefined-unspecified-and-implementation-defined-behavior-in-c/)。
在 ARM 架構上， shift operators 會將 256 bits 視為一個 pattern space 。意思就是 shift 每 256 bits 才會 "wraps around" (每 shift 256 bits 會 repeat 的意思)。
在 X86 和 X64 compile ，若是 shift 32-bit 的 operand ，兩者的行為會相同，都是每 32 bits wraps around 一次。但如果是 shift 64-bit 的 operand ，因為X64有支援 64-bit 的instruction,所以 compiler 會去 emits 這個 instruction 。但在 X86 中，由於不支援 64-bit instruction , 所以會去 emits 一個 small software routine,這個 routine 與 ARM 相同， 都是 256 bits 為一個 pattern space 。因此行為也與 ARM 較相似。
>emits 在原文中的用法是 emit the instruction 與 emit the routine , 因此我猜測是與 call 相近的意思 , 但怕翻譯不精準所以採用原文。
>( [emit](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/emit) (vt) 發出，射出，散發)
>
>另外推測在 X86 中，若是 shift 64-bit 的 operand ，效能會比在 X64 慢，因為在文中說到 X86 會去 emit 另外的 software routine .而 X64 只是去做內建 instruction 而已。但礙於手邊沒有那麼多系統，因此先不做效能比較。
>[name=rex662624][color=#662624]
* Widths of the pattern spaces on each architecture
可以看出 shift 32-bit 的 data ，X86 與 X64 相同， 64-bit 則是 X86 與ARM 相同。
| Variable size | ARM | x86 | x64 |
| ---| --- | ---| --- |
|32|256|32|32|
|64|256|256|64|
* Given a 32-bit integer with a value of 1
以下是對用 32-bit integer ,儲存的值為1 ，將之 shift 不同位所得到結果。(取自於[ Visual C++ Team Blog ](https://blogs.msdn.microsoft.com/vcblog/2012/10/25/hello-arm-exploring-undefined-unspecified-and-implementation-defined-behavior-in-c/)。)
可以發現 X86 與 X64 果真行為相同，每只要將 Shift amount % 32 ，就是他應該要 shift 的位數。而ARM 32~128 bits 的欄位都為0，因為他是 256 bits 才一個循環 ，所以 shift 32 bits 雖然還沒到 256 bits ，但由於是用 32-bit int 來儲存 ，所以無法存 2^32 而變成 0。
| Shift amount | ARM | x86 | x64 |
| ---| --- | ---| --- |
| 0 | 1 | 1 | 1 |
| 16 | 32768~註~ | 32768~註~ | 32768~註~ |
| 32 | 0 | 1 | 1 |
| 48 | 0 | 32768~註~ | 32768~註~ |
| 64 | 0 | 1 | 1 |
| 96 | 0 | 1 | 1 |
| 128 | 0 | 1 | 1 |
| 256 | 1 | 1 | 1 |
* Given a 64-bit integer with a value of 1:
以下是對用 64-bit integer ,儲存的值為1 ，將之 shift 不同位所得到結果。可以看到這次 X86 與 ARM 行為相同，都是 256-bit 一個循環，在shift 256 bits 後就會回到 1 ，因為 256%256=0 ，等同於 shift 0 bit
| Shift amount | ARM | x86 | x64 |
| ---| --- | ---| --- |
| 0 | 1 | 1 | 1 |
| 16 | 32768~註~ | 32768~註~ | 32768~註~ |
| 32 | 4294967296 | 4294967296 | 4294967296 |
| 48 | 2^48 | 2^48 | 2^48 |
| 64 | 0 | 0 | 1 |
| 96 | 0 | 0 | 4294967296 |
| 128 | 0 | 0 | 1 |
| 256 | 1 | 1 | 1 |
>上面兩個表格，值有"註"的欄位，應為作者誤植。因為2^16應該是 65536 而非 32768。
>[name=rex662624][color=#662624]
## [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)心得與啟發
看了交大學長的這篇心得分享後，佩服之餘同時也覺得有點惶恐，因為裡面說到的"資工系的學生不會寫程式"，不禁讓我反思，我們在學校學的種種知識，究竟會不會跟產業脫節，又或者更準確的說，我們是否能像作者一樣做出這種真的能賣出銷售的產品，把在學校所學的知識應用到市場層面。
而上了三周本學期的這堂課後，我也了解了自己在實作上的不足，上課的許多範例，與分派的許多回家作業，都是與業界息息相關。而我在學習的過程中，與看到這篇文章的作者，更了解到了自己的渺小，而我也學到了，在學習的路上要保持著永遠不滿足的心態，才能越來越進步。
作者找到了兩個志同道合的好友參與這項專案，用三人團隊做出了這個自動飲料機。而貫通整篇文章的中心思想就是—遇到困難仍然勇往直前。許多不同領域的學生要做到整合，勢必資訊領域的學生也要懂機械，機械領域的學生也要略知資訊，才能知道甚麼可行，什麼不可行。因此製作過程中一定會遇到許多困難，而支撐他們的，是靠對這件事的熱情，與心中的夢想。
最後，這件發明也因為作者去當兵，乏於維護而無法送進飲料店。但我覺得他們也沒有失敗。或者說，花時間去提升自己，增強自己的競爭力，不管市場採不採納，永遠稱不上是失敗。因為就算沒有成功打入市場，他們也贏得了經驗。
這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少(節錄自文章中)。我認為不僅僅是指他們做專案的過程付出很多，光是有個夢想，敢開始去接專案或發明東西，我認為就是跨出了一大步，這也是現在大部分的學生都沒有的。而我們這些只有課內科目要學習的學生，就更沒有理由偷懶了。畢竟人不付出犧牲，就得不到任何回報，一棵樹要長得更高，接受更多的光明，那麼它的根就必須更深入黑暗。
Sign in with Wallet
Connect another wallet