漫话进位制

    人有十个手指,用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了,手指头就不够用了。当然,有人会想到还有脚趾头。搬弄脚趾头是不现实的,数手指头只需要站着比划一下就可以了,数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记,比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”,它相当于十个指头。这样,我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈,你的MM数只有两根木棒加4个手指头,于是我的MM比你的多。久而久之,人们就只接受0到9这十个数字了,再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢?那我们现在很可能正在使用八进制,数学发展起来后我们最终只接受八个数字,而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号,这里为了便于叙述,我们仍然使用阿拉伯数字的0到7来表示。于是,人类数数的方式将变为:0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,…。这里,数字8被记作10,数字64则用100代替。在这个数学世界里,6+5=13,因为6+1得到的数已经是一位数中最大的了,再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指,12进制将成为更难想像的事。在12进制中,人类会把10和11直接想成是一个“数字”。研究的进位制大于10时,大于9的数字我们习惯上用大写字母ABC来表示。这样,自然数序列里将多出两个符号A和B来,数数的方式变为…,8,9,A,B,10,11,12,…。

    我们自然会想,人类生活中究竟有没有其它的进位制呢?当然有。比如,时间和角度就是60进位制,60秒=1分。还有更怪的,计算机的储存容量单位是1024进制的,1MB=1024KB。当然,这也是有原因的。我们在研究几何时常常需要用到1/2,1/3,1/4或者1/6,我们希望这些分数在角度进制下恰好都是整数以便于运算。于是,角度的进位制就变成了60。为什么时间也是60进位制呢?因为时间和角度密切相关,你看看你的手表就知道了(别告诉我你的手表是数字型的)。为什么钟和手表又要用圆形表盘的方式来表示时间呢?其实人自古以来计算时间都是用的圆形盘面,因为地球绕太阳旋转和地球的自转使得时间具有了周期性。
    计算机使用二进制,因为计算机元件只有两种状态(开和关,或者说通电和断电),因此计算机只认0和1两个数字。1024是2的幂,又比较接近1000符合人的习惯,因此把1024当成了计算机容量的进位制。

    前段时间有人在OIBH上问,为什么纸币的面值都是1*10^n、2*10^n、5*10^n呢。有人回答说这样的货币系统可以使得某种贪心方法正确。确实有这个结论,这样的货币系统使得解决“凑钱和找零时最少使用多少张纸币”这一问题的贪心算法(不断拿最大面额的纸币)是正确。但用这一点来解释我们的问题显然是可笑的,人们首先考虑的并不是如何方便地使用最少纸币,而是如何方便地得到总面额。一个只有1元纸币和7元纸币的货币系统同样满足贪心性质,但显然傻子才会设计出这种别扭的货币系统来。因此,我的回答是“纸币的面值取10的约数,这样的话凑钱和找零最方便”。但是,有人会问,要是我们使用的进位制不是10怎么办?换句话说,如果我们使用的是23进位制,除1和本身外没有其它约数的话,又该怎样设置货币系统呢。答案非常出人意料,如果我们使用的是23进位制的话,我们很可能根本发展不出数学这门学科来。10=1+2+3+4,是前四个正整数的和;10又是2和5的积;这样的进位制非常适合数学的发展。同样地,6=1+2+3,6=2*3,因此可能正在使用六进制的昆虫们很容易发展出数学来(六足动物的数学非常强,不是有人发现了蜜蜂蜂巢的六边形样式设计是最科学的么)。大家看过《计算机中的上帝》(Calculating God)吗?那里面构造了这样一种生物:他有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体,除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的困难。而事实上,这种生物恰好又没有发展数学的必要性。他就好像人类一样,对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说,如果你眼前有3个,或者5个东西,你不需要数,看一眼就知道有多少个;但当你眼前出现的物体数目达到7个或者8个时,你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来,数目超过46后就统称为“很多”了。直接感知数目达到50甚至60多的生物个体就扮演着该种族中的僧侣角色。46这个数字对于种族的生存已经完全足够了,他们在组建部落时总会保证部落的个体数不超过这个数字。因此,这种生物不需要数数的能力,他们也就无须发展数学了。他们不知道30加30等于多少,从某种意义上说他们甚至不知道一加一等于几,因为他们头脑中根本没有数字这个概念。作为一种补偿,他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论,因为他们的思维不受演绎逻辑的束缚。

    下文将介绍两套进制转换的方法,然后介绍这两套方法在小数转换上的应用。更多的进位制相关应用你可以在文后的习题部分中体会到。

    在讲进位制时,大多数教材会教大家二进制和十进制如何互换。今天我就偏不这样讲,我要和那些教材讲得一样了我还不如不写今天这些东西。二进制虽然常用,但比较特殊,很可能会了二进制但仍然不会其它进制;我们今天当一回蜜蜂,看看六进制和十进制怎么互相转换。学会这个后,任意进制间的转换你就应该都会了。
    说起进位制时往往要回到最根本的一些计数方法上。这篇日志是我第237篇日志。数字“237”表示两个百,加上三个十,加上七个单位一。我们把它们分别叫百位、十位和个位,同一个数字在不同数位上表示的实际数量不同。用一个式子表示上面的意思就是,237=2*100+3*10+7。这就是进位制的实际意义。
    现在,假如我是一只勤劳的蜜蜂。我写237篇日志是肯定不可能的了,因为我的数学世界里根本没有7这个数字。那就说我写了235篇日志吧。结合前面所说的东西,“十位”上的数表示有多少个6,“百位”上的数表示有多少个36(后面提到的十位、百位打引号表明这不是十进制中的“十”和“百”)。于是,六进制下的235就应该等于2*6^2+3*6+5。这个算式你用什么进制算出答案就相当于把六进制中的235转换为了什么进制。不过你要把这个式子当成别的进制算是不大可能的,算之前你估计得重新背一遍乘法口诀表(注意我为什么不说是“九九”乘法口诀表)。这就是我们为什么一般只研究十进制与其它进制互换的原因。我们用熟悉的十进制进行计算,得出2*6^2+3*6+5=72+18+5=95。这是按定义进行进制转换的方法。六进制的235等于十进制的95,我们记作(
235)6=(95)10。那个6和10是下标,应该像H2O的2一样小小地写在下面。我就懒得排版了,反正转贴个几次就成Plain Text了。
    下面的任务是,考虑怎么把(95)10变回(235)6。使用六进制计算13*10+5可以得到235(十位上的9相当于六进制中的13),但我们说过六进制计算很麻烦。下面我们给出一种把十进制转换为六进制的方法,仔细思考你会发现这种方法显然是正确的。我们把所有6的幂从小到大写出来:1,6,36,216,…。216远远超过95了,因此95的六进制不可能是四位数。95里面有两个36,因此在最高位上写个“2”。去掉两个36,95里只剩23。23里有三个6,数字3将填写在第二位上,去掉这三个6最后所剩的5留给最末位。换句话说,我们不断寻找最大的x使得6^x不超过当前数,当前数减去6^x并在右起第x+1位上加一。这事实上是前面六进制转十进制的逆过程。
    上面的进制互换方法是一套方法,这是我们所介绍的第一套方法。这套方法的特点是正确性很显然,但是计算比较复杂,又费马达又费电。我们需要一个计算更方便的进制转换方法。下面介绍的就是进制转换的第二套方案。

    再一次回到一个很基础的问题:在十进制中,为什么乘以10相当于在数的末尾加一个0?我们同样会联想到位运算:为什么二进制左移一位(末尾加一个0)相当于乘以2?事实上,这个结论普遍存在于所有进位制中:k进制数的末尾加个0,相当于该数乘以k。证明方法非常简单,乘以一个k就相当于进位制展开式的每个指数都加一,也就相当于所有数字左移一位。六进制235=2*6^2+3*6+5,乘以6的话式子将变为2*6^3+3*6^2+5*6,也即2350。利用这个性质,六进制235可以很快转为十进制:235相当于2后面添0,加上3,再添一个0,再加上5,写为算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展开来,得到的式子和前面的那种计算方法(2*6^2+3*6+5)一模一样,但这里的计算方式更简便一些。如果写成程序,六进制字符串t转为十进制数a只需要一句话就可以完成:
for i:=1 to length(t) do a:=a*6+ord(t[i])-48;
    使用这种方法将十进制变回六进制是一个彻头彻尾的逆向操作:当前数不断除以6并把余数作为新的最高位。比如,95除以6等于15余5,余数5就是个位,15除以6的余数3作为“十位”,最终的商2是“百位”。这叫做短除法,是最常见的方法,网上随处可见。

    下面说一下进位制中的小数。前面的东西如果理解了,小数进制的转换将顺理成章地进行下去。六进制中的0.1相当于十进制的1/6,因为六进制中的0.1、0.2、0.3、0.4、0.5五个数把区间0到1均分为了6分。同样地,(0.05)6=(5/36)10。你会发现,一个“十分位”代表1/6,一个“百分位”代表1/6^2,之前的很多结论仍然成立。六进制小数12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3),通过负指数把进制转换的整数部分和小数部分联系在了一起。(12.345)6转为十进制后居然变成了无限小数,其实这并不奇怪,这只是一个约数的问题:同样是三分之一,在我的六进制下正好分干净(0.2),但在你十进制下就总也分不完,总要剩一点留给下一位(0.333333…)。这里有一些小数进制转换的实例。可以看到,一个进制下的有限小数很可能是另一个进制下的无限循环小数。另一个有趣的例子在这里
    既然前面所说的第一套方法中六进制转十进制对于小数仍然成立,那么第一套方法的十进制转六进制也可以直接在小数上使用。如果你嫌无限小数很别扭,用分数进行操作是一种不错的选择。具体操作方法和前文叙述一模一样。针对纯小数的进制转换,我们把前文的描述换种方法再说一遍:不断寻找最小的正整数x使得1/6^x不超过当前数,当前数减去1/6^x并在小数点后第x位上加一。我就不再举例子了,下面主要讨论第二套方法在小数上的应用。
    我们曾说过,在k进制末尾加0相当于该数乘以k。可惜这对小数没有用,小数后你加它八百个“0”这个数仍然不变。其实,“末尾加0”只是这种性质反映在整数上的一种现象而已,我们还需要看到更本质的东西(还记得高二哲学么)。考虑到小数的乘k和除k,不难想到这种性质的实质是小数点的移动,整数的末尾加0其实是小数点向右移动一位的结果。显然小数也有类似的结论:将k进制小数的小数点左移一位,相当于该数除以k。比如,十进制中3.14除以10就变成了0.314。结论的证明和原来完全相同:除以k后展开式中的指数全部减一,相当于所有数右移一位。有了这个结论,我们的方法就出来了。来看六进制12.345如何转换为十进制。由于这种方法对整数和小数的处理方法有一些不同,转进制时我们通常对整数部分和小数部分分别进行操作。先把12转成十进制的8,然后单独考虑小数部分。0.345可以看作是数字“5”的小数点左移,加上4后小数点再次左移,再加上3并最后一次左移小数点;写成算式即((5/6+4)/6+3)/6。展开这个式子,实质与前面的方法仍然一样。小数部分十进制转六进制依然是彻头彻尾的逆向操作:当前数不断乘以6并取出整数部分写下来。
    这里有一个实例供大家参考,这个例子中的进制转换保证不涉及无限循环小数。1/4在十进制和六进制下的表示肯定都是有限小数,因为4的唯一一个因子2同样也是10和6的因子。先看0.25怎么变成六进制:0.25*6=1.5,取出1,留下0.5;0.5*6=3,没有小数部分了,因此(0.25)10就等于(0.13)6。现在我再把它变回去:(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。这不是彻头彻尾的逆操作吗?

    每年NOIp前总有人问负进位制。事实上,如果你搞清了上面的问题,负进位制将非常好理解。负进位制有一个非常奇特的功能:它可以表示出负数但不需要用负号。一个负进制数可能是负数,也可能是正数。比如,负六进制下的12等于十进制下的-4,而负六进制下的123等于1*(-6)^2+2*(-6)^1+3,即十进制下的27。是正是负取决于位数的奇偶:若该数有偶数位,则该数为负数;若有奇数位,则该数为正数。原因很简单,小数点每右移一位,相当于这个数乘以-6;从一位数开始,乘奇数次后该数的位数变成偶数且值为负,乘偶数次该数仍有奇数位且值仍为正。由于末尾添0的性质(小数点移位的性质)仍然成立,负六进制与十进制的转换依然是上面的方法:(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十进制转负六进制?还是那句话:彻头彻尾的逆操作。找到最小的非负整数x使得当前数减x能被6整除,这个x将作为新的最高位写到结果中,然后当前数减去x再除以-6。在这里我不说“余数”这个词,因为当除数为负数时对余数的定义很模糊。不再举例子了,例子都举烦了,自己把(123)-6=…=(27)10那一行倒过去看就是例子了。
    当然,还有更神奇的:-1+i进制可以表示出复数来,因为-1+i的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样,我也就不多说了。

    进位制的问题结束了。我们这里是以六进制为例进行的说明,但是不要忘