本文的核心內(nèi)容源自于Henry S. Warren的《Hacker's delight》，記錄于此贤惯，僅作為教學(xué)之用洼专。貢獻(xiàn)歸于原作者。
初學(xué)二進(jìn)制的時候孵构，老師喜歡問一個問題屁商，為何二進(jìn)制很重要？同學(xué)們喜歡這么回答：因?yàn)槎M(jìn)制非常有趣颈墅、容易理解而且更加高效蜡镶！我非常清楚雾袱，對他們而言，二進(jìn)制并不有趣帽哑，也不容易谜酒，更為重要的是，他們不知道什么進(jìn)制更加高效妻枕。原諒我的夸張僻族，大多數(shù)人（包括學(xué)計(jì)算機(jī)數(shù)十年的老手）也不見得知道什么進(jìn)制最高效。因?yàn)槁判常蠋煆膩聿唤淌雒矗覇?strong>這樣的問題有意思嗎？嗯哼愕掏，看看下面的分析再下結(jié)論吧度秘。
首先，我們先定義電路的開銷饵撑。二進(jìn)制有兩種狀態(tài)剑梳，如果把二進(jìn)制電路的開銷定為2（兩個單位開銷），那么三進(jìn)制有三種狀態(tài)滑潘，開銷就是3垢乙，四進(jìn)制有四個狀態(tài)則開銷就是4。因此语卤，我們可令b進(jìn)制電路的開銷為b追逮。
其次，b進(jìn)制如果要表達(dá)0到M范圍的值需要log_b( M + 1 )（即粹舵，以b為底對M+1求對數(shù)）這么多電路钮孵。比如，如果是二進(jìn)制要表達(dá)0-255眼滤，則需要log( 256 ) = 8個比特巴席。 又比如，用十進(jìn)制表示0-999需要log_10(1000)=3個十進(jìn)制數(shù)柠偶。
接著情妖，就可以定義表達(dá)這M+1個數(shù)所使用電路的開銷，簡單的乘法得:
c = k*log_b(M+1)*b （公式1）
其中诱担，k是一個比例常數(shù)毡证，暫時可以忽略其意義。
然后蔫仙，就需要使用一點(diǎn)點(diǎn)高等數(shù)學(xué)的知識了料睛。把c理解為b的函數(shù)，該函數(shù)會在導(dǎo)數(shù)為零處達(dá)到極值，因此恤煞，要對c進(jìn)行求導(dǎo)屎勘。有一個技巧就是，先對log_b(M+1)進(jìn)行換底（高中的換底公式?jīng)]有忘記吧居扒，剛高考完的大一新生們概漱？）得到以e為底的自然對數(shù)表達(dá)：ln (M+1) / ln b。其好處還是明顯的喜喂，把M+1這一項(xiàng)獨(dú)立出來瓤摧。運(yùn)用鏈?zhǔn)椒▌t，整理得：
c‘ = k*ln (M+1) * (ln b - 1 )/ (ln b)^2
該公式在ln b - 1時為0玉吁，即 b為e （2.718照弥，歐拉常數(shù)，又稱納皮爾常數(shù)进副，我最近才知道這個名字这揣。）時為零。因此影斑，三進(jìn)制是最高效的進(jìn)制给赞。
最后，二進(jìn)制與三進(jìn)制差別有多大呢矫户？使用公式1塞俱，很容易算：
c(2) : c(3) = 2*ln 3 : 3*ln 2 = 1.056
結(jié)論是，二進(jìn)制比三進(jìn)制稍微開銷大那么一點(diǎn)點(diǎn)吏垮。如果結(jié)合二進(jìn)制電路在實(shí)現(xiàn)上的優(yōu)勢，這點(diǎn)開銷也許就可以忽略不計(jì)罐旗。
以上分析展示了一種分析問題解決問題的典范實(shí)例膳汪，可推廣稱為通用方法，值得學(xué)習(xí)九秀。就結(jié)論本身而言遗嗽，也許還不如提出問題更有價值。
本文的分析源自于Henry S. Warren的《Hacker's delight》鼓蜒，目前是第二版痹换，有中文翻譯版（不建議購買），值得閱讀都弹，是一本內(nèi)涵深刻的算法書娇豫，盡管名字有點(diǎn)古怪。
2017年6月整理
