# 2018q3 Homework (quiz1)
###### tags: `bauuuu1021`,`BroLeaf`
contributed by <`bauuuu1021`,`BroLeaf`>
[2018q1 第 1 週測驗題](https://hackmd.io/s/rJh9U4Guf)

---

## 測驗 `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 為多少？

:::success
延伸問題:
* 為什麼上述程式碼可運作呢？
* 將 N 改為其他質數再改寫為對應的程式碼，一樣使用遞迴
:::
* 紀錄 input n 的**奇、偶數位為 1** 的有幾個 bit 在odd_c 、 even_c 裡，然後取兩者差的絕對值再遞迴呼叫
* 而兩者的差值要同時也是 N 的倍數、或是 0 才會回傳 true.
* 帶幾個數字 0011、0111、1111 就會馬上知道 N 是 3
* 這是因為 3 可以寫成 0011 而在 3 的倍數上一直加 3 ，odd_c 、 even_c 的差值會有兩種結果出現
* 差值相等 (0011+0011 = 0110)
* 相差為 3n (10101+00011 = 11000)

這種說法雖然直觀，但是不嚴謹，所以我們證明他的推廣
* 詳細的證明：

**證明**
試證：三的倍數，皆為奇偶數位 1 個數差為 0 或 3n 的數
奇數位的 `1` 代表 2^2n^ 也就是 ：1, 4, 16, 64…這些數共同的特色是 3$p_i$+1
偶數位的 `1` 代表 2^2n+1^ 也就是 ：2, 8, 32, 128…這些數共同的特色是 3$q_i$-1

因此可得到，
奇偶數位 `1` 的個數相等時：代表 3(P+Q) 為三的倍數
奇偶數位 `1` 的個數相差3的倍數：代表 3P+3 or 3Q-3皆為三的倍數
p.s. P = Σpi , Q = Σqi
得證假設成立。

:::warning
以電路設計的觀點，檢視上面遞迴程式的實作，倍頻和除頻的電路是否有相似之處？
:notes: jserv
:::

module div2_v2 (
    input      clk,
    input      rst_n,
    output reg o_clk
);
reg cnt;
always@(posedge clk or negedge rst_n) begin
    if (!rst_n)
        cnt <= 0;
    else if (cnt == 1) // 0 ~ 1
        cnt <= 0;
    else
        cnt <= cnt + 1;
end
always@(posedge clk or negedge rst_n) begin
    if (!rst_n)
        o_clk <= 0;
    else if (cnt < 1) // 0 
        o_clk = 0;
    else              // 1
        o_clk = 1;
end
endmodule

* 用 verilog 實作的除 2 的除頻器，第 7 ~ 14 行是一個簡單的計數器， 15 ~ 22 行就是主要的除頻，這段也是主要和題目相似的地方，根據計數器的值，來決定 o_clk 的 output 。

### 將 N 改為其他質數再改寫為對應的程式碼
* 為了能將 N 推廣到更多的數，所以我想了一個能夠一般化的方法
#### 改寫演算法
* 我在計算的過程中發現，只要是某個奇數 N ，在求 N mod 2^m^, 2^m+1^, 2^m+2^ ...所得到的值會不斷變化，且最後一定會形成一個循環。很明顯，當 N 愈大，一次循環的數就愈多，而有可能的值也會變多。
* 只有當 N = 2^m^ - 1 時，可以確定每 m 個 bit 一個循環

|N mod 2^m^|1|2|4|8|16|32|64|128|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|3|1|2|1|2|1|2|1|2|
|5|1|2|4|3|1|2|4|3|
|7|1|2|4|1|2|4|1|2|
|15|1|2|4|8|1|2|4|8|

* 而當要計算某數 A 是不是 N 的倍數時，就把一次讀一個循環的 bit ，再把 mod 過後的值當成加權，個別乘上
* 例如：N = 5 ，就一次讀 4 個 bit (看上表，每 4 個 bit 循環)第一個 bit 乘上 1 、第二個 bit 乘上 2 、第三個 bit 乘上 4 、第四個 bit 乘上 3 ，加總起來後繼續讀下去，全部加總後再把值呼叫遞迴繼續執行，若 A 為 5 的倍數，則最後一定得出 5 或 0。
* 實際判斷一次：判斷 77(1001101)是不是 7 的倍數帶入公式，從最小的 bit 開始， $1\times1+0\times2+1\times4+1\times1+0\times2+0\times4+1\times1 = 7$，所以得到 77 是 7 的倍數。
* 用更直白的話解說就是，把 A 寫成二進位，把每個 bit 所代表的 2 的某次方去 mod N ，把結果加總起來，再重來，直到結果變成 N 或是 < N
* N = 5

int isMult5(unsigned int n) 
{
  int ret = 0;
  if (n == 0 || n == 5)  // return true if the input is 0 or 5
    return 1;
  if (n < 5)		// return false if the input is not 0.
    return 0;
  while (n)
  {
    if (n & 1)	        // first bit, weighted is 1.
      ret++;
    n >>= 1;
    if (n & 1)		// second bit, weighted is 2.
      ret+=2;
    n >>= 1;
    if (n & 1)		// third bit, weighted is 4.
      ret+=4;	
    n >>= 1;
    if (n & 1)		// fourth bit, weighted is 3.
      ret+=3;
    n >>= 1;
    }
    return(isMult5(ret - 5));
}

* 最後之所以要 - 5 是因為避免傳入 6 or 7 導致遞迴不能終止
* N = 7

int isMult7(unsigned int n)
{
    int ret = 0;
    if (n == 0 || n == 7)    // return true if the input is 0 or 7
        return 1;
    if (n < 7)    // return false if the input is not 0.
        return 0;
    while (n)
    {
        if (n & 1)   // first bit, weighted is 1.
            ret++;
        n >>= 1;
        if (n & 1)   // sedcond bit, weighted is 2. 
            ret+=2;
        n >>= 1;
        if (n & 1)
            ret+=4; // third bit, weighted is 4.
        n >>= 1;
    }
    return(isMult7(ret));
}

* 當 N = 2^m^ - 1 時，還有另一個性質，當被帶入的數字作上面提到的加權計算時，其實結果就跟直接對 N 作 and 是一樣的，在這個前提下，直接修改 N = 7 裏面 while 的程式碼，再加上 N = 31 的實作
* N = 7

int isMult7(unsigned int n)
{
    int ret = 0;
    if (n == 0 || n == 7)    // return true if the input is 0 or 7
        return 1;
    if (n < 7)    // return false if the input is not 0.
        return 0;
    while (n)
    {
        ret += n & 7;
        n >>= 3;
    }
    return(isMult7(ret));
}

* N = 31

int isMult31(unsigned int n)
{
    int ret = 0;
    if (n == 0 || n == 0X1F) return 1;
    if (n < 31) return 0;
    while (n)
    {
        ret += n & 0X1F;
        n >>= 5;
    }
    return(isMult31(ret));
}

## 測驗 `2`

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

:::success
延伸問題:
* 為什麼？
* 舉出類似的案例並解釋
:::
* 對任意正整數 x 除以任意正整數 m ，得商為 k 餘數為 r。可寫為 $x=k*m+r$，r 亦可寫為 x%m
* 可將題目的 A 拆成兩項相加：$hi_A$,$lo_A$
* $hi_A$ (k*B) 為 A 中 >= B 部份
* $lo_A$ ( r ) 為 A 中 < B 部份
* 則 A % B = A/B 的餘數 = $lo_A$，即取比 B 小的所有位數
* 假設 B 為 2 的 n 次方，為 1000...0 的形式(n 個 0)；(B-1) 為 111...1 (n 個 1) 形式，`(A & (B - 1))` 即可取得比 B 小的部份

|A|$x_1$|$x_2$|$x_3$|$x_4$|$x_5$|...|...|...|$x_m$|
|---|---|---|---|---|---|---|---|---|---|
| B | | | 1 | 0 | 0 | ... |... | ... | 0 |
| B-1 | | | | 1 | 1 | ... | ... | ... | 1 |
| A%B | | | | $x_4$ | $x_5$ | ... |... | ... |$x_m$ |

---

## 測驗 `3`

在 C 程式中，表達式 `1 << 2 + 3 << 4` 求值後為何？

:::success
延伸問題:
* 在 C 語言規格書中，找出對應運算子優先權的描述並嘗試解讀
:::
* 在 [C 語言規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 的 6-5 : precedence of operators 中有以下註解:
`The syntax specifies the precedence of operators in the evaluation of an expression, which is the same as the order of the major subclauses of this subclause, highest precedence first.`
意思也就是說運算子的優先權和它在規格書中介紹的順序先後相同，先介紹到的運算子有較高優先權。
* 題目中的 `+` 在 6.5.6 Additive operators 中被定義， `<<` 則到了 6.5.7 Bitwise shift operators 才被定義。因此必須先執行 `+` 再執行 `<<`。
* 答案相當於 `1<<(2+3)<<4 = 512`
:::warning
不用把完整表格列出，但需要將 C99/C11 對應的原文列出！
:notes: jserv
:::
* 附上 [cppreference.com](http://en.cppreference.com/w/c/language/operator_precedence) 所整理的表格

| Precedence | Operator | Description | Associativity |
| --------- | ------ | --------- | ------ |
|1 | ++ -\-<br>()<br>[ ]<br>.<br>-><br>(type){list} |Suffix/postfix increment and decrement<br>Function call<br>Array subscripting<br>Structure and union member access<br>Structure and union member access through pointer<br>Compound literal|Left-to-right|
|2|++ -\-<br>+ -<br>! ~<br>(type)<br>*<br>&<br>sizeof<br>_Alignof |Prefix increment and decrement<br>Unary plus and minus<br>Logical NOT and bitwise NOT<br>Type cast<br>Indirection (dereference)<br>Address-of<br>Size-of<br>Alignment requirement |Right-to-left
|3 |* / % |Multiplication, division, and remainder |Left-to-right|
|4 |+ - |Addition and subtraction|
|5 |<< >> |Bitwise left shift and right shift|
|6 |<<=<br> >>= |For relational operators < and ≤ respectively<br>For relational operators > and ≥ respectively|
|7 |== != |For relational = and ≠ respectively|
|8 |& |Bitwise AND|
|9 |^ |Bitwise XOR (exclusive or)|
|10 | \| | Bitwise OR (inclusive or)
|11 |&& |Logical AND
|12 | \|\| |Logical OR
|13| ?: |Ternary conditional |Right-to-Left
|14 |=<br>+= -=<br>*= /= %=<br><<= >>=<br>&= ^= \|=|Simple assignment<br>Assignment by sum and difference<br> Assignment by product, quotient, and remainder<br> Assignment by bitwise left shift and right shift <br>Assignment by bitwise AND, XOR, and OR|
|15 |, |Comma |Left-to-right

:::warning
摘錄並且解讀！思考為何 C 語言規格要這樣制定優先權順序 (提示: Python 也有類似的規範)
:notes: jserv
:::

---

## 測驗 `4`

考慮某些硬體平台執行乘法的時間較長，我們會以 `(x << 5) - (x)` 取代 `*` 31，那麼 `*` (-6) 該如何用 shift 搭配 add/sub 實作呢？

:::success
延伸問題:
* 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？
:::
* 參考 CS：APP 3/e `2.3.6 乘以常數` (第 71 頁)
:::warning
參考資料時，應該附上章節的名稱
:notes: jserv
:::
* 以 $x * 14$ 為例；因為 $14=2^3+2^2+2^1$，所以可以將 $x * 14$ 改寫成 $x*2^3+x*2^2+x*2^1=(x<<3)+(x<<2)+(x<<1)$。又因 $14=2^4-2^1$，所以也可以寫成 $(x<<4)-(x<<1)$。
* 題目欲求的 $*（-6）$ 可以改寫成 $-2^2-2^1$ 或 $-2^3+2^1$，但取後者可以少做一次減法。得 $x *（-6）=(x<<1)-(x<<3)$ ，所以答案為 `(c) 2 個 shift 搭配 1 個 add/sub`
* CS:APP 中有歸納出： $x*K$ 中的 K 如果可以表示成 [$1^*(111)0^*$] 的 [Regular Expression](https://en.wikipedia.org/wiki/Regular_expression) ，有最小唯一解。其中最高位的 1 在第 n 位，最低位的 1 在第 m 位。
* $K = 2^n+2^{n-1}+...+2^m = 2^{n+1}-2^m$
* 因此 $x*K$ 可寫為：
* $x*K = x*(2^n+2^{n-1}+...+2^m) = x*2^n +x*2^{n-1}+...+x*2^m$ <br> $= (x<<n)+(x<<(n-1))+...+(x<<m)$
* $x*K = x*(2^{n+1}-2^m) = x*2^{n+1}-x*2^m = (x<<n+1)-(x<<m)$
* 由於上述第 1 種表示法有多少 1 就要寫成多少項相加，第 2 種不論 1 的數量有多少都只有兩項。顯然 K 可表示成 [$1^*(111)0^*$] 形式時，因為 1 的數量必$>=3$，相較而言第 2 種方式可以用較少運算次數達成目標。
* 因此當 K 可表示成 [$1^*(111)0^*$] 形式時，有最小唯一解
:::warning
TODO: 找出編譯器最佳化過程中，透過上述技巧改寫整數乘法的案例
:notes: jserv
:::
* 寫了以下程式

#include <stdio.h>
int main () {
    int x=11, y=0;
    y=x*31;
}

* 並透過 `gcc -S` 得到 assembly code，以下擷取部份

    ...
    main:
    .LFB0:
		.cfi_startproc
		pushq	%rbp
		.cfi_def_cfa_offset 16
		.cfi_offset 6, -16
		movq	%rsp, %rbp
		.cfi_def_cfa_register 6
		movl	$11, -8(%rbp)
		movl	$0, -4(%rbp)
		movl	-8(%rbp), %edx
		movl	%edx, %eax
		sall	$5, %eax
		subl	%edx, %eax
		movl	%eax, -4(%rbp)
		movl	$0, %eax
		popq	%rbp
		.cfi_def_cfa 7, 8
	    ret
	...

* [指令](http://www.cs.princeton.edu/courses/archive/spr17/cos217/lectures/13_Assembly1.pdf) 形式:name{b,w,l,q} src, dest
* byte(b) ⇒ operands are one-byte entities
* word(w) ⇒ operands are two-byte entities
* long(l) ⇒ operands are four-byte entities
* quad(q) ⇒ operands are eight-byte entitles
* 第 13.14 行將 x,y 分別放入初值
* 第 15.16 行將 x 值額外存入暫存器 %edx, %eax
* 第 17 行將 %eax 往左移 5 位
* 第 18 行將 %eax 減去 %edx 再存入 %eax
* 第 19 行將 %eax 中值存回 y

---

## 測驗 `5`

考慮以下整數乘法的實作程式碼:

int mul(int n, int m)
{ 
    int ret = 0;
    for (int c = 0; m; c++, m /= 2)
        if (!(m % 2 - 1)) OP
    return ret;
}

上述 `OP` 對應到下方哪個程式敘述呢？

:::success
延伸問題:
* 解釋為何乘法可運作？
:::
* 先把程式碼做一些分析，看到函式 OP 前面的條件式

 !(m % 2 - 1)

* 把他分解來看
* `(m % 2)` 如果 m 是奇數，就是 true
* `(m % 2 - 1)` 則反過來，如果 m 是偶數，才是 true
* `!(m % 2 - 1)` 就簡單了，如果 m 是奇數，就是 true
* 再來看 for loop 每次的變化 `m /= 2` 看到這裡應該就明白， for loop 每次做的就是看 m 的二進位表示，最右邊一位是不是 1 ，如果是的話就執行 OP
* 因為 m /= 2 就相當於右移 1 ，所以在每次執行 OP 時，會把 ret 加上相對應的 n * 2^c^ ，所以可以算出 ret += n << c
* 為何 m 為負，此演算法就失效 ?
根據[ Modulo operator with negative values ](https://stackoverflow.com/questions/7594508/modulo-operator-with-negative-values) 得知，若要算 `x%y` ，電腦其實是做 `x-(x/y)*y` ，因此若 m 是負數，`m % 2` 就會變成是做 `m-(m/2)*2` ，得到的結果不是 0 就是 -1 ，會導致 **if 永遠不成立，因此最後的 ret 永遠都是0**。
* 而會造成上述這個原因是因為我們預測餘數不是 0 就是1，但是若 m 是負數，餘數就會是 0 或是-1，因而使演算法失效。

因此，根據上面的觀察，只要把 code 改為以下，就能支援 signed number。

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

### 延伸問題 ： 解釋為何乘法可運作？
如同我上面所述的，每次只看 m 的一個 bit 去對 n 作位移，再把所有結果加總起來，如果用數學式子可以表達成：
令 $m = (c_0*2^0 + c_1*2^1 + c_2*2^2+......+c_n*2^n)$
$\Rightarrow n*m = n*(c_0*2^0 + c_1*2^1 + c_2*2^2+......+c_n*2^n)$
展開後第 n 項就是 for loop 跑第幾次所加上去的值
:::warning
繼續以邏輯電路的設計，思考乘法器的實作
:notes: jserv
:::

## 參考資料
* [2018q1 Homework2 (作業區)](https://hackmd.io/s/BykAwRuKz)
* [bauuuu1021共筆](https://hackmd.io/s/Bkmr6V6tM#%E7%AC%AC-1-%E5%91%A8%E7%AC%AC-4-%E9%A1%8C)
* [BroLeaf共筆](https://hackmd.io/s/B1QbUVz9G)
* [e94046165共筆](https://hackmd.io/s5qyemoWSUKynwvIUFOcog#%E6%B8%AC%E8%A9%A6amp%E9%87%8D%E8%AE%80%E7%A8%8B%E5%BC%8F%E7%A2%BC)
* [rex662624共筆](https://hackmd.io/s/r189YEBFf)
* [solution](https://legacy.gitbook.com/book/dreamanddead/csapp-3e-solutions/details)