# 2018q1 Homework2 (assessment)
contributed by <`ujiet`>

### 第 1 週第 2 題：

:::success
給定 B 為 2 的某次方 (power of 2)，那麼是否 `A % B` 等價於 `(A & (B - 1))`?
`(a)` 是
`(b)` 否

延伸問題:
- 為什麼？
- 舉出類似的案例並解釋
:::

- 想法：已知在二進位制裡面，當一個數每向右 shift 一個 bit 時，其值相當於除以 2 。
- 因此，當 $A$ 除以 $2^n$ 時，會相當於將 A 向右 shift n 個 bit。
- 而當 $A\ mod\ 2^n$ 時，會相當於將 A 的最右邊 n 個 bit。

e.g.
A = 10010111 = 151, B = 00010000 = 16

A % B = 151 % 16 = 7 = 0111 (A 的最右邊 4 個 bit)

- 實務上可經由 mask 來得到，理論上若 n = 4 ，將 A 與 00001111 做 and 運算，即可得 A % B ， 而所需的 mask，即 00001111 ，可由 (B - 1) 得到。
- 依此類推，由於 $n \in N$ 時皆成立，故 `A % B` 等價於 `(A & (B - 1))`。

- [類似案例 1 - 快速將一個數乗以 7](https://www.geeksforgeeks.org/efficient-way-to-multiply-with-7/)

#include <stdio.h>

int multiplyBySeven(unsigned int n)
{ 
	/* Note the inner bracket here. This is needed 
	because precedence of '-' operator is higher 
	than '<<' */
	return ((n<<3) - n);
}

- 原理：因為 7n = 8n - n，故運用 shift 左移 3 bits 快速得到 8n 後再減去一個 n 即可得。

[類似案例 2 - Swap two nibbles in a byte (nibble 為 4 bits 的區塊)](https://www.geeksforgeeks.org/swap-two-nibbles-byte/)

#include <stdio.h>

unsigned char swapNibbles(unsigned char x)
{
	return ( (x & 0x0F)<<4 | (x & 0xF0)>>4 );
}

- 原理： 0x0F = 00001111, 0xF0 = 11110000
- (x & 0x0F) 得到 x 的右邊 4 個 bit，用 <<4 移到左邊，(x & 0xF0) 同理得左邊 4 bit。
- 將上述兩個數做 or 運算即可完成交換。

---
### 第 2 週第 3 題：
:::success
考慮到某些實數的二進位表示形式如同 $0.yyyyy...$ 這樣的無限循環小數，其中 $y$ 是個 $k$ 位的二進位序列，例如 $\frac{1}{3}$ 的二進位表示為 $0.01010101...$ (y = `01`)，而 $\frac{1}{5}$ 的二進位表示為 $0.001100110011...$ (y = `0011`)，考慮到以下 y 值，求出對應的十進位分數值。
- y = `010011` => $\frac{19}{X1}$
- y = `101` => $\frac{5}{X2}$
- y = `0110` => $\frac{2}{X3}$
:::
- 想法：這種無限循環小數通常都有規則可循，先觀察實際例子看看是否能找出公式。
- 先看第一個例子，已知 $y = 010011$，則 $k = 6$，且二進位表示式 => $0.010011010011...$
- 令欲求的實數為 $x$ ，先試試看將 $x$ 從二進位轉換成十進位的表示法
=> $x = (2^{-2}+2^{-5}+2^{-6})+(2^{-8}+2^{-11}+2^{-12})+...$
=> $\ \ =(2^{-2}+2^{-5}+2^{-6})(1+2^{-6}+2^{-12}+...)$
=> $\ \ =(0.y)(\cfrac{1}{1-2^{-6}}) = (0.y)(\cfrac{1}{1-2^{-k}})$
- 到此已經求出公式，代入 $y$ 和 $k$ ，即可得出答案。將第一題的已知條件代入，得到
=> $x = (\cfrac{1}{4}+\cfrac{1}{32}+\cfrac{1}{64})(\cfrac{1}{1-\cfrac{1}{64}})$
=> $\ \ = (\cfrac{16}{64}+\cfrac{2}{64}+\cfrac{1}{64})(\cfrac{64}{63}) = \cfrac{19}{63}，\therefore X1 = 63$
- 注意最後一個式子，兩個括號裡的 $64$ 消掉了，這顯然不是巧合，再看下一個例子。
- 已知 $y = 101$，$k = 3$，代入公式得到
=> $x = (2^{-1}+2^{-3})(\cfrac{1}{1-2^{-3}})$
=> $\ \ =(\cfrac{1}{2}+\cfrac{1}{8})(\cfrac{1}{1-\cfrac{1}{8}}) = \cfrac{5}{7}，\therefore X2=7$
- 觀察得知，不管是 $X1$ 還是 $X2$，其值都是他們的 $2^{k}-1$，照這個邏輯則 $X3$ 理應是 $2^{4}-1 = 15$ ，但**結果卻是錯誤的**。
- 第三個例子， $y = 0110$，$k = 4$，代入公式得到
=> $x = (2^{-2}+2^{-3})(\cfrac{1}{1-2^{-4}})$
=> $\ \ =(\cfrac{1}{4}+\cfrac{1}{8})(\cfrac{1}{1-\cfrac{1}{16}})=(\cfrac{4+2}{16})(\cfrac{16}{15}) = \cfrac{6}{15}=\cfrac{2}{5}，\therefore X3=5$
- 上述錯誤的原因在於被約分了，所以 $X_n=2^{k}-1$ 只能在將 $0.y$ 通分到分母為 $2^k$ 後的分子與 $2^{k}-1$ 互質的情況才能使用。
- 又其實 $0.y$ 通分後的分子就是 $y$ 的值，因為 $0.y$ 左移 $k$ 個 bit 後就是 $y$ ，這個動作其實就相當於將 $y$ 乗上 $2^k$ ，看下面的例子可以更明瞭。
>e.g.
>
>$y = 010011 = 2^4+2^1+2^0$
>$0.y = 0.010011 = 2^{-2}+2^{-5}+2^{-6}=(2^{-6})(2^4+2^1+2^0)=\cfrac{2^4+2^1+2^0}{2^6}=\cfrac{y}{2^k}$

- 又 $k=\cfrac{2^k}{2^k-1}$，因此，公式可以改寫如下
$$x = \cfrac{y}{2^k-1}$$
---
### 第 3 週第 1 題：
:::success
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz)，假設 double 為 32-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式，請補上對應數值，使其得以運作：

#include <stdint.h>

/* A union allowing us to convert between a double and two 32-bit integers.
 * Little-endian representation
 */
typedef union {
    double value;
    struct {
        uint32_t lsw;
        uint32_t msw;
    } parts;
} ieee_double_shape_type;

/* Set a double from two 32 bit ints.  */
#define INSERT_WORDS(d, ix0, ix1)       \
    do {                                \
        ieee_double_shape_type iw_u = { \
            .parts.msw = ix0,           \
            .parts.lsw = ix1,           \
        };                              \
        (d) = iw_u.value;               \
    } while (0)

/* Get two 32 bit ints from a double.  */
#define EXTRACT_WORDS(ix0, ix1, d)   \
    do {                             \
        ieee_double_shape_type ew_u; \
        ew_u.value = (d);            \
        (ix0) = ew_u.parts.msw;      \
        (ix1) = ew_u.parts.lsw;      \
    } while (0)

static const double one = 1.0, tiny = 1.0e-300;

double ieee754_sqrt(double x)
{
    double z;
    int32_t sign = 0x80000000;
    uint32_t r, t1, s1, ix1, q1;
    int32_t ix0, s0, q, m, t, i;

    EXTRACT_WORDS(ix0, ix1, x);

    /* take care of INF and NaN */
    if ((ix0 & KK1) == KK2) {
        /* sqrt(NaN) = NaN, sqrt(+INF) = +INF, sqrt(-INF) = sNaN */
        return x * x + x;
    }
    /* take care of zero */
    if (ix0 <= 0) {
        if (((ix0 & (~sign)) | ix1) == 0)
            return x; /* sqrt(+-0) = +-0 */
        if (ix0 < 0)
            return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
    }
    /* normalize x */
    m = (ix0 >> 20);
    if (m == 0) { /* subnormal x */
        while (ix0 == 0) {
            m -= 21;
            ix0 |= (ix1 >> 11);
            ix1 <<= 21;
        }
        for (i = 0; (ix0 & 0x00100000) == 0; i++)
            ix0 <<= 1;
        m -= i - 1;
        ix0 |= (ix1 >> (32 - i));
        ix1 <<= i;
    }
    m -= KK3; /* unbias exponent */
    ix0 = (ix0 & 0x000fffff) | 0x00100000;
    if (m & 1) { /* odd m, double x to make it even */
        ix0 += ix0 + ((ix1 & sign) >> 31);
        ix1 += ix1;
    }
    m >>= 1; /* m = [m/2] */

    /* generate sqrt(x) bit by bit */
    ix0 += ix0 + ((ix1 & sign) >> 31);
    ix1 += ix1;
    q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
    r = 0x00200000;       /* r = moving bit from right to left */

    while (r != 0) {
        t = s0 + r;
        if (t <= ix0) {
            s0 = t + r;
            ix0 -= t;
            q += r;
        }
        ix0 += ix0 + ((ix1 & sign) >> 31);
        ix1 += ix1;
        r >>= 1;
    }

    r = sign;
    while (r != 0) {
        t1 = s1 + r;
        t = s0;
        if ((t < ix0) || ((t == ix0) && (t1 <= ix1))) {
            s1 = t1 + r;
            if (((t1 & sign) == sign) && (s1 & sign) == 0)
                s0 += 1;
            ix0 -= t;
            if (ix1 < t1)
                ix0 -= 1;
            ix1 -= t1;
            q1 += r;
        }
        ix0 += ix0 + ((ix1 & sign) >> 31);
        ix1 += ix1;
        r >>= 1;
    }

    /* use floating add to find out rounding direction */
    if ((ix0 | ix1) != 0) {
        z = one - tiny; /* trigger inexact flag */
        if (z >= one) {
            z = one + tiny;
            if (q1 == (uint32_t) 0xffffffff) {
                q1 = 0;
                q += 1;
            } else if (z > one) {
                if (q1 == (uint32_t) KK4)
                    q += 1;
                q1 += 2;
            } else
                q1 += (q1 & 1);
        }
    }
    ix0 = (q >> 1) + 0x3fe00000;
    ix1 = q1 >> 1;
    if ((q & 1) == 1)
        ix1 |= sign;
    ix0 += (m << KK5);
    INSERT_WORDS(z, ix0, ix1);
    return z;
}

延伸題目: 解釋上述程式碼何以運作，並且改為 float (單精度) 版本，注意應該用更短的程式碼來實作
:::

- 想法：有點複雜，將程式碼分段拆解看看。

/* A union allowing us to convert between a double and two 32-bit integers.
 * Little-endian representation
 */
typedef union {
    double value;
    struct {
        uint32_t lsw;
        uint32_t msw;
    } parts;
} ieee_double_shape_type;

- 在 IEEE 754 中 double 是 64-bit 的。此段程式碼的目的為設定一個新的符合 IEEE double 的資料型別，type 名為 ieee_double_shape_type。
- union 與 struct 非常相像，差別在於 union 在記憶體內所保有的空間僅能存放一個 field (欄位)的資料，適用於某種資料可能有兩種以上不同型態的情況，但同時間只能使用其中一個 field。
- 因此，對 ieee_double_shape_type 這個資料型別來說，他可能是一個 32-bit 的預設 double 且值為 value，也可能是一個名為 parts 的結構體，裡面存放有兩個無號 32-bit 整數 --- lsw 和 msw (least & most significant word)，而此結構體就是 IEEE double。
- 所以 struct 裡的記憶體配置長得像 $$|\ lsw\ |\ msw\ |$$ $$or$$ $$|\ \ \ \ \ value\ \ \ \ \ |$$ 每個欄位各 32 bits，此為 little-endian 表示法。但實際的數字應該是長成像 $$|\ msw\ \ lsw\ |$$

/* Set a double from two 32 bit ints.  */
#define INSERT_WORDS(d, ix0, ix1)       \
    do {                                \
        ieee_double_shape_type iw_u = { \
            .parts.msw = ix0,           \
            .parts.lsw = ix1,           \
        };                              \
        (d) = iw_u.value;               \
    } while (0)

/* Get two 32 bit ints from a double.  */
#define EXTRACT_WORDS(ix0, ix1, d)   \
    do {                             \
        ieee_double_shape_type ew_u; \
        ew_u.value = (d);            \
        (ix0) = ew_u.parts.msw;      \
        (ix1) = ew_u.parts.lsw;      \
    } while (0)

static const double one = 1.0, tiny = 1.0e-300;

- 定義了 INSERT_WORDS 和 EXTRACT_WORDS 函數的行為，並設定了兩個常數。
:::danger
具體作用為何呢？可否舉出 sqrt 以外，其他浮點數也用得到的案例嗎？
:notes: jserv
:::
>- INSERT_WORDS 相當於將 32-bit 的 ix0 和 ix1 分別放在 msw 和 lsw 的記憶體位置，並將兩者合起來，看成是一個新的 64-bit 數 d。EXTRACT_WORDS 則是相反，但原本的數 d 只有 32-bit。

double ieee754_sqrt(double x) { 
    double z; 
    int32_t sign = 0x80000000; 
    uint32_t r, t1, s1, ix1, q1; 
    int32_t ix0, s0, q, m, t, i; 
    
    EXTRACT_WORDS(ix0, ix1, x);

- 宣告了 sign = 1000 0000 ... 0000，為 32-bit 有號整數。
- 宣告了一些需要的變數，值得注意的是 ix0 為宣告為有號而 ix1 為無號。原因應該是 ix0 為 value 的 msw 部分，所以需要保留最前面表示正負號的位元。
- 對輸入的 x 做 EXTRACT_WORDS，相當於把 x 分為 ix0 和 ix1 兩個部分。
---
- 若測試時印不出來，可能需要引入 inttypes.h 標頭檔
- printf 的範例如下

printf("ix0: %" PRId32 "\n", ix0);
printf("ix1: %" PRIu32 "\n", ix1);

---
- [Approved Verbs for Windows PowerShell Commands](https://msdn.microsoft.com/en-us/library/ms714428.aspx)
- Windows PowerShell Commands 所使用的動詞列表，有助提昇 git commit 描述之精準度。
- [C 語言的 2016](http://www.infoq.com/cn/articles/c-language-2016)
- 一些有關 C 語言的使用心得。