Try   HackMD

2018q1 Homework2 (assessment)

contributed by <raygoah>

課前測驗參考解答

Week 1

題目：

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

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

想法及思考

  1. 一開始看到題目，可以知道此題是為了要做乘法
  2. 看到在 for 迴圈中，每次都將 m / 2 ，同時將 c 的值加一，可以聯想到 n << 1 代表把 n 乘 2 乘一次，因此若寫成 n << c ，及代表要將 n 乘 2 乘 c 次
  3. 而觀察到 for 迴圈中的 if ，猜測本題重點便是在於為什麼達成 if 的條件後要進行 OP ，這背後代表的意思，就是完成這題乘法的關鍵

解題思緒

  • 從 if (!(m % 2 - 1)) OP 中可以知道，只有在 m 為奇數時，OP 才會執行，而這代表著只有在 m 一開始就是奇數，第一次進迴圈的時候 OP 會被執行，此外還有在跳出迴圈前一次，m = 1 時，OP 會被執行
  • 而從以上幾點來看，迴圈中每次將 m 除以 2，並將 c 加一的目的，便是要將 m 改寫成
    2c    ，但這樣會因為 m 是奇數時而無法順利表示，因此若要在 m 是奇數時表示成
    2c+1     的話，便需要利用 m 是奇數時第一次進入 for 迴圈中，if 的條件式會成立，OP 會執行的這一點，即可以順利的將 m 表示成
    2c+1
  • 而在了解了 m 是如何表示後，便可以了解此題想要做的，應該是要把
    n∗m     改寫成以下兩種狀況
    • m 為奇數時：
      (n∗2c)+(n∗1)
    • m 為偶數時：
      n∗2c
  • 而這時便可以利用 << 的特性，每向左移一位元代表乘以二，以及結合上述的想法，便可以選出正確答案：OP 為 (e) ret += n << c;

延伸問題

解釋為何乘法可運作？

  • 如我在上方所提到，此題將乘數 m 改寫，依照 m 為奇或偶分別寫成
    2c+1     以及
    2c    ，因此整個乘法便會改寫成如下所示：
    • m 為奇數時：
      (n∗2c)+(n∗1)
    • m 為偶數時：
      n∗2c
  • 在將
    n∗m     改寫後，便可以利用 <<，寫成如題目的程式碼，順利的完成可運作的乘法程式

參考

  • rwe0214 在課堂上的講解

Week 2

題目：

typedef unsigned int float_bits;

float_bits float_x0_5(float_bits f) {
    unsigned sig = f >> 31;
    unsigned rest = f & 0x7FFFFFFF;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;

    /* NaN or INF */
    if (exp == A0) return f;

    /* round to even. Last 2 bits of frac are considered:
     * 00 => 0 just >> 1
     * 01 => 0 (round to even) just >> 1
     * 10 => 1 just >> 1
     * 11 => 1 + 1 (round to even) just >> 1 and plus 1
     */
   int addition = (frac & 0x3) == 0x3;

    /* Denormalized */
    if (exp == 0) {
        frac >>= A1;
        frac += addition;
    /* Normalized to denormalized */
    } else if (exp == 1) {
        rest >>= A2;
        rest += addition;
        exp = rest >> A3 & A4;
        frac = rest & 0x7FFFFF;
    /* Normalized */
    } else {
        exp -= A5;
    }
    return sig << A6 | exp << 23 | frac;
}

想法及思考

  • 看完題目可以知道，此題的 function 想要做的，是將以 IEEE 754 表示的 32 位元浮點數乘與 0.5
  • 要先搞清楚 IEEE 754 的規則，當初就是沒有搞清楚，結果這幾題都錯很慘，念資工連這都不會，慚愧…
  • 主要要測驗的，是其中註解為 Denormalized 以及 Normalized 的部份，熟悉規則便可解決
  • fraction 為 0 ~ 22 bits，exp 為 23 ~30 bits，sign bit 為第 31 bit

解題思緒

  • 照著題目順序從 A0 看到 A6，雖然每一題的選項都很多，但只要知道 IEEE 754 的規則，要選出正確答案不難

  • A0:

    ​​​​/* NaN or INF */
​​​​if (exp == A0) return f;
    • 可以看到註解清楚的告訴我們，這邊是要處理關於遇到 NaN 以及 INF 時該做什麼
    • 這裡是決定當遇到這兩種情況時，就不用再乘 0.5，直接回傳原本的數字
    • 因此考慮到 IEEE 754 對於 NaN 以及 INF 的定義，這兩種情況的 exp 值會是全為 1 ，因此要選擇一個全為 1 的答案，也就是 0xFF

  • A1:

    ​​​​/* Denormalized */
​​​​if (exp == 0) {
​​​​    frac >>= A1;
​​​​    frac += addition;
​​​​}
    • A1 關係到的部份，是在遇到非規格化的值時，該做些什麼處理
    • 這部份也是滿直觀的，因為非規格化的值，exp 為 0 ，因此在這裡不需要做什麼，只需要將 fraction 的部份乘上 0.5，也就是右移一次即可，所以 A1 選 1
    • 而在 frac += addition; 的部份是用於做捨入的，採用 round to even 的方法，捨入的方法在 code 中的註解有詳細的介紹

  • A2 A3 A4:

    ​​​​/* Normalized to denormalized */
​​​​else if (exp == 1) {
​​​​    rest >>= A2;
​​​​    rest += addition;
​​​​    exp = rest >> A3 & A4;
​​​​    frac = rest & 0x7FFFFF;
​​​​}
    • 在這個 else if 中，需要填的是 A2 A3 以及 A4
    • 而同樣的註解有說明，這部份所要做的是將規格化的數字在乘上 0.5 後，成為非規格化的數字時，所需要做的處理
    • 這邊利用了在前面先把 sign bit 拿掉後得到的 rest，把 rest 先乘上 0.5，也就是右移一次，所以這裡 A2 和 A1 一樣，也是選 1
    • 接著在 rest += addition; 的部份，同樣的也是做捨入
    • 而在 exp = rest >> A3 & A4; 這裡，要從 rest 中把第 23 到第 31 bit 的數字取出，也就是只要留下 exp 的部份，因此需要先向右移位 23 次，再和 0x7FFFFFFF 做一次遮罩，便可以得到，因此 A3 為 23，而 A4 則是選擇 0x7FFFFFFF

    這邊不理解的一點是，對於 exp 為何不直接將其設為 0

    因為在乘完 0.5 後，得到的答案會是非規格化的數字，而在 IEEE 754 中，只要是非規格化的數字，exp 都會是 0，那麼為何要選擇用 bitwise 的方式而非將 exp 直接設為 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

  • A5

    ​​​​/* Normalized */
​​​​else {
​​​​    exp -= A5;
​​​​}
    • 在 A5 的部份，是關於規格化的數字乘上 0.5 後，還是規格化的數字時，所要做的處理
    • 因為我們要做的是要將整個數乘上 0.5，也就是表示成
      (−1)s∗M∗2E       時，E 的值必須要減一，因此我們將 exp 減 1，即可解決，A5 的答案為 1

  • A6

    ​​​​return sig << A6 | exp << 23 | frac;
    • 在最後要將上面得到的 sig, exp 以及 frac 合成一個資料型態為 unsigned int 的數字回傳，因此依照 IEEE 754 規定，sign bit 為第 32 個 bit，因此將 sig 向左移位 31 次，A6 選澤 31

參考

  • CS:APP 3/e

Week 3

題目：

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

想法及思考

  • 先了解算術右移以及邏輯右移兩者的不同
  • 題目有兩點提示：
    1. 可由 sizeof(int) * 8 得知整數型態 int 的位元數 w
    2. 移位量 k 的有效範圍在 0 到 w - 1

解題思緒

  • 首先先由算術右移的部份下手：

    • 算術右移的特點在於，右移完後會依照 sign bit 是多少，把空缺的 bits 補上，讓右移完成後的結果和原數正負號相同
    ​​​​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;
​​​​}
​​​​
    • int xsrl = (unsigned) x >> k; 首先將 x 右移 K 位
    • int w = sizeof(int) << P1; 這邊可由提示中提到，由 sizeof(int) * 8 得知整數型態 int 的位元數 w，因此要乘上 8 就等同於向左移位 3 次，因此 P1 為 3
    • int mask = (int) -1 << (P2); 在這裡 mask 為了要讓原本是小於 0 的數，在經過算術右移後得到的結果仍舊是負數，因此之後要對從右邊數來 k 個 bits 做遮罩，所以在這邊要將 -1 向左移 (w-k) 次，因此 P2 選擇 w-k
    • 在有關 P3 的部份，接續了 P2，也就是為了要讓原本是小於 0 的數，在經過算術右移後得到的結果仍舊是負數，因此要把 xsl 和 mask 的每個 bit 做邏輯運算的 'or' ，把右邊數來 k 個 bits 全部設為 1 ，因此在這邊 P3 要選 |

  • 接著是邏輯右移的部份

    • 邏輯右移與算術右移不同，在右移後，不管原本數字是正或是負，左邊補上的都是 0 ，因此可能會有原本是負數但經過算術右移後得到正數的結果
    ​​​​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;
​​​​}

    • P4 的地方和 P1 一樣，sizeof(int) * 8 得知整數型態 int 的位元數 w，因此 P4 為 3

    • P5 也是和 P2 的概念一樣，只是之後遮罩的作法不同，但這邊也是為了讓 mask 從右數來 k 個 bits 皆為 1 其他位元皆為 0，因此在這裡 P5 也是選擇 w-k

    • P6 P7 的部份是邏輯右移與算術右移最重要的區別，在邏輯右移中要讓右移後從左邊補上的 bits 全部為 0 ，因此要先將 mask 做一次邏輯運算的 not ，讓 mask 從原本的右邊數來 k 個 bits 皆為 1 其他位元皆為 0 ，變成從右數來 k 個 bits 皆為 0 其他位元皆為 1，接著和 xsrl 做 & ，確認右邊數來 k 個 bits 全部為 0 ，而左邊數來 k 個 bits 留下移位後要的數字，得到最後的結果，因此 P6 為 & 而 P7 為 ~mask

延伸題目

  • 題目：在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
  • x86_64：
    • 邏輯移位：shr 以及 shl
      • 用法: shr src, dest 將 dest 向左移位 src 個 bits
      • 範例：
      ​​​​​​​​movw $ff00,%ax  # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256) 
​​​​​​​​shrw $3,%ax     # ax=0001.1111.1110.0000 (0x1fe0, signed and unsigned 8160)
​​​​​​​​                # (logical shifting unsigned numbers right by 3
​​​​​​​​                #   is like integer division by 8)
​​​​​​​​shlw $1,%ax     # ax=0011.1111.1100.0000 (0x3fc0, signed and unsigned 16320) 
​​​​​​​​                # (logical shifting unsigned numbers left by 1
​​​​​​​​                #   is like multiplication by 2)
      • shr 為向右移位，shl 為向左移位，兩者皆是將超過範圍的 bits 移除，並將空缺的 bits 補上 0
    • 算數移位：sar 以及 sal
      • 用法: sar src, dest 將 dest 向右移位 src 個 bits，並依照原本的 sign bit 是多少，把空缺位都補上一樣的 0 或 1
      • 範例：
      ​​​​​​​​movw $ff00,%ax  # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256)
​​​​​​​​salw $2,%ax     # ax=1111.1100.0000.0000 (0xfc00, unsigned 64512, signed -1024)
​​​​​​​​                # (arithmetic shifting left by 2 is like multiplication by 4 for
​​​​​​​​                # negative numbers, but has an impact on positives with most
​​​​​​​​                # significant bit set (i.e. set bits shifted out))
​​​​​​​​sarw $5,%ax     # ax=1111.1111.1110.0000 (0xffe0, unsigned 65504, signed -32)
​​​​​​​​                # (arithmetic shifting right by 5 is like integer division by 32
​​​​​​​​                # for negative numbers)
  • Aarch32/Aarch64：
    • 邏輯移位：
      • 向右移位：LSR
      • 向左移位：LSL
    • 算術移位：
      • 向右移位：ASR
      • 向左移位：ASL

參考

因為自動飲料機而延畢的那一年

Last changed by 
 
雷承勳
0
582
Published on HackMD