# 2018q1 Homework2
contributed by <`YuanHaoHo`>

## 第二周_測驗題1
題目如下:
請完成下方程式碼，依循 IEEE 754 單精度規範，輸出 2x的浮點數表達法，而且考慮兩種狀況：

- 當 x 過小的時候，回傳 0.0 0.0
- 當 x 過大的時候，回傳 +∞ +∞

注意：這裡假設 `u2f` 函式返回的浮點數值與其無號數輸入有著相同的位數，也就是至少 32-bit

程式如下:

#include <math.h>
static inline float u2f(unsigned int x){retrun *(float *) &x;}

float exp2_fp(int x){
    unsigned int exp /* exponent */, frac /* fracton */;
    /* too small */
    if (x < 2 - pow(2, Y0)) - 23) {
        exp = 0;
        frac = 0;
    /* denormalized */
    }else if (x < Y1 - pow(2, Y2)) {
        exp = 0;
        frac = 1 << (unsigned) (x - (2 - pow(2, Y3)- Y4));
    /* normalized */
    }else if (x < pow(2, Y5)) {
        exp = pow(2, Y6) - 1 + x;
        frac = 0;
    /* too large */
    }else{
    exp = Y7;
    frac = 0;
    }
    /* pack exp andfrac int 32 bits */
    return u2f((unsigned) exp << 23 | frac);
}

尋找`Y0~Y7`為多少?
### 解題路程、必備知識與解法
#### 解題路程
鄙人我是第二周才加選近來這堂課的，所以這題就是我在這堂課小考的第一題，當時在略有所聞的狀況下被同學拉進來，其實心理建設還沒架好，這造就我在第一次看到這類奇妙題目的心靈有點受傷，我記得考30分鐘但我這題就花超過30分鐘，實在是很嗨。
回家後我上網找尋有沒有類似的題目，很慶幸在 [stack overflow](https://stackoverflow.com/questions/29710514/normalized-and-denormalized-confusion-in-c) 上找到了。於是看著答案思索，結果怎麼越寫越奇怪，在重填考卷後怎麼還是有錯，後來發現原來是 unsigend 惹的禍，再次重想重填後才找到對的答案，可說是一路坎坷。
#### 解題必備知識
>中英文間記得空白
>[name=課程助教][color=red]
> > 好的!已更改!
> > [name=YuanHaoHo][color=blue]

這題主要將所輸入不同的 x 值帶入2的次方數，並將2的次方數用 **IEEE754** 這個規範下的 floating piont 表示法將其呈現。由上圖可知，在 32bits 內的 MSB 是 sigened bit ，剩下有 8bits 來表示 exponential ，剩下的 mantissa 就是 fraction 的部分，共有 23bits 。

2小於0的次方數，可以用 shift 來表示，例如：
> 1/2 -> 0.1
> 1/4 -> 0.01
> 1/8 -> 0.001
>
由上可知每當向右 shift 一位是除以2，向左一位為乘2，則在 mantissa 的表示法可以用` 1 << n`來表示2的小數點位子，而`n`為次方數。

但因為這題題目，很奸詐的將 exponenial 設計成 unsigened ，這造成我在思考上一直打結，其實這題的想法更為簡單，因為 exponential 這部分都是正的，所以如果輸入的`x`是負的且小於 -127，就只會呈現在 mantissa 上，也就是說再 eponential 的準位自動往上拉了 127，所以要自動扣掉，如此設想變不會有問題。
#### 解題方法

 /* too small */
    if (x < 2 - pow(2, Y0)) - 23) {
        exp = 0;
        frac = 0;

先看`Y0`，這個部份主要是當輸入的`x`值太小時，在呈現上都是`0`的狀況，判斷式內主要是**考慮到unsigned的準位改變**，還有**小於mantissa那23bit**之後，所以`x < 2 - pow(2, Y0)) - 23`才會成立，而此時的`Y0`就是`7`。

/* denormalized */
    }else if (x < Y1 - pow(2, Y2)) {
        exp = 0;
        frac = 1 << (unsigned) (x - (2 - pow(2, Y3)- Y4));

再來看`Y1~Y4`，這個部份的主要是再敘述當`x`太小只能用mantissa的部份來表示，所以`x`值的範圍應該在`-127-23 ~ -127`之間，由此推斷`Y1`為`1`，`Y2`為`7`；而`Y3~4`的部份可以解釋成：因為我的`exp`在此部份為`0`，所以**只要考慮到fraction的部份**，由上述推斷可知，此部份的範圍就是在`-127-23 ~ -127`，將輸入的`x`值**扣掉原本的準位改變**後，可以得到`1`從LSB往右移多少，也因此`Y3`為`7`，`Y4`為`23`。

/* normalized */
    }else if (x < pow(2, Y5)) {
        exp = pow(2, Y6) - 1 + x;
        frac = 0;

這個部份則比較好推斷，數值最大的狀況就是把`exp`填滿，但在考慮負數的情況下，`Y5`只能為`7`，而`Y6`是考慮到準位改變（unsigned）的問題所以要幫忙加上`127`，因此`Y6`為`7`。

 /* too large */
    }else{
    exp = Y7;
    frac = 0;
    }

最後一個部份就是輸入`x`值太大的狀況，此刻`Y7`就是最大值`0xFF`。

## 第一周_測驗題1
題目如下：

#include <stdlib.h>
int isMultN(unsigned int n) {
    int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */
    
    if (n == 0)    // return true if difference is 0.
        return 1;
    if (n == 1)    // return false if the difference is not 0.
        return 0;
    
    while (n) {
        if (n & 1)   // odd bit is SET, increment odd_C
            odd_c++;
        n >>= 1; 
    
        if (n & 1)   // even bit is SET, increment even_c
            even_c++;
        n = n >> 1;
    }
    
    /* Recursive call till you get 0/1 */
    return(isMultN(abs(odd_c - even_c)));
}

其作用為檢查輸入整數是否為 `N` 的倍數，那麼 `N` 為多少？

### 解題必備知識與解法
#### 解題必備知識
這類題目屬於 bitwise 類型的，而這要解這題必須要知道以下兩種運算方法：

1. n & 1
2. n >>= 1 or n = n >> 1

第1項就是比較 LSB 這項是不是1，如果是1則輸出1，如果是0則輸出0；第2項是將 `n` 進行 shift 的動作且每做完一次就更新。

而這題第2件必需要知道的事情就是在2進位裡，各個倍數所擁有的特徵，例如三的倍數，我們可以由以下列舉法推得：
> 00000011 -> 3
> 00000110 -> 6
> 00001001 -> 9
> 00001100 -> 12
> 00001111 -> 15
> 00010010 -> 18
>
由以上規律可以推得，奇數項為1的bits數恆等於偶數項為1的bits數，也因此可以由奇偶數項為1項的差來推測是否為3的倍數。

#### 解題方法
這題主要是因為為遞迴判斷式，所以可以由 function 中，慢慢推敲得到答案，再解題的路途中，如果用看的看不出來，其實可以帶二進位數字，以下我就帶 0110 和 1001 進入，去推敲看看是否可以得到答案。
稍稍改一下 code 比較容易懂：

#include <stdlib.h>
int isMultN(unsigned int n) {
 int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */

 if (n == 0){ // return true if difference is 0.
 printf("Yes, It's N Mul.\\n");
 return   1;
}
 if (n == 1){ // return false if the difference is not 0.
 printf("No, it isn't N Mul.\\n");
 return   0;
}

 while (n) {
 if (n & 1) // odd bit is SET, increment odd_C
    odd_c++;
 printf("odd_c : %d , n : %p \\n",odd_c , n);
 n >>=   1;

 if (n & 1) // even bit is SET, increment even_c
    even_c++;
 printf("even_c : %d , n : %p \\n",even_c , n);
 n = n >>   1;
}

 /* Recursive call till you get 0/1 */
 return(isMultN(abs(odd_c - even_c)));
}

int main(){
 unsigned int n = <帶入值>; // 0110
 isMultN(n);
 return 0 ;
}

在`n = 6` ， 0110~(2)~ 帶入後，可得以下：

odd_c : 0 , n : 0x6
even_c : 1 , n : 0x3
odd_c : 1 , n : 0x1
even_c : 1 , n : (nil)
Yes, It's N Mul.

做成表格比較好懂：

| Shift: n | 0x6 | 0x3 | 0x1 | nil |
| :------: | :--: | :--: | :--: | :--: |
| 2's | 0110 | 0011 | 0001 | 0000 |
| odd_c | 0 | X | 1 | 1 |
| even_c | 0 | 1 | 1 | 1 |

在 `n = 9` ， 1001~(2)~ 帶入後，可得以下：

odd_c : 1 , n : 0x9
even_c : 0 , n : 0x4
odd_c : 1 , n : 0x2
even_c : 1 , n : 0x1
Yes, It's N Mul.

做成表格比較好懂：

| Shift: n | 0x9 | 0x4 | 0x2 | 0x1 |
|:-------: | :--: | :--: | :--: | :--: |
| 2's | 1001 | 0100 | 0010 | 0001 |
| odd_c | 1 | 1 | 1 | 1 |
| even_c | 0 | 0 | 0 | 1 |
當`odd_c`和`even_c`的數字相等時，會`return 1`，代表以上兩者皆表示為其為`N`的倍數，由此可推論`9`和`6`的公因數為`3`，因此此題`N`為`3`。
#### 延伸討論
既然已經知道如何判斷二進位數是否為3的倍數後，我們來討論一下如何進行判斷是否為5的倍數的方法。
以下式我再 PTT 上找到的方法：
1. 把數字右移兩位 - 原數字後面兩位.... (如果這個結果是5的倍數..則代表原數字是五的倍數.)
2. 當然你為了要檢查(1)的結果是不是5的倍數...還要再回(1)再做一次檢查 (直到後面的兩位數字大於被右兩位的數字值)..

> 10100 => 101-00=101=>1-01=0=>5的倍數
> 1011111=>10111-11=10100=>101-00=101=>1-01=0=>5的倍數
> 1000111=>10001-11=1110=>11-10=1=>0-1 < 0 =>所以不是5的倍數

依造以上想法，我們可以建構出以下遞迴式：

#include <stdlib.h>
int isMultN(unsigned int n) {
 if (n == 0){ // return true if difference is 0.
 printf("Yes, It's N Mul.\\n");
 return 1;
 }

 if (n == 1){ // return false if the difference is not 0.
 printf("No, it isn't N Mul.\\n");
 return 0;
 }

 /* Recursive call till you get 0/1 */
 return(isMultN((n >> 2) - (n & 0x3)));
}

int main(){
 unsigned int n = <輸入數字> ; 
 isMultN(n);
 return 0;
}

Reference ： [從二進位判斷數字是否被5整除](https://www.ptt.cc/bbs/Prob_Solve/M.1223098109.A.99F.html)

## 第三周_測驗題2
題目如下：
考慮到下方函式 `shift_right_arith` 和 `shift_right_logical` 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，而移位量 `k` 的有效範圍在 0 到 `w - 1`。

#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;
}

### 解題路程、必備知識與解法
#### 解題路程
我覺得這題的難度不高，但會選擇這一題是因為經歷這些小考，這是我唯一全對的，讓我被感親切XD。好拉，其實是蠻可憐的，寫這麼多題這題才唯一全對QQ，但確實對 bitwise 這類東西感受比較深刻，掌握度也因此提高了不少。

#### 必備知識
好拉不喇賽，來討論這題所需的必備知識，從題目來看，首先要搞清楚的就是算術右移與邏輯右移之間的差別了，算術右移主要的特色就是當右移發生時，所有數一次右移，尾部丟失，符號位右移後，在最高位補上複製的原符號位；邏輯右移則比較簡單，當其發生時，就最高位補零，尾部丟失。
再來就是從題目上可以得知，`sizeof(int) * 8` 為整數型態 `int` 的位元數 `w`，而整數型態的位元數為32bits，因此`w`為32，而`k`的有效範圍為0 到 `w - 1`，因此`k`的範圍在`0 ~ 31`之間。
#### 解題方法
先討論運算右移的部份：

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;
}

* 因為`w`的大小為32，而`sizeof(int)`的大小為4，所以如果`4 << P1 `為32的話，則`P1`為3。
* 要解`P2`要先了解`mask`這個變數在做什麼，往下看會看到`xsrl P3 mask`好像是運用`mask`做什麼運算，且是在`x`屬於負數的情況下才會用到，如此先假設`mask`的工作就是做向右位移`k`個，那麼利用`-1 << (P2)`可以至做出什麼？ `-1`二位進位表示為32個`1`，因此可以得到一個32bits的二進位，前面`k`個為1，後面`w-k`個為0，因此`P2`是`w-k`。
* 看到這邊應該會明朗一些，趕緊拿出紙筆計算寫一下。假設向右移動5個，且`x`為負數，我們得到的`mask`是`11111000 00000000 00000000 00000000`，用我們先前對於運算右移的概念，會發現很巧合的，我們將前面應該要補1的部份用`mask`補完成了，所以在`xsrl P3 mask`我們設`P3`為`|`，就可以用OR把右移後的和補1銜接上了，感嘆設計這個CODE的大神吧。

再來我們來討論邏輯右移：

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;
}

* 這邊的`P4`和`P1`的解法一樣，接為3。
* `P5`和`P2`的想法也一樣，但些微不同的部份是，我們不必再需要考慮`x`的正負，因此此刻先不決定`P5`的解答，先往下看。
* `P7`的解答有兩個可以選，分別式`mask`和`~mask`，這個的選擇不外乎就是搭配`P6`，如果此時的選擇和`P3`的一樣，會讓補位變成1，這樣的話會與邏輯右移的理念不合，換個角度想，假設`P7`是`~mask`，讓`xsra`去和他做AND，則可以確保右移的部份，且補位為0，因此`P6`的選擇就簡單多了，為`&`。
* 由上面`P6`、`P7`的選擇，可以推得`P5`與`P2`答案一樣的話，所以有的假設都成立且運算正確，答案為`w-k`

### 延伸題目

題目：在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制

#### x86_64：

| 邏輯右移 | 邏輯左移 | 運算右移 | 運算左移 |
| :-----: | :----: | :----: |:-----:|
| shr | shl | sar | sal |

使用範例：
* 邏輯移位

movw   $ff00,%ax        # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256) 
shrw   $3,%ax           # ax=0001.1111.1110.0000 (0x1fe0, signed and unsigned 8160)
                        # (logical shifting unsigned numbers right by 3
                        #   is like integer division by 8)
shlw   $1,%ax           # ax=0011.1111.1100.0000 (0x3fc0, signed and unsigned 16320) 
                        # (logical shifting unsigned numbers left by 1
                        #   is like multiplication by 2)

* 運算移位

movw   $ff00,%ax        # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256)
salw   $2,%ax           # ax=1111.1100.0000.0000 (0xfc00, unsigned 64512, signed -1024)
                        # (arithmetic shifting left by 2 is like multiplication by 4 for
                        #   negative numbers, but has an impact on positives with most
                        #   significant bit set (i.e. set bits shifted out))
sarw   $5,%ax           # ax=1111.1111.1110.0000 (0xffe0, unsigned 65504, signed -32)
                        # (arithmetic shifting right by 5 is like integer division by 32
                        #   for negative numbers)

#### Aarch32/Aarch64 ：

| 邏輯右移 | 邏輯左移 | 運算右移 | 運算左移 |
| :-----: | :----: | :----: |:-----:|
| LSR | LSL | ASR | ASL |

==參考：==
* [X86 Assembly/Shift and Rotate](https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate)
* [ARM-Assembly: Arithmetic Shift / Logical Shift](https://stackoverflow.com/questions/14565444/arm-assembly-arithmetic-shift-logical-shift)
* [raygoah](https://hackmd.io/s/HyCc94IKM)