# 2024q1 Homework5 (assessment) contributed by < `dockyu` > ## 閱讀〈因為自動飲料機而延畢的那一年〉與課程啟發 ### 閱讀心得 我看完[因為自動飲料機而延畢的那一年]()後覺得非常感動，他們就好像灌籃高手裡的湘北高中一樣付出努力但是最後卻不是最好的結果，乍看之下好像浪費了付出的努力，但是如果過程中有學到東西(心態的成長，經驗累積，朋友的幫助)就夠了 ## 期末專題提案 希望能夠進行 [simplefs](https://hackmd.io/@sysprog/linux2023-projects#simplefs) 或是 [kHTTPd-改進](https://hackmd.io/@sysprog/linux2023-projects#kHTTPd-%E6%94%B9%E9%80%B2) --- ![image](https://hackmd.io/_uploads/B1kSm7QQA.png) IEEE 754. Assume float is 32-bit width. ```c // Return x * 10 float float_mul10(float x) { // using bitwise operation; No mul/div unsigned sign = (unsigned)x >> 31; unsigned exp = ((unsigned)x << 1) >> 23; unsigned frac = ((unsigned)x << 9) >> 9; unsigned frac1 = frac << 3; unsigned frac2 = frac << 1; frac1 += frac2; frac1 = frac1 >> 4; exp = exp << 2; unsigned result = (sign << 31) | (exp << 23) | (frac1); return (float)result; } ``` > 10 = (2 << 3) + (2 << 0) > float_mul10(4.9) = ? TODO: 撰寫程式碼、測試，分析 誠實面對自己！ --- 如果按照我一開始的寫法 (unsigned) 會將 x 強制轉型，之後操作的都不是浮點數的格式，小數點以下的部份也在這時候就不見了 ```c unsigned frac = ((unsigned)x << 9) >> 9; ``` 印出 (unsigned)x 的二進制 ```bash /* x: 4.9 */ (unsigned)x 4 0x00000004 0000 0000 0000 0000 0000 0000 0000 0100 ``` 用一個指標 p 指到 x ，可以在不用強制轉型的情況下使用 bitwise 去操作，輸出 `*p` 確認 ```c /* x: 4.9 */ unsigned* p = (unsigned*)&x; ``` ```bash *p 0x409ccccd 0100 0000 1001 1100 1100 1100 1100 1101 ``` 取出浮點數的三個區塊 ```c unsigned sign = (*p & 0x80000000) >> 31; /* 1000 0000 0000 0000 0000 0000 0000 0000 */ unsigned exp = (*p & 0x7F800000) >> 23; /* 0111 1111 1000 0000 0000 0000 0000 0000 */ unsigned frac = *p & 0x007FFFFF; /* 0000 0000 0111 1111 1111 1111 1111 1111 */ ``` ```bash x 0x409ccccd 0100 0000 1001 1100 1100 1100 1100 1101 sign 0x00000000 0000 0000 0000 0000 0000 0000 0000 0000 exp 0x00000081 0000 0000 0000 0000 0000 0000 1000 0001 frac 0x001ccccd 0000 0000 0001 1100 1100 1100 1100 1101 ``` 指數部份是 $129-127=2$ ，是2的2次方 小數部份是 $00111001100110011001101$ ，最前面要加上1所以是 $1.00111001100110011001101_{2}$ ，也就是十進制的 $1.22500002384185791016_{10}$ 小數部份乘上指數部份 $1.22500002384185791016*2^{2}=4.90000009537$ 從這個結果可以看出這確實是 4.9 的浮點數，而且我取出的3個部份也是對的，接著就可以將小數部份乘10 我一開始的寫法是 ```c /* frac: 00111001100110011001101 */ unsigned frac1 = frac << 3; unsigned frac2 = frac << 1; frac1 += frac2; ``` 沒有考慮到前面要加上的1，所以現在要做的是將小數部份乘以10並從第一個1開始向後數24個，後面23的就會是 frac 的 23 bit 的內容 首先要將 implicit leading bit 補上去， 在 IEEE 754 中浮點數的 implicit leading bit 是 1 ```c frac = frac | 0x00800000; ``` 可以看到在第24位加上1，因為 frac 佔了 23 位 ```bash frac 0x001ccccd 0000 0000 0001 1100 1100 1100 1100 1101 frac with implicit leading bit 1 0x009ccccd 0000 0000 1001 1100 1100 1100 1100 1101 ``` 首先是能正確的乘2和乘8 ```c unsigned frac2 = frac << 1; /* frac * 2 */ unsigned frac8 = frac << 3; /* frac * 8 */ ``` ```bash frac*2 0x0139999a 0000 0001 0011 1001 1001 1001 1001 1010 frac*8 0x04e66668 0000 0100 1110 0110 0110 0110 0110 1000 ``` ```c frac = frac2 + frac8; /* frac * 10 */ ``` 因為 frac8 在 27 位一定有1，而兩個二進制相加最多只會進位一位，所以 28 位有可能會有 1 ，而 29 位則不可能會有，所以只要判斷 28 位 是不是 1 就可以了，因為如果不是 那就知道最高位的 1 一定在 27 位 + 28 位是 1 : 取 5~27 為 frac + 28 位不是 1(27位是1) : 取 4~26 為 frac ```c if (frac >> 27) frac = frac >> 4; else frac = frac >> 3; frac = frac & 0xff7fffff; /* 1111 1111 0111 1111 1111 1111 1111 1111 */ ``` ```bash frac * 10 0x06200002 0000 0110 0010 0000 0000 0000 0000 0010 frac 23 bit 0x00440000 0000 0000 0100 0100 0000 0000 0000 0000 ``` 在這之前因為有調整位數所以指數部份也要有對應的更改 + 28 位是 1 : frac 位移4位，指數要+4 + 28 位不是 1(27位是1) : frac 位移3位，指數要+3 ```c if (frac >> 27) { exp += 4; frac = frac >> 4; } else { exp += 3; frac = frac >> 3; } ``` 可以成功輸出 ```c float x = 4.9; printf("%f\n", float_mul10(x)); /* 49.000000 */ x = 4.91; printf("%f\n", float_mul10(x)); /* 49.099998 */ x = 4.92; printf("%f\n", float_mul10(x)); /* 49.200001 */ ``` 如果比較直接乘10和我寫的乘10，會發現我的誤差也會出現在直接乘10上，但在某些數值上還是會有不一樣例如3.14 ```bash 49.000000 49.000000 x:4.910000 49.099998 49.099998 x:4.920000 49.200001 49.200001 x:99.000000 990.000000 990.000000 x:99.900002 999.000000 999.000000 x:3.140000 31.400002 31.400000 ``` 我想要作到 branchless ```diff - if (frac >> 27) { - exp += 4; - frac = frac >> 4; - } else { - exp += 3; - frac = frac >> 3; - } + int shift = 3 + (frac >> 27); + exp += shift; + frac = frac >> shift; ``` commit: [06e0963](https://github.com/dockyu/multiply_10/commit/06e09638f7d1e694ad25251096c73985d1d088a9) --- TODO: quiz3+4 + [quiz7](https://hackmd.io/@sysprog/linux2024-quiz7) + extra