二进制数转十进制优化算法探讨

欧海飞

文章编号：2095-6835（2016）07-0094-02

摘 要：叙述了数制转换的基本方法，说明了二进制数转十进制算法的基本思路，并提出了一种优化算法，解决了传统算法中运行效率低的问题。另外，还详细分析了优化算法的实现方法，通过比较测试数据展现出这种算法的优越性。

关键词：二进制；十进制；优化算法；运行效率

中图分类号：TP332.2 文献标识码：A DOI：10.15913/j.cnki.kjycx.2016.07.094

目前，二进制数被广泛应用于计算机系统中。在当前的自动化控制系统中，无不以二进制数为核心。在数据采集、传输、交换、运算、录入和输出等所有环节中，均使用二进制数。然而在现实生活中，信息交流大多使用的是十进制，因而在机器与人之间则涉及到了数制转换问题。随着处理器技术的不断发展，这些数制转换早已不是问题。但是，在一些小型嵌入式系统中，通常将单片机作为主控处理器。因为其运算性能有限，如果需要频繁地转换数制，则会影响系统的正常运行。

本文简要探讨了基于MCS-51指令系统的微处理器作数据转换算法的相关内容，分析了二进制转十进制的思路，并提出了一种新算法。经过对比，结果表明，此算法具有较高的运行效率和较强的实用性。

1 二进制数转十进制的基本方法

二进制转十进制的基本方法是使用除法运算。以双字节的16位二进制整数为例，在C51编译器中将其定义为unsigned int数据类型，其取值范围为 0～65 535（十进制表示），或0x0000～0xffff（十六进制表示）。由此可见，其最大值占用十进制数的五位，分别为个、十、百、千、万位。在KEIL C51集成开发系统中，可以编写适当的C程序，实现二进制数到十进制数的转换。一个典型的例子如图1所示。

这是我们常用的一种方法，把待转换的16位二进制数x除以10 000，结果的整数部分即为十进制的万位，然后以x以10 000为模取余数，再除以1 000，得出结果的整数部分为十进制的千位，依次类推，即可算出百位、十位和个位。

这种算法的原理很简单，在此不再赘述。将这个程序用KEIL C51编译仿真运行，可以得到正确的运算结果，但是，，执行上面的代码程序所需的运行时间为994个时钟周期。经过相关分析可知，这一段程序中需要进行4次16位整数的除法和4次16位整数求余运算。标准的51内核单片机为8位机，其16位乘法、除法、求模运算的处理效率很低。在计算过程中，该程序段多次调用KEIL C51自带的16位除法运算库函数“C？UIDIV”，消耗了大量的MCU运行时间。

查看程序1不难发现，当执行语句“x=x% 100”后，x的取值必然小于100.因此，在最后两语句中，求十位和个位的运算不必采用unsigned int数据类型进行运算，可将其强制转换为unsigned char数据类型，以加快处理速度。标准MCS-51单片机内核支持8位乘/除法运算指令，可以高效地进行8位的乘/除法运算。程序1修改后如图2所示。

通过仿真运行可知，此次运行时间为959时钟周期，处理效率略有改善，但是，仍然没有明显提升。这是因为程序仍需要进行6次16位除法/求余运算。

因此，再变通一下，改变一下运算次序，先用x除以1 000，结果暂存于1个临时变量temp中，temp的值代表x包含多少个1 000.至此不难得出，temp取值范围为0～65，可以用1个unsigned char数据类型表示。如果对temp分别进行除10和求余运算，即可得出万位和千位数据。具体程序如图3所示。

程序3与程序2相比，减少了2次16位的除法/求余运算。由编译仿真测试结果可知，这一次运行时间减至666时钟周期。

由一系列的测试结果可知，程序耗时最多的是16位除法/求余的运算，而避免16位数据运算是提高运行效率的有效方法之一。仔细分析程序3可知，再减少16位运算的次数是难以实现的，要想进一步提高其效率，只能改变方式，运用其他算法达到提高效率的目的。

2 优化算法的研究

1个16位的二进制数可以拆解为两部分，即高6位和低10位。现在只考虑高6位部分，我们知道，210=1 024=1 K，这个“K”的单位比十进制数的“千”多了一点点，所以，可以近似认为“K”就是“千”。当1个16位的二进制数转换为用“K”作单位时，就可以近似得出它对应的十进制数中有几个“千”。将二进制数转换为用“K”表示的过程很简单，只需把16位的二进制数低10位截去，剩余的6位二进制数字就表示有多少个“K”。举例说明：

0b 000100 0000000000=4，096；

0b 100000 0000000000=32，768；

0b 101001 0000000000=41，984.

在这3个等式中，左侧二进制数的高6位数值刚好就是右侧十进制数千位和万位的数值。也就是说，只要把二进制数高6位转换为十进制，即可求得千位和万位的结果。不过，当二进制数高6位的数值大于0b 101001（十进制41）时，对应的十进制数千位要多加1。这是因为二进制1 K比1 000多24的尾数累计结果。

按照这个思路，用C程序可以实现任意16位二进制数x的高6位部分的转换。通过简单的运算很容易得到万位和千位的转换结果，即：

i = x >> 10； //舍弃低10位，取高6位

if （i > 41） i++； //超出41需加1修正

wan = i / 10； //计算万位

qian = i % 10； //计算千位

之前的运算只涉及8位除法/求余运算，并不需要16位运算，因而效率较高。在此需要注意的是，当前i取值不是最终结果，考虑到x的低十位转换过程可能产生进位的情况，i的值将在之后的处理过程中修正。

现在考虑低10位的转换方法，由于前面千位用近似的1 K表示，每个1 K比1 000多了24，多出部分需累加到低10位的数值中。假如低10位数值用j表示，数值j应作累加运算，即：

j = x & 0x3ff； //取低10位

j = i * 24 + j； //累加i*24

考虑j的取值为 0～1 023，超出了1个字节范围，不便于8位机处理，所以，可把j的低二位忽略，只取高8位，则其数值相当于缩小了4倍，使其值在256以内，进而用unsigned char类型表示，也便于计算。这个过程可表示为：

j = （x>>2）； //只取x的2～10位

j = i * 6 + j； //累加i*6

在此需要注意的是，这里的i*24改为i*6是因为j缩小了4倍，因而i*24也同样缩小4倍。同时，j经过累加运算后，运算结果可能会超出8位范围，所以，需检测进位标志CY来判定是否溢出。一旦溢出，则表示j的取值大于255，也就意味着低10位累加结果大于1 023，因而需向i进位（1 000），并让j扣减250（1 000/4）。此运算过程为：

if （CY == 1） //判定是否有进位

{

i++；

j += 6； //对于8位运算，加6与减 250 等效

}

j经过加6运算后，仍有可能大于或等于250.也就是说，低10位数值大于等于1 000.如果它为真，则需要再一次向i进位，即：

if （j >= 250） //判定是否需进位

{

i++；

j += 6； //对于8位运算，加6与减 250 等效

}

经过2次累加，现在可以保证j的值在250以内。也就是说，低10位数值小于1 000.同时，i取值也经过修正得到正确值，并可据此求出最终的万位、千位数值，即：

wan = i / 10； //计算万位

qian = i % 10； //计算千位

至此，可以计算十进制数的百位、十位和个位。在计算百位时，只要把低10位的数据除以100，即可得出结果。但是，1 000以内的数值除以100仍得按16位除法运算。变通一下，现在j的取值是低10位数值缩小4倍（忽略低2位）的结果，所以，低10位数值除以100，等效于j/25，即可避开16位除法运算，使用8位除法达到目的。于是有：

bai = j / 25； //计算百位

剩余的十位、个位计算比较容易，只需把j对25求余，然后重新扩大4倍，并与最低两位相加，即得100以内的尾数。具体计算是：

j = （j % 25） * 4 + （x & 3）； //计算模100余数

最后，可以计算十位与个位数值了，即：

shi = j / 10； //计算十位

ge = j % 10； //计算个位

到此为止，个位、十位、百位、千位、万位已经全部计算完毕。计算过程稍微有些复杂，但是，在整个计算过程中，没有使用16位除法/求余运算，所以，程序运行速度比较快。将文中全部的计算过程整理好，得到的程序如图4所示。

将程序4进行编译仿真测试，得出运行时间为101时钟周期，比程序1、程序2和程序3快了6～9倍。由此可知，运用此算法后，运行速度明显提升。另外，针对KEIL C51的编译器和标准51内核的结构，利用内部寄存器B还可以进一步优化程序，但是，程序的可移植性将变差。优化后的程序如图5所示。

试运行程序5，测试结果表明，经过优化的程序只需要72时钟周期，而且有效加快了运行速度。

3 结束语

算法往往是决定程序运行效率的最重要因素，好的算法可以让低配置的系统获得高性能。本文提及的改进算法只是一个特例，在不同的硬件架构、不同的编译环境中，实现的方法也不相同。因此，在工作过程中，程序设计员需要根据不同系统的特点，寻求合适的最优算法，充分发挥系统的性能。

〔编辑：白洁〕