contributed by < dockyu
>
我看完因為自動飲料機而延畢的那一年後覺得非常感動,他們就好像灌籃高手裡的湘北高中一樣付出努力但是最後卻不是最好的結果,乍看之下好像浪費了付出的努力,但是如果過程中有學到東西(心態的成長,經驗累積,朋友的幫助)就夠了
IEEE 754. Assume float is 32-bit width.
// 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 強制轉型,之後操作的都不是浮點數的格式,小數點以下的部份也在這時候就不見了
unsigned frac = ((unsigned)x << 9) >> 9;
印出 (unsigned)x 的二進制
/* x: 4.9 */
(unsigned)x
4
0x00000004
0000 0000 0000 0000 0000 0000 0000 0100
用一個指標 p 指到 x ,可以在不用強制轉型的情況下使用 bitwise 去操作,輸出 *p
確認
/* x: 4.9 */
unsigned* p = (unsigned*)&x;
*p
0x409ccccd
0100 0000 1001 1100 1100 1100 1100 1101
取出浮點數的三個區塊
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 */
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
指數部份是
小數部份是
小數部份乘上指數部份
從這個結果可以看出這確實是 4.9 的浮點數,而且我取出的3個部份也是對的,接著就可以將小數部份乘10
我一開始的寫法是
/* 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
frac = frac | 0x00800000;
可以看到在第24位加上1,因為 frac 佔了 23 位
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
unsigned frac2 = frac << 1; /* frac * 2 */
unsigned frac8 = frac << 3; /* frac * 8 */
frac*2
0x0139999a
0000 0001 0011 1001 1001 1001 1001 1010
frac*8
0x04e66668
0000 0100 1110 0110 0110 0110 0110 1000
frac = frac2 + frac8; /* frac * 10 */
因為 frac8 在 27 位一定有1,而兩個二進制相加最多只會進位一位,所以 28 位有可能會有 1 ,而 29 位則不可能會有,所以只要判斷 28 位 是不是 1 就可以了,因為如果不是 那就知道最高位的 1 一定在 27 位
if (frac >> 27)
frac = frac >> 4;
else
frac = frac >> 3;
frac = frac & 0xff7fffff; /* 1111 1111 0111 1111 1111 1111 1111 1111 */
frac * 10
0x06200002
0000 0110 0010 0000 0000 0000 0000 0010
frac 23 bit
0x00440000
0000 0000 0100 0100 0000 0000 0000 0000
在這之前因為有調整位數所以指數部份也要有對應的更改
if (frac >> 27) {
exp += 4;
frac = frac >> 4;
} else {
exp += 3;
frac = frac >> 3;
}
可以成功輸出
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
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
- 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
TODO: quiz3+4 + quiz7 + extra