在計(jì)算機(jī)圖形運(yùn)算中，常常要將浮點(diǎn)數(shù)轉(zhuǎn)換為整數(shù)，例如在圖像的光柵化階段，就要執(zhí)行大量的類型轉(zhuǎn)換，以便將浮點(diǎn)數(shù)表示的坐標(biāo)轉(zhuǎn)化為整數(shù)表示的屏幕坐標(biāo)。Ok，it's so easy：
----------------------------------------------------------------------------------------
//
// 強(qiáng)制類型轉(zhuǎn)換
// 小數(shù)部分將被裁剪掉
//
int_val = (int)float_val;
----------------------------------------------------------------------------------------
嘿嘿，很高興你居然和我一樣單純！這個(gè)操作實(shí)在是太TINY了，以至于我從來沒想過它是怎么實(shí)現(xiàn)的，直到某天某個(gè)家伙跟我說，不要使用標(biāo)準(zhǔn)C類型轉(zhuǎn)換，因?yàn)槟翘耍∥耶?dāng)時(shí)的震驚不下于倒霉的冒險(xiǎn)者遇上了龍。

標(biāo)準(zhǔn)C類型轉(zhuǎn)換最大的優(yōu)點(diǎn)是，它是獨(dú)立于平臺的，無論是在X86上跑，還是在PowerPC上跑，你什么都不用擔(dān)心，編譯器會為你搞定一切。而這也恰恰是它最大的缺點(diǎn)——嚴(yán)重依賴于編譯器的實(shí)現(xiàn)。而實(shí)際測試表明，編譯器所生成的代碼，其速度實(shí)在不盡人意。

一個(gè)替代的方法是直接對數(shù)據(jù)位進(jìn)行操作。如果你對IEEE浮點(diǎn)數(shù)的表示法比較熟悉的話（如果你壓根什么都不知道，請先查閱文末附錄中的資料），這是顯而易見的。它提取指數(shù)和尾數(shù)，然后對尾數(shù)執(zhí)行移位操作。代碼如下：
----------------------------------------------------------------------------------------
//
// 將32位浮點(diǎn)數(shù)fval轉(zhuǎn)換為32位整數(shù)并存儲在ival中
// 小數(shù)部分將被裁剪掉
//
void TruncToInt32 (int &ival, float fval)
{
ival = *(int *)&fval;

// 提取尾數(shù)
// 注意實(shí)際的尾數(shù)前面還有一個(gè)被省略掉的1
int mantissa = (ival & 0x07fffff) | 0x800000;

// 提取指數(shù)
// 以23分界，指數(shù)大于23則左移，否則右移
// 由于指數(shù)用偏移表示，所以23+127=150
int exponent = 150 - ((ival >> 23) & 0xff);

if (exponent < 0)
ival = (mantissa << -exponent);
else
ival = (mantissa >> exponent);

// 如果小于0，則將結(jié)果取反
if ((*(int *)&fval) & 0x80000000)
ival = -ival;
}
----------------------------------------------------------------------------------------
該函數(shù)有一個(gè)BUG，那就是當(dāng)fval=0時(shí)，返回值是2。原因是對于語句mantissa>>exponent，編譯器使用了循環(huán)移位指令。解決方法是要么對0作特殊處理，要么直接用匯編來實(shí)現(xiàn)。

這個(gè)函數(shù)比標(biāo)準(zhǔn)的C轉(zhuǎn)換要快，而且由于整個(gè)過程只使用了整數(shù)運(yùn)算，可以和FPU并行運(yùn)行。但缺點(diǎn)是，(1)依賴于硬件平臺。例如根據(jù)小尾和大尾順序的不同，要相應(yīng)地修改函數(shù)。(2)對于float和double要使用不同的實(shí)現(xiàn)，因?yàn)槎叩臄?shù)據(jù)位不同。(3)對于float，只能保留24位有效值，盡管int有32位。

更快的方法是使用FPU指令FISTP，它將棧中的浮點(diǎn)數(shù)彈出并保存為整數(shù)：
----------------------------------------------------------------------------------------
//
// 將64位浮點(diǎn)數(shù)fval轉(zhuǎn)換為32位整數(shù)并存儲在ival中
// 小數(shù)部分將四舍五入到偶數(shù)
//
inline void RoundToIntFPU (int &ival, double fval)
{
_asm
{
fld fval
mov edx, dword ptr [ival]
fistp dword ptr [edx]
}
}
----------------------------------------------------------------------------------------
很好，無論速度還是精度似乎都相當(dāng)令人滿意。但如果換一個(gè)角度來看的話，fistp指令需要6個(gè)cycle，而浮點(diǎn)數(shù)乘法才僅僅需要3個(gè)cycle！更糟的是，當(dāng)fistp運(yùn)行的時(shí)候，它必須占用FPU，也就是說，其他的浮點(diǎn)運(yùn)算將不能執(zhí)行。僅僅為了一次類型轉(zhuǎn)換操作就要付出如此大的代價(jià)，光想想就覺得心疼。

當(dāng)然，它也有很多優(yōu)點(diǎn)：更快的速度，更精確的數(shù)值（四舍五入到偶數(shù)），更強(qiáng)的適用性（float和double均可)。要注意的是，F(xiàn)PU默認(rèn)的四舍五入到偶數(shù)（round to even）和我們平常所說的四舍五入（round）是不同的。二者的區(qū)別在于對中間值的處理上。考慮十進(jìn)制的3.5和4.5。四舍五入到偶數(shù)是使其趨向于鄰近的偶數(shù)，所以舍入的結(jié)果是3.5->4，4.5->4；而傳統(tǒng)的四舍五入則是3.5->4，4.5->5。四舍五入到偶數(shù)可以產(chǎn)生更精確，更穩(wěn)定的數(shù)值。

除此之外，還有更好，更快的方法嗎？有的，那就是華麗的 Magic Number ！

請看下面的函數(shù)：
----------------------------------------------------------------------------------------
//
// 將64位浮點(diǎn)數(shù)轉(zhuǎn)換為32位整數(shù)
// 小數(shù)部分將四舍五入到偶數(shù)
//
inline void RoundToInt64 (int &val, double dval)
{
static double magic = 6755399441055744.0;
dval += magic;
val = *(int*)&dval;
}
----------------------------------------------------------------------------------------
快，這就是它最偉大的地方！你所需要的僅僅是一次浮點(diǎn)數(shù)加法，你還能再奢望些什么呢？

當(dāng)然，絕對不要使用莫名其妙的代碼，現(xiàn)在馬上就讓我們來看看它是怎么變的戲法。

首先，我們要搞清楚FPU是怎樣執(zhí)行浮點(diǎn)數(shù)加法的。考慮一下8.75加2^23。8.75的二進(jìn)制表示是1000.11，轉(zhuǎn)化為IEEE標(biāo)準(zhǔn)浮點(diǎn)數(shù)格式是1.00011*2^3。假設(shè)二者均是32位的float，它們在內(nèi)存中的存儲為：
----------------------------------------------------------------------------------------
符號位(31), 指數(shù)(30-23), 尾數(shù)(22-0)

8.75: 0, 10000010, 0001 1000 0000 0000 0000 000

2^23: 0, 10010110，0000 0000 0000 0000 0000 000
----------------------------------------------------------------------------------------
FPU所執(zhí)行的操作是：(1)提升指數(shù)較小者的指數(shù)，使二者指數(shù)相同；(2)將二者的尾數(shù)相加；(3)將結(jié)果規(guī)整為標(biāo)準(zhǔn)格式。讓我們具體來看看整個(gè)過程：
----------------------------------------------------------------------------------------
1，提升8.75的指數(shù)，尾數(shù)要相應(yīng)地右移23-3=20位：

8.75 = 1.00011*2^3 = .0000000000000000000100011*2^23

2，將二者相加。必須注意的是，
   由于float只有23位尾數(shù)，所以8.75的低位被移除掉了：

8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 +
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 =
0, 10010110, 0000 0000 0000 0000 0001 000

3，將規(guī)整為標(biāo)準(zhǔn)格式：

別忘了2^23還有個(gè)前導(dǎo)1，所以結(jié)果是規(guī)整的，無需執(zhí)行任何操作
----------------------------------------------------------------------------------------
你發(fā)現(xiàn)什么了嗎？不錯(cuò)，將結(jié)果的尾數(shù)部分提取出來，正是int(8.75)！是的，magic number的奧妙就在這里，通過迫使FPU將尾數(shù)移位，從而獲得我們需要的結(jié)果。

但是別高興得太早，讓我們來看看負(fù)數(shù)的情況。以-8.75為例，-8.75加2^23相當(dāng)于2^23減去8.75，過程如下：
----------------------------------------------------------------------------------------
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 -
8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 =
0, 10010110, 1111 1111 1111 1111 1110 000
----------------------------------------------------------------------------------------
很好，尾數(shù)部分正是int(-8.75)=-8的補(bǔ)碼。然而，2^23的前導(dǎo)1在減法過程中被借位了，所以結(jié)果的尾數(shù)前面并沒有1，F(xiàn)PU將執(zhí)行規(guī)整操作，最后我們得到的是：
----------------------------------------------------------------------------------------
0, 10010110, 1111 1111 1111 1111 1100 000
----------------------------------------------------------------------------------------
功虧一簣！等等，如果將2^23的尾數(shù)的最高位置1，那么在減法過程中不就可以保全前導(dǎo)1了嗎？完全正確，這就是我們需要的。所以最后的magic number是0,10010110,1000 0000 0000 0000 0000 000，也就是1.5*2^23。

然而，我們要清楚這個(gè)方法的一些局限性。首先，在將結(jié)果的float值保存為整數(shù)時(shí)，我們需要使用某些mask值將22-31位屏蔽掉。其次，float只能保有最多23位的有效值，在將尾數(shù)最高位置1后，有效值更是降到了22位，這意味著我們對大于2^23-1的數(shù)值無能為力。

相比之下，如果我們只處理double，那么所有的問題就都迎刃而解了。首先，double的指數(shù)位，符號位和尾數(shù)的最高位全部都在高32位，無需屏蔽操作。其次，double有多達(dá)52位的尾數(shù)，對于32位的int來說，實(shí)在是太奢侈了！

用于double的magic number是1.5*2^52=6755399441055744.0，推導(dǎo)過程是一樣的。

根據(jù)同樣的原理，我們還可以計(jì)算出將float和double轉(zhuǎn)化為定點(diǎn)數(shù)的magic number。例如對于16-16的定點(diǎn)數(shù)，尾數(shù)右移的位數(shù)比原先轉(zhuǎn)化為整數(shù)時(shí)要少16，所以對于double來說，相應(yīng)的magic number就是1.5*2^36。如果要轉(zhuǎn)化為8-24的定點(diǎn)數(shù)，則移位次數(shù)要少24，magic number是1.5*2^28。對于其他格式的定點(diǎn)數(shù)，以此類推。比起int(float_val*65536)這樣的表達(dá)式，無論是速度還是精度都要優(yōu)勝得多。

另外，不得不再次重申的是，對于在最后的結(jié)果中被移除掉的數(shù)值，F(xiàn)PU會將其四舍五入到偶數(shù)。然而，有時(shí)我們確實(shí)需要像floor和ceil那樣的操作，那該怎么辦呢？很簡單，將原數(shù)加上或減去一個(gè)修正值就可以了，如下所示：
----------------------------------------------------------------------------------------
// 修正值
static double magic_delta=0.499999999999;

// 截取到整數(shù)
inline void Floor64 (int &val, double dval)
{
RoundToInt64(val,dval-delta);
}

// 進(jìn)位到整數(shù)
inline void Ceil64 (int &val, double dval)
{
RoundToInt64(val,dval+delta);
}
----------------------------------------------------------------------------------------
這個(gè)世界上沒有免費(fèi)的午餐。我們獲得了速度，相對應(yīng)地，也必須付出一些代價(jià)，那就是可移植性。上述方法全都基于以下幾個(gè)假設(shè)：(1)在x86上跑；(2)符合IEEE的浮點(diǎn)數(shù)標(biāo)準(zhǔn)；(3)int為32位，float為32位，double為64位。局限性其實(shí)是蠻大的，相比之下，int_val=(int)float_val就要省事多了。當(dāng)然，你也可以使用條件編譯。

最后，讓我們來看兩組實(shí)際的測試數(shù)值。這份報(bào)告來自于Sree Kotay和他的朋友Herf：
----------------------------------------------------------------------------------------
平臺：Pentium IV/1.2

64位浮點(diǎn)數(shù)到32位整數(shù)的轉(zhuǎn)換：

int(f)：        2772.65 ms
fistp：         679.269 ms
magic number：  622.519 ms

64位浮點(diǎn)數(shù)到16-16定點(diǎn)數(shù)的轉(zhuǎn)換：

int(f*65536)：  2974.57 ms
fistp：         3100.84 ms
magic number：  606.80 ms

floor函數(shù)：

ANSI floor：    7719.400 ms
magic number：  687.177 ms
----------------------------------------------------------------------------------------
平臺：Pentium D/3.2

64位浮點(diǎn)數(shù)到32位整數(shù)的轉(zhuǎn)換：

int(f)：        1948.470 ms
fistp：         523.792 ms
magic number：  333.033 ms

64位浮點(diǎn)數(shù)到16-16定點(diǎn)數(shù)的轉(zhuǎn)換：

int(f*65536)：  2163.56 ms
fistp：         7103.66 ms
magic number：  335.03 ms

floor函數(shù)：

ANSI floor：    3771.55 ms
magic number：  380.25 ms
----------------------------------------------------------------------------------------
性能的差距實(shí)在令人驚訝，不是嗎？我想說的是，寫編譯器的家伙絕對不是傻瓜（恐怕比你我都要聰明得多），他們當(dāng)然知道所有這些優(yōu)秀的算法。但為什么編譯器的表現(xiàn)會如此糟糕呢？其中一個(gè)理由是，為了使浮點(diǎn)數(shù)運(yùn)算盡可能精確和迅速，IEEE在算法的選擇上有很多的限制。而另一方面，IEEE的舍入規(guī)則（四舍五入到偶數(shù)）盡管從維持浮點(diǎn)數(shù)的連貫性上來看非常棒，但卻不符合ANSI C在浮點(diǎn)數(shù)到整數(shù)的類型轉(zhuǎn)換上的說明（截尾）。于是，編譯器不得不做一大堆的工作來保證行為的正確性（符合標(biāo)準(zhǔn)）。這在大部分情況下都不是什么問題——除非你在寫圖形/聲音/多媒體之類的代碼。

剛剛在我的賽揚(yáng)1.1G上實(shí)際測試了一下。編譯器是VC2003，使用PerformenceCounter來計(jì)算時(shí)間，在DEBUG模式下，C標(biāo)準(zhǔn)轉(zhuǎn)換/FISTP/MagicNumber三種方法所耗費(fèi)時(shí)間的比約為5/3/2。但在優(yōu)化全開的RELEASE模式下，標(biāo)準(zhǔn)C類型轉(zhuǎn)換的速度卻是遙遙領(lǐng)先于所有其他的方法！也不知道是我的測試方法有問題，還是該贊VS厲害。
--------------------------------------------------------------------------------------
參考文獻(xiàn)和相關(guān)資源可到鄙人的小店下載：http://greatsorcerer.go2.icpcn.com/info/float2int.html

1，What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg（PDF）：
這篇論文囊括了關(guān)于浮點(diǎn)數(shù)的所有東西，正如其名字所示，任何想要了解浮點(diǎn)數(shù)的人都必讀的文獻(xiàn)。（其中關(guān)于精度的討論實(shí)在令我受益非淺。） 

2，Let's Get to The Floating Point by Chris Hecker（PDF）：
早期的關(guān)于浮點(diǎn)數(shù)的文章，寫得非常棒，值得一看。
 
3，IEEE Standard 754 for Binary Floating Point Arithmetic by Prof.W.Kahan（PDF）：
關(guān)于IEEE754標(biāo)準(zhǔn)的說明。 

4，IA64 Floating Point Operations and the IEEE Standard for Binary Floating Point Arithmetic（PDF）：
關(guān)于IA64的浮點(diǎn)數(shù)實(shí)現(xiàn)。 

5，Know Your FPU: Fixing Floating Fast by Sree Kotay