changed 7 years ago  
Linked with GitHub

2018q1 Homework2 (assessment)

contributed by < f74034067 >

第 1 週測驗題 測驗 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 對應到下方哪個程式敘述呢？
(a) ret = n << c;
(b) ret += n;
(c) ret <<= n;
(d) ret = c << n;
(e) ret += n << c;

答案

(e) ret += n << c;

想法

首先看到 if (!(m % 2 - 1)) 中如果 m 為奇數，也就是二進位表示最後一位為 1 時，則會進行 OP，再看到 for 迴圈會不斷將 m / 2 ，也就是右移，而 c 會不斷累加，用以紀錄 m 右移了幾次，最後可以發現

若 m 的第一個 bit 為 1 ，則 ret += n * 1
若 m 的第二個 bit 為 1 ，則 ret += n * 2
若 m 的第三個 bit 為 1 ，則 ret += n * 4
...

例如若 m = 11，則 ret = n * (1 + 2 + 8)

延伸

若是 m 為負數時，m % 2會得出 0 與 -1 兩種可能，所以 (!(m % 2 - 1)) 只會得出 false 的結果，因此 m < 0 時只會 return 0，乘法無法順利運作。

如何修正？不要只有「因為…所以…」這樣的描述，要有推論和改進方案！我們做的是工程訓練，不是考公職。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

第 2 週測驗題 測驗 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}\)

想法

利用無窮等比級數的公式，當公比 -1 < r < 1，則總和為 \(\frac{首項}{1-r}\)

答案

  • y = 010011 => 首項 = \(\frac{19}{64}\) ，r = \(\frac{1}{64}\) => x1 = 63
  • y = 101 => 首項 = \(\frac{5}{8}\) ，r = \(\frac{1}{8}\) => x2 = 7
  • y = 0110 => 首項 = \(\frac{6}{16}\) ，r = \(\frac{1}{16}\) => x3 = 5

第 3 週測驗題 測驗 2

3 月 26 日的截止時間剩下幾小時了，但我看不到你的充分付出。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

考慮到下方函式 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;
}

想法

shift_right_arith : 把最左位元的值填入新的最左位元
1101 0111 => 1110 1011

shift_right_logical : 移走的位填充為 0
1101 0111 => 0110 1011

  • 算術右移

    • 由 sizeof(int) * 8 得知整數型態 int 的位元數 w 可推得 p1 = 3。
    • (int) -1 = \((111...1)_2\) ， mask 只要最左邊的 k 個位元為 1，因此左移 (w - k)
    • 由 if (x < 0) 可以推算當 x 最左邊的 bit 為 1 時 xsrl 必須把最左邊的 k 個 bits 改回 1 => xsrl | mask

  • 邏輯右移

    • p4 = 3
    • (int) -1 = \((111...1)_2\) ， mask 只要最左邊的 k 個位元為 1，因此左移 (w - k)
    • 將最左邊 k 個位元填充為 0 => xsra & ~mask

答案

#include <stdio.h>
int shift_right_arith(int x, int k) {
    int xsrl = (unsigned) x >> k;
    int w = sizeof(int) << 3;
    int mask = (int) -1 << (w-k);
    if (x < 0)
        return xsrl | mask;
    return xsrl;
}

unsigned shift_right_logical(unsigned x, int k) {
    unsigned xsra = (int) x >> k;
    int w = sizeof(int) << 3;
    int mask = (int) -1 << (w-k);
    return xsra & ~mask;
}

延伸

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

  • Reference :

  • x86_64

    • sar dest, src
      Arithmetic shift dest to the right by src bits. Spaces are filled with sign bit (to maintain sign of original value), which is the original highest bit.

    • shr dest, src
      Logical shift dest to the right by src bits.

  • Aarch32/Aarch64

    • r0, r1, ASR r2

      shift value in r1 r2 places right and fill in vacant bits with copies of original most significant bit

    • r0, r1, LSR r2

      shift the binary value of r1 r2 places to the right

Select a repo