Try   HackMD

D03: assessment

contributed by <rex662624>

第二周測驗題 第2題

這題是要實作 float number * 0.5 的code。以下為題目




































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

解題

首先4~7行分別把正負號、除了正負號剩下來的數字、次方項、數字部分離出來。注意到 & 在這裡都是 mask 的功能。 例如 f & 0x7FFFFF;就是把後23位保留，正好是IEEE-754 單精度的 mantissa 部分。

第10行的部分，NaN 和 INF 乘上 0.5 分別就是 return NaN 和 INF ，而他們的次方部分為11111111(=A0)。

第18行的addition是 round to even 作用。(CS:APP 3/e 第83頁有講述 round to even) 也就是乘上0.5後，要是有動到 mantissa ，就必須要考慮捨入問題。而這裡只有最後2 bit 是11時要+1，(frac & 0x3)是先把最後3位 mask 出來 ，而後會做 (最後三位)==0x3 ;如果最後兩位是11，addition才=1 。

而除了上面的 Nan 和 INF ，我們可以分3種狀況 : Denormalized 的數字， Normalized 的數字做完運算後成為 Denormalized ， 還有運算前後皆為 Normalized 。 分別為圖上的if 、 else if 、else 。

首先第一種狀況，因為 Denormalized 的數字 exp 部分為0，所以要乘上0.5，直接在 mantissa 的部分向右移一位(A1=1)。最後注意要加上捨入部分。

第二種狀況，因為 exp=1 ，因此由正規數變為非正規數。而26 27行跟第一種狀況做的動作相同(A2=1)。第28行的部分，我則是覺得可以改寫成 exp = rest >> A3 ，因為rest本來就是扣掉sign之後的數字，再右移後一定前面的位數都會是0 。甚至可以寫exp = 0就好，因為只有 exp為1 狀況會進入，而做完後一定是 denormalized ，也就是 0 。而這裡的答案是A3=23 A4=0XFF，意義是先右移使 exp 在最低位，再用 mask 保證只保留末8位。

是的！解法有很多種，你可嘗試用其他方法來做，看能否讓程式碼更精簡。

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

最後的else為正規數的部分，只要將次方-1(A5=1)就是答案。而下面的A6=31，是把他們移到自己應該要放的位置，例如 sig 應該放在最高位。而後用 logic or 就能拚起完整的32bit。

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

解題

在此題中， c 是用來計算目前跑了幾次 loop ， m 每次都除以2，就是每次都往右 shift 1 bit 。

而 if 內判斷的是若是目前的 m 最後一個 bit 為 1 就要做後面的 OP 。因為 m%2 是把最後的 bit 為何找出來，不是1就是0。而後-1會變成0或-1。再加上一個 !，因為 !0= 1 、 !(-1)=0 ，因此原本 m 最後一個 bit 為 1，if內才會為1。

然後以乘法直式的想法，就可以想出 OP = ret += n << c 。

延伸問題 : 解釋為何乘法可運作？

此處的演算法，與計算機組織學到的二進位乘法器電路相同。
(圖片出自於計算機組織上課投影片Ch3_Arithmetic_1)

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 →

這邊的演算法就是數學直式的規則。試想一般二進位直式乘法，若乘數尾數是1，我們會把1乘上被乘數寫下來，之後往左一位看(對應到 m/2 )。而後我們看倒數第二個 bit 時，若又是 1 ，我們會把乘數寫下來，但這時候要寫的位置是在左移 1bit 的位置 (對應n<<c) 。

舉例: 若是 15 X 16 換成二進位是 01111(n) X 10000(m) 。第一次進入 for 迴圈後， m 的最後一位不為0，因此會不做 if 繼續下個迴圈，直到 c=4 ，此時 m=00001 ，才會做 ret+=(01111)<<4 。下次 m/2 後 m 已經=0，所以跳出迴圈，算出答案為11110000，也就是240。

* 實驗 : 是否適用於 signed 和 unsigned 狀況

測試 輸出
printf("%d\n",mul(85,16)); 1360
printf("%d\n",mul(-85,16)); -1360
printf("%d\n",mul(85,-16)); 0
printf("%d\n",mul(-85,-16)); 0

觀察到: 只適用於兩者皆為 unsigned ，但 n 若是為負號也可運作。 m 若是為負號會使答案為0 。

  • 為何 m 為負，此演算法就失效 ?
    根據 Modulo operator with negative values 得知，若要算x%y ，電腦其實是做x-(x/y)*y 因此在這裡的狀況，若 m 是負數， if 內需要做 m%2 ，就等於是做 m-(m/2)*2 ，因此 if 內的 m % 2 不是0就是 -1 ， 會導致 if 永遠不成立，因此最後的 ret 永遠都是0 。
    而會造成上述這個原因是因為我們預測餘數不是0就是1，所以用m % 2 - 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;
}

以上程式碼多加了 else if ，是 m 為負的狀況。因為 m 為負數 ，m%2 不是0就是-1，所以若m%2==-1，就要做ret -= n<<c 。用減的原因是因為 m 是負數，因此要用減法而非加法。

而上面的演算法也不會影響到本來的運算。因為若 m 為正數，只分為 m%2 ==1 和 m%2 ==0 ，而 m%2 ==1 會跑進上面的 if ， m%2 ==0 也不會跑進下面的 else if ，與原來的行為相同。

測試 輸出
printf("%d\n",mul(17,8)); 136
printf("%d\n",mul(-17,8)); -136
printf("%d\n",mul(17,-8)); -136
printf("%d\n",mul(-17,-8)); 136

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

解題

首先要釐清何謂邏輯位移 (Logical shift) 與算術位移 (Arithmetic shift) ，以 shift right 來說，邏輯位移不論是正數還是負數，左邊都會補0，而算術位移則是需要補上數字的 MSB(most significant bit) 。因此若是負數就會補1，正數則補0。

題目上的第4、5行，是在第7行做使用。 w 的意義是先得到 int 的 bit 數，因為 1byte = 8 bits ，因此需要左移 3 bits ，P1=3。而 mask 是利用 int 總 bit 數，也就是 w ，減去要位移的 bit 數 ，因此P2=w-k，而因為邏輯右移需要在前面補上MSB， 而剛才的 mask 除了最低的 w-k bits 會全部都是 1 ，因此要用 or (P3=|)，才能使 x 為負數的狀況時，前面補上的 bit 都將是1。

而下面的 function ，也就是算術位移，P4與P5作用都與上面相同(P4=3 P5=w-k)，因為 P5=w-k 是之後要保留下來的bit 數，其他在左邊的bit全部都要填成0。因此為了要保留這些 bits 清空前面的 bits， 因此要用 and 而非 or( P6= &)，P7 要改成 ~mask ， 讓前面的 bit 變成0 ，後面 w-k bits 全部都為 1 。

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

首先查資料時，有查到Java本身就已經有把邏輯位移與算術位移分開，分別是>>>(logical shift right )、>>( arithmetic shift right)。

X86_64

參考 x86 Assembly Language Reference Manual 與 X86 Assembly/Shift and Rotate

  • Arithmetic shift
    sal sar ，分別代表 shift arithmetic left 、 shift arithmetic right 。
    語法:sal dest,CL sar dest,CL，把 dest 算數左/右移 CL 個 bit ，特性是最後一個被移走的 bit 會在 carry flag 當中。

  • Logical shift
    shl shr ，分別代表shift logical left 、 shift logical right 。
    語法:sal dest,CL sar dest,CL，把 dest 邏輯左/右移 CL 個 bit ，特性與算術位移相同，最後一個被移走的 bit 會在 carry flag 當中。

  • Double Precision shift
    shld shrd，代表double-precision left shifts 與 double-precision right shifts 。
    語法:shld dest, src, cnt , shrd dest, src, cnt 。 src 與 cnt 可適用於 16- or 32-bit register value 。在 64 bits的環境下也支援 64-bit register vale 。 其cnt 可以是 immediate byte value 或是 CL register 。 而src 限定要是 register ， dest 則可以是 register ，或是 memory location 。

ARMv8架構 (Aarch32/Aarch64)

參考 ARM Compiler toolchain Assembler Reference

  • Arithmetic shift
    ASR

  • Logical shift
    LSR LSL

可以發現在算術位移並沒有左移這個指令，推測是因為算術左移其實是和邏輯左移作的動作相同，所以沒有必要再特地創造另一個 instructin 。

TODO: 參照 ARM-Assembly: Arithmetic Shift / Logical Shift 以及討論中提到的材料，用圖和案例解說

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

而以上三者的功效則與 X86_64 相似，都會把最後一個移走的 bit 存進carry當中。

同樣的 shift operator (<< , >>)在不同架構的差異

除了上面提到的在不同架構， shift 有不同的 assembly 指令外，同樣的 << operator , 在不同架構也會有差異。參考 Visual C++ Team Blog 。

在 ARM 架構上， shift operators 會將 256 bits 視為一個 pattern space 。意思就是 shift 每 256 bits 才會 "wraps around" (每 shift 256 bits 會 repeat 的意思)。
在 X86 和 X64 compile ，若是 shift 32-bit 的 operand ，兩者的行為會相同，都是每 32 bits wraps around 一次。但如果是 shift 64-bit 的 operand ，因為X64有支援 64-bit 的instruction,所以 compiler 會去 emits 這個 instruction 。但在 X86 中，由於不支援 64-bit instruction , 所以會去 emits 一個 small software routine,這個 routine 與 ARM 相同， 都是 256 bits 為一個 pattern space 。因此行為也與 ARM 較相似。

emits 在原文中的用法是 emit the instruction 與 emit the routine , 因此我猜測是與 call 相近的意思 , 但怕翻譯不精準所以採用原文。
( emit (vt) 發出，射出，散發)

另外推測在 X86 中，若是 shift 64-bit 的 operand ，效能會比在 X64 慢，因為在文中說到 X86 會去 emit 另外的 software routine .而 X64 只是去做內建 instruction 而已。但礙於手邊沒有那麼多系統，因此先不做效能比較。
rex662624

  • Widths of the pattern spaces on each architecture
    可以看出 shift 32-bit 的 data ，X86 與 X64 相同， 64-bit 則是 X86 與ARM 相同。
Variable size ARM x86 x64
32 256 32 32
64 256 256 64
  • Given a 32-bit integer with a value of 1
    以下是對用 32-bit integer ,儲存的值為1 ，將之 shift 不同位所得到結果。(取自於 Visual C++ Team Blog 。)
    可以發現 X86 與 X64 果真行為相同，每只要將 Shift amount % 32 ，就是他應該要 shift 的位數。而ARM 32~128 bits 的欄位都為0，因為他是 256 bits 才一個循環 ，所以 shift 32 bits 雖然還沒到 256 bits ，但由於是用 32-bit int 來儲存 ，所以無法存 2^32 而變成 0。
Shift amount ARM x86 x64
0 1 1 1
16 32768註 32768註 32768註
32 0 1 1
48 0 32768註 32768註
64 0 1 1
96 0 1 1
128 0 1 1
256 1 1 1
  • Given a 64-bit integer with a value of 1:
    以下是對用 64-bit integer ,儲存的值為1 ，將之 shift 不同位所得到結果。可以看到這次 X86 與 ARM 行為相同，都是 256-bit 一個循環，在shift 256 bits 後就會回到 1 ，因為 256%256=0 ，等同於 shift 0 bit
Shift amount ARM x86 x64
0 1 1 1
16 32768註 32768註 32768註
32 4294967296 4294967296 4294967296
48 2^48 2^48 2^48
64 0 0 1
96 0 0 4294967296
128 0 0 1
256 1 1 1

上面兩個表格，值有"註"的欄位，應為作者誤植。因為2^16應該是 65536 而非 32768。
rex662624

因為自動飲料機而延畢的那一年心得與啟發

看了交大學長的這篇心得分享後，佩服之餘同時也覺得有點惶恐，因為裡面說到的"資工系的學生不會寫程式"，不禁讓我反思，我們在學校學的種種知識，究竟會不會跟產業脫節，又或者更準確的說，我們是否能像作者一樣做出這種真的能賣出銷售的產品，把在學校所學的知識應用到市場層面。

而上了三周本學期的這堂課後，我也了解了自己在實作上的不足，上課的許多範例，與分派的許多回家作業，都是與業界息息相關。而我在學習的過程中，與看到這篇文章的作者，更了解到了自己的渺小，而我也學到了，在學習的路上要保持著永遠不滿足的心態，才能越來越進步。

作者找到了兩個志同道合的好友參與這項專案，用三人團隊做出了這個自動飲料機。而貫通整篇文章的中心思想就是—遇到困難仍然勇往直前。許多不同領域的學生要做到整合，勢必資訊領域的學生也要懂機械，機械領域的學生也要略知資訊，才能知道甚麼可行，什麼不可行。因此製作過程中一定會遇到許多困難，而支撐他們的，是靠對這件事的熱情，與心中的夢想。

最後，這件發明也因為作者去當兵，乏於維護而無法送進飲料店。但我覺得他們也沒有失敗。或者說，花時間去提升自己，增強自己的競爭力，不管市場採不採納，永遠稱不上是失敗。因為就算沒有成功打入市場，他們也贏得了經驗。

這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少(節錄自文章中)。我認為不僅僅是指他們做專案的過程付出很多，光是有個夢想，敢開始去接專案或發明東西，我認為就是跨出了一大步，這也是現在大部分的學生都沒有的。而我們這些只有課內科目要學習的學生，就更沒有理由偷懶了。畢竟人不付出犧牲，就得不到任何回報，一棵樹要長得更高，接受更多的光明，那麼它的根就必須更深入黑暗。

Last changed by 
 
蔡宇軒
0
1531
Published on HackMD