# 2018q1 Homework3 (assessment)
contributed by <`t5i0m7`>
主要是去重新看前三周的題目，重新做答並找出三題我比較有問題的做討論

## Week 1 : 問題(一)
#### 題目提供的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 1; 
    if (n == 1) 
        return 0;
    
    while (n) { 
        if (n & 1)
            odd_c++;
        n >>= 1; 
        if (n & 1)
            even_c++; 
        n = n >> 1; 
    }
    /* Recursive call till you get 0/1 */ 
    return(isMultN(abs(odd_c - even_c)));
} 
// even bit is SET, increment even_c 
// odd bit is SET, increment odd_C 
// return false if the difference is not 0. // return true if difference is 0.

其題目問此function的isMultN裡的N為多少，也就是在問判斷是否N倍的函式的N為多少因為那時做答時間少，我自己也是一次看到這種判斷倍數的函式，所以在寫的時偏向用感覺猜出答案沒有詳細的去了解或是推導出結果。

#### 判斷奇位個數與偶位個數

while (n) { 
        if (n & 1)
            odd_c++;
        n >>= 1; 
        if (n & 1)
            even_c++; 
        n = n >> 1; 
    }

可以看出這段code兩位兩位抓，每次抓完都做shift，算完後做一次遞迴讓終止條件做判斷，判斷偶位數的個數跟奇位數的各數相差。

#### 終止條件

if (n == 0) return   1;
if (n == 1) return   0;

在一開始做這個測驗有種辦猜測，因為後兩位必須符合上述條件，所以能符合這種規則的二進制的數字也只有3了。但後來看到延伸題目時就有點心虛了，一個延伸題目要解釋為何這個遞回式可行，而另一個則西換改code來達成其它的N的倍數判斷，要回答這兩個問題就必須了解或推出背後的數學式。

在試了很多方式來推導，整理出最後的流程，首先我是先從程式碼來下手，從上述可得知：
* 必須使用遞迴直到終止條件用上
* 轉二進位後每兩位要做一次odd和even個數的判斷
* abs(odd-even)在遞迴一定要用上

綜合以上條件我會先從Input下手，將Input N 轉成二進位來看 :
:::info
N = c0 * 2^0^ + c1 * 2^1^ + c2 * 2^2^ + c3 * 2^3^ . . .
c0 + c2 + c4 + ..... = odd_c
c1 + c3 + c5 + ..... = even_c
:::
而盡然要判斷是否為3的配樹的話，那就直接對N做%3：
(N = c0 * 2^0^ + c1 * 2^1^ + c2 * 2^2^ + c3 * 2^3^ . . . ) % 3
從這裡可以看出來對每項的餘數，若所有細數皆為一的話，則每項的餘數則為1 2 1 2 . . . 1 2這樣一值循環，這樣樓上odd和even的關係式就能用上。
:::info
c0 + c2 + c4 + … = odd_c
c1 + c3 + c5 + … = even_c
=> N % 3 = (odd_c + 2 * even_c) % 3
:::
目前只用到程式碼給的while裡寫的，還差abs(odd - even)沒用上，這條件一定得用上，我已我再將上述等式改寫一下。
:::info
N % 3 = (odd_c - even_c + even_c + 2 * even_c) % 3
==> N % 3 = [ (odd_c - even_c) + 3 * even_c ] % 3
==> N % 3 = (odd_c-even_c) % 3
:::
從上述可得到如程式碼給的遞迴式，而就如同程式碼一樣當odd_c - even_c 為0時為整除，故能被三整除，而我們也可以從上得知整個code背後的原理。

#### 延伸(二)判斷其它倍數
題目要求要用遞迴的code來做判斷倍數，由以上原理我認為對每個不同的變數都要像上面一樣才可推出遞迴的code要如何時做，以7的倍數判斷為例，一開始一樣對N做二進位展開之後去找餘數的規律：
:::info
(N = c0 * 2^0^ + c1 * 2^1^ + c2 * 2^2^ + c3 * 2^3^ . . . ) % 7
係數全用1代可得餘數的規律
=>1 2 4 1 2 4 . . . . 1 2 4
:::
因此我會用三個變數來存one_c tow_c three_c來存，並藉此來推出遞迴的終止條件，根據上述等式再加上剛剛的變數可將等式改為：
:::info
N % 7 = (one_c + two_c * 2 + three_c * 4) % 7
從這裡要開始湊出終止條件one_c , tow_c , three_c的關係，而我就像剛剛將一項能被7整除
=> N % 7 =[ ( one_c - three_c) + (two_c - three_c)* 2 ] % 7
=> N % 7 =[ ( one_c - two_c) + (two_c - three_c)* 3] % 7
:::
從上面的等式可以知道要將 ( one_c - two_c) + (two_c - three_c)* 3做遞迴直到( one_c - two_c) + (two_c - three_c)* 3為零。
其code可改寫：

#include <stdlib.h> 
int isMultSeven(unsigned int n) 
{ 
    int one_c = 0 ,two_c = 0 ,three_c = 0;
    /* variables to count odd and even SET bits */
    if (n == 0) 
        return 1; 
    if (n < 7 )
        return 0;
    
    while (n) { 
        if (n & 1)
            one_c++;
        n >>= 1; 
        if (n & 1)
            two_c++; 
        n = n >> 1; 
        if (n & 1)
            three_c++; 
        n = n >> 1; 
    }
    /* Recursive call till you get 0/1 */ 
    return(isMultSeven(abs(( one_c - two_c) + (two_c - three_c)* 3)));
} 

### 第一周總結
基本上題目圍繞在bitwise-operation上，使用bit運算做出來的這些function，基本上不太直覺，腦袋需要轉一下才能了解整段code在幹麻，第一周的課程例看到了蠻多特別的用法，像是一次讀一個word來判斷結尾字元，裡面用到的迪摩根定律來做判斷，整個就比一班一個byte一個byte比還來的有效率多，雖然第一周只是起頭而已但對我來講學到了許多。

## Week 2 : 問題(一)
做這周的練習必須了解何謂IEEE754的表達方式，對於3種case必須深度了解，看題目的code才會比較輕鬆。剛開始對我來講，不好理解的是Normalized和Denormalized的差別，不過在看了CS:APP之後，就了結其中的關係，寫得非常的詳細。

* Normalized number
普通IEEE 754的表達數字，數字沒有過小、過大、或特殊數值。

過小：< ( 2^1-bias^ ) * 2^-f^ <- bias為2^k-1^-1，f為fraction的位數，k為exponent的位數，而一但過小就可用denormalized number來表示。

過大：> ( 2^1-bias^ ) 則進進入special number的範圍

* Denormalized number
一般Denormalized number：介於( 2^1-bias^ ) * 2^-f^ 與 ( 2^1-bias^ ) 之間，當在與正規畫數值做運算是要注意exponent的進位。

零：< ( 2^1-bias^ ) * 2^-f^ 時則 exponent和fraction的位數皆為0而在sign bit可以決定+0或-0

* special number
有像是正負無窮大漢NaN之類的表示，當exponent全為一則此表示special number，有可分fraction有值=>NaN or Inf,sign bit =>決定正負

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

float exp2_fp(int x) {
    unsigned int exp /* exponent */, frac /* fraction */;

    /* too small */
    if (x < 2 - pow(2, Y0) - 23) {
        exp = 0;
        frac = 0;
    /* denormalize */
    } 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 and frac into 32 bits */
    return u2f((unsigned) exp << 23 | frac);
}

而這個題目主要是要理解這段code，其目的是要將2^k轉成IEEE754得形式，並要補完這段code，順著註解可以將上述IEEE754三種number的表示法來瞭解這段code，此段code依註解分為四個部分來做剛剛正規化、非正規化等等的判斷，從判斷太小，而後非正規再來正規數值，到最後太大的判斷，從這樣的順序可以一步一步得到要得值。

* too small => n < ( 2^1-bias^ ) * 2^-f^ => 可得最小exponent為2-2^7=126而fraction的指數部分為也就是最後一位，Y0為7
* denormalized => 介於( 2^1-bias^ ) * 2^-f^ 與 ( 2^1-bias^ ) 之間，所以考慮fraction的指數位相對於最小數的指數位 => Y1=2 , Y2=7 , Y3=7 ,Y4=23
* normalized => n < ( 2^1-bias^ )只需考慮到expoent的數值跟一般在做IEEE754算exponent一樣x+bias即可 => Y5=7 , Y6=7
* special case(too large) => exponent全為一 => Y7 = Oxff

### Week2總結
這周花很多時間去了解IEEE754在剛碰到這類的問題時其實非常困惑，以前在上計概時只有遇過normalized的情況，其它的情況在上課時才第一次了解到，原來IEEE754太大或太小時會發生的例外，甚至式specal number的情形，都可以用IEEE754表達，那時我也了解matlab那些特殊數值在code再浮點樹的表示為如何。