2018q1 Homework2 (assessment)

contributed by potter903p

1.課堂測驗及參考解答

第 1 周 - 測驗 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 為多少？

想法 & 作法 :

• 首先先觀察回傳質 return(isMultN(abs(odd_c - even_c))); 得知唯有在 odd_c 等於 even_c 時程式才會判定為 N 的倍數。
• while 迴圈中第一個判斷式會判斷傳入數值之奇數位原的值為 1 或是 0 ，為 1 時將數值 odd_c 加 1 ， 而第個二個判斷式則為偶數位原的相同判斷。
• 由前述兩點得知該數字 N 之倍數的特性為偶數位原與奇數位元個數相同。

  這邊思考不夠周全，透過 e94046165 同學的筆記得知由於是遞迴呼叫，所以兩者之差值為 3 的倍數時均會成立，相比之前只有考慮到兩者數值相等應該思考輸入為多少時會回傳 1。
  因此最後的結論為：偶數位原與奇數位原之差值為 3 的倍數

• 在這邊將前 4 位元之 odd_c 以及 even_c 列出來做比較 :
  • 同為 0 ：
    ${0000}_2(0_{10})$
  • 同為 1 ：
    ${0011}_2(3_{10})$ ,
    ${1001}_2(9_{10})$ ,
    ${0110}_2(6_{10})$ ,
    ${1100}_2({12}_{10})$
  • 同為 2 ：
    ${1111}_2({15}_{10})$
• 經由觀察得知這些均為 3 的倍數故 N = 3

---

延伸問題:

• 為什麼上述程式碼可運作呢？
• 將 N 改為其他質數再改寫為對應的程式碼，一樣使用遞迴

N = 5

#include <stdlib.h>
int isMultN(unsigned int n) {
    int number = 0;
    number = n & 1;
    while(n > 0) {
        n >>= 1;
        number += (n & 1) * 2;
        n >>= 1;
        number += (n & 1) * 4;
        n >>= 1;
        number += (n & 1) * 8;
        n >>= 1;
        number += (n & 1) * 6;
    }

    if(number <= 15) {
        return number == 15 ? 1 : number == 10 ? 1 : number == 5 ? 1 : 0;
    }

    return isMultN(number);
}

想法 & 作法 :

• 剛開始的構想很簡單大家國中小都有學過 5 的倍數為個位數為 0 或 5 的數，因此這邊就想辦法把所輸入數字的個位數字求出來。
• 在這邊同樣做二進位表示法的初步觀察，對一個 8 bits 的數字而言每一個位數所代表的數值如下圖 ：
  ​​​​0000 0000    0000 0000    0000 0000    0000 0000    0000 0000
  ​​​​        ^           ^           ^           ^          ^
  ​​​​        1           2           4           8         16
  ​​​​             0000 0000    0000 0000    0000 0000    0000 0000 0000
  ​​​​               ^           ^           ^               ^
  ​​​​              32          64         128             256
  

  由於只關心個位數的值所以將其他位數忽略以後會發現存在著 2 , 4 , 8 , 6 四個數字為一組的循環規律，因此只需要將第一位的值取出以後，依序取出四個一組的數字乘上相對應的重複數值後再做相加就可以得到一個經過適當刪減後的數值。
• 經過實驗凡是 15 以下的數值經過這套轉換後都會保有原本之數值，所以回傳值為 0 , 5 , 10 , 15 的數值都是 5 的倍數。

N = 7

---

第三周 - 測驗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;
}

求 P1 ~ P7 的值？

想法 & 作法 ：

首先要弄清楚 Arithmetic shift 和 Logical shift 之間的差異，兩者在 left shift 的操作是相同的都會在 LSB 端插入 0 ， Arithmetic right shift 會在 MSB 端插入原本的 sign bit ， logical right shift 則會在 MSB 端插入 0 。

而在 C 語言中 right shift 的兩種方法指令是相同的，而使用的時機是取決於所傳入的數字。
-> 如果傳入的數字為 unsigned value 則執行 logical shift
-> 如果傳入的數字為 signed value 則執行 arithmetic shift

• 基於題目給的提示，我們可以知道 w 為 int 的位元數，由於 1 byte = 8 bits 所以這邊要把得到的值乘上 8 倍才會等於位元數，所以 P1 以及 P4 的數值皆為 3 （向左 shift 三位）。
• shift_right_arith() 中，第一行先將傳入的數字 cast 成 unsigned 的格式，如果傳入的數值是 < 0 ，則原來的數值會變成原數值再加上 UINT_MAX + 1(說明)，更重要的是這會讓原本預計要執行 arithmetic right shift 的 signed value 變成執行 logicaL right shift 的 unsigned value ，因此對負數而言這樣轉換完會使得原本前面應該重複填入的 sign bit : 1 變成填入 0 ，因此我們要設法在 if(x < 0) 中做補救。
• 依照上一個步驟做完轉換會讓原本前面應該為 1 的 bits 變成 0 ，至於是多少個 bits 呢？總長為 w 向右 shift k 個位置，所以預期開頭應該要有 k 個為 1 的 bits ，因此這邊的 mask 應該為開頭 k 項為 1 其餘為 0 的形式，這樣之後只要和先前轉換完的數字做 ｜ 的指令這樣就可以將前 k 項轉換為 1 ，在這邊 P2 數值應為 w - k 而 P3 則為前述的 ｜ 指令。
• shift_right_logical() 中，第一行將傳入的數字轉換成有號數，所以這邊的 right shift 就會是 arithmetic shift ，同樣對於 < 0 的數字而言由於是執行 arithmetic right shift ，所以原來預期是由 0 shift in 但是卻變成了 sign bit : 1 shift in ， 因此我們要想辦法將前面填入的 1 轉換成 0 。
• 在這邊要改變的位元數和剛才一樣是前 k bits ，所以P5 同樣是 w - k ，但由於是要清除 bits 的緣故，這邊的 mask 要變成 ~mask 然後再跟轉換完的數做 & 的操作，這樣才能在清除前面位元的情況下不改變後面後面位元的值，所以 P6 為 & ,P7 為 ~mask。

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

---

第二周 - 測驗3

題目 ：

考慮到某些實數的二進位表示形式如同

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

想法 & 作法 ：

先來複習一下等比數列的定義：從第二項起，每一項與前一項的比都是一個常數。
以題目中的

$0.010101...$（y = 01）為例就可以把它看成是：

$0\ast 2^{-1}+1\ast 2^{-2}+0\ast 2^{-3}+1\ast 2^{-4}...$
其實就是一個首項為

$(0\ast 2^{-1}+1\ast 2^{-2})$ 而公比為

$2^{-2}$ 的無窮等比數列的和，在這邊順便複習一下無窮等比級數的公式：

$\frac{\mathrm{首}\mathrm{項}}{1-\mathrm{公}\mathrm{比}}$ 因此就使用這個公式帶入題目中。

• y = 010011
  首項 :
  $(0\ast 2^{-1}+1\ast 2^{-2}+0\ast 2^{-3}+0\ast 2^{-4}+1\ast 2^{-5}+1\ast 2^{-6})$
  公比 :
  $2^{-6}$
  計算 :
  $\frac{(0\ast 2^{-1}+1\ast 2^{-2}+0\ast 2^{-3}+0\ast 2^{-4}+1\ast 2^{-5}+1\ast 2^{-6})}{1-2^{-6}}=\frac{19}{x1}$
  答案 :
  $x1=63$
• y = 101
  首項 :
  $(1\ast 2^{-1}+0\ast 2^{-2}+1\ast 2^{-3})$
  公比 :
  $2^{-3}$
  計算 :
  $\frac{(1\ast 2^{-1}+0\ast 2^{-2}+1\ast 2^{-3})}{1-2^{-3}}=\frac{5}{x2}$
  答案 :
  $x2=7$
• y = 0110
  首項 :
  $(0\ast 2^{-1}+1\ast 2^{-2}+1\ast 2^{-3}+0\ast 2^{-4})$
  公比 :
  $2^{-4}$
  計算 :
  $\frac{(0\ast 2^{-1}+1\ast 2^{-2}+1\ast 2^{-3}+0\ast 2^{-4})}{1-2^{-4}}=\frac{2}{x3}$
  答案 :
  $x3=5$

---

2.閱讀 因為自動飲料機而延畢的那一年 的啟發

• 讀後心得和啟發

---

3.研讀給定的「課後學習」教材和 CS:APP 3/e，紀錄心得和提問