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_arithshift_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

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

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

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

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

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

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