CSI讲义3--最高效的进制是什么？

本文的核心内容源自于Henry S. Warren的《Hacker's delight》，记录于此，仅作为教学之用。贡献归于原作者。

初学二进制的时候，老师喜欢问一个问题，为何二进制很重要？同学们喜欢这么回答：因为二进制非常有趣、容易理解而且更加高效！我非常清楚，对他们而言，二进制并不有趣，也不容易，更为重要的是，他们不知道什么进制更加高效。原谅我的夸张，大多数人（包括学计算机数十年的老手）也不见得知道什么进制最高效。因为，老师从来不教，而且问这样的问题有意思吗？嗯哼，看看下面的分析再下结论吧。

首先，我们先定义电路的开销。二进制有两种状态，如果把二进制电路的开销定为2（两个单位开销），那么三进制有三种状态，开销就是3，四进制有四个状态则开销就是4。因此，我们可令b进制电路的开销为b。

其次，b进制如果要表达0到M范围的值需要log_b( M + 1 )（即，以b为底对M+1求对数）这么多电路。比如，如果是二进制要表达0-255，则需要log( 256 ) = 8个比特。 又比如，用十进制表示0-999需要log_10(1000)=3个十进制数。

接着，就可以定义表达这M+1个数所使用电路的开销，简单的乘法得:
c = k*log_b(M+1)*b （公式1）
其中，k是一个比例常数，暂时可以忽略其意义。

然后，就需要使用一点点高等数学的知识了。把c理解为b的函数，该函数会在导数为零处达到极值，因此，要对c进行求导。有一个技巧就是，先对log_b(M+1)进行换底（高中的换底公式没有忘记吧，刚高考完的大一新生们？）得到以e为底的自然对数表达：ln (M+1) / ln b。其好处还是明显的，把M+1这一项独立出来。运用链式法则，整理得：
c‘ = k*ln (M+1) * (ln b - 1 )/ (ln b)^2
该公式在ln b - 1时为0，即 b为e （2.718，欧拉常数，又称纳皮尔常数，我最近才知道这个名字。）时为零。因此，三进制是最高效的进制。

最后，二进制与三进制差别有多大呢？使用公式1，很容易算：
c(2) : c(3) = 2*ln 3 : 3*ln 2 = 1.056

结论是，二进制比三进制稍微开销大那么一点点。如果结合二进制电路在实现上的优势，这点开销也许就可以忽略不计。

以上分析展示了一种分析问题解决问题的典范实例，可推广称为通用方法，值得学习。就结论本身而言，也许还不如提出问题更有价值。

本文的分析源自于Henry S. Warren的《Hacker's delight》，目前是第二版，有中文翻译版（不建议购买），值得阅读，是一本内涵深刻的算法书，尽管名字有点古怪。

Hacker's delight

2017年6月整理