contributed by <rex662624
>
這題是要實作 float number * 0.5 的code。以下為題目
首先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位。
是的!解法有很多種,你可嘗試用其他方法來做,看能否讓程式碼更精簡。
最後的else為正規數的部分,只要將次方-1(A5=1)就是答案。而下面的A6=31,是把他們移到自己應該要放的位置,例如 sig 應該放在最高位。而後用 logic or 就能拚起完整的32bit。
考慮以下整數乘法的實作程式碼:
在此題中, 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)
這邊的演算法就是數學直式的規則。試想一般二進位直式乘法,若乘數尾數是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。
測試 | 輸出 |
---|---|
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 。
x%y
,電腦其實是做x-(x/y)*y
因此在這裡的狀況,若 m 是負數, if 內需要做 m%2
,就等於是做 m-(m/2)*2
,因此 if 內的 m % 2 不是0就是 -1 , 會導致 if 永遠不成立,因此最後的 ret 永遠都是0 。m % 2 - 1
來判斷,但是若 m 是負數,餘數就會是0或是-1,因而使演算法失效。因此,根據上面的觀察,只要把 code 改為以下,就能支援 signed number。
以上程式碼多加了 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 |
考慮到下方函式 shift_right_arith
和 shift_right_logical
分別表示算術右移和邏輯右移,請嘗試補完程式碼。可由 sizeof(int) * 8
得知整數型態 int
的位元數 w
,而位移量 k
的有效範圍在 0 到 w - 1
。
首先要釐清何謂邏輯位移 (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 。
首先查資料時,有查到Java本身就已經有把邏輯位移與算術位移分開,分別是>>>
(logical shift right )、>>
( arithmetic shift right)。
參考 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 。
參考 ARM Compiler toolchain Assembler Reference
Arithmetic shift
ASR
Logical shift
LSR
LSL
可以發現在算術位移並沒有左移這個指令,推測是因為算術左移其實是和邏輯左移作的動作相同,所以沒有必要再特地創造另一個 instructin 。
TODO: 參照 ARM-Assembly: Arithmetic Shift / Logical Shift 以及討論中提到的材料,用圖和案例解說
而以上三者的功效則與 X86_64 相似,都會把最後一個移走的 bit 存進carry當中。
除了上面提到的在不同架構, 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
Variable size | ARM | x86 | x64 |
---|---|---|---|
32 | 256 | 32 | 32 |
64 | 256 | 256 | 64 |
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 |
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
看了交大學長的這篇心得分享後,佩服之餘同時也覺得有點惶恐,因為裡面說到的"資工系的學生不會寫程式",不禁讓我反思,我們在學校學的種種知識,究竟會不會跟產業脫節,又或者更準確的說,我們是否能像作者一樣做出這種真的能賣出銷售的產品,把在學校所學的知識應用到市場層面。
而上了三周本學期的這堂課後,我也了解了自己在實作上的不足,上課的許多範例,與分派的許多回家作業,都是與業界息息相關。而我在學習的過程中,與看到這篇文章的作者,更了解到了自己的渺小,而我也學到了,在學習的路上要保持著永遠不滿足的心態,才能越來越進步。
作者找到了兩個志同道合的好友參與這項專案,用三人團隊做出了這個自動飲料機。而貫通整篇文章的中心思想就是—遇到困難仍然勇往直前。許多不同領域的學生要做到整合,勢必資訊領域的學生也要懂機械,機械領域的學生也要略知資訊,才能知道甚麼可行,什麼不可行。因此製作過程中一定會遇到許多困難,而支撐他們的,是靠對這件事的熱情,與心中的夢想。
最後,這件發明也因為作者去當兵,乏於維護而無法送進飲料店。但我覺得他們也沒有失敗。或者說,花時間去提升自己,增強自己的競爭力,不管市場採不採納,永遠稱不上是失敗。因為就算沒有成功打入市場,他們也贏得了經驗。
這個世界比任何人都殘酷,也比任何人都公平,犧牲了多少就會得到多少(節錄自文章中)。我認為不僅僅是指他們做專案的過程付出很多,光是有個夢想,敢開始去接專案或發明東西,我認為就是跨出了一大步,這也是現在大部分的學生都沒有的。而我們這些只有課內科目要學習的學生,就更沒有理由偷懶了。畢竟人不付出犧牲,就得不到任何回報,一棵樹要長得更高,接受更多的光明,那麼它的根就必須更深入黑暗。