二進(jìn)制數(shù)轉(zhuǎn)十進(jìn)制優(yōu)化算法探討

歐海飛

文章編號(hào)：2095-6835（2016）07-0094-02

摘 要：敘述了數(shù)制轉(zhuǎn)換的基本方法，說明了二進(jìn)制數(shù)轉(zhuǎn)十進(jìn)制算法的基本思路，并提出了一種優(yōu)化算法，解決了傳統(tǒng)算法中運(yùn)行效率低的問題。另外，還詳細(xì)分析了優(yōu)化算法的實(shí)現(xiàn)方法，通過比較測(cè)試數(shù)據(jù)展現(xiàn)出這種算法的優(yōu)越性。

關(guān)鍵詞：二進(jìn)制；十進(jìn)制；優(yōu)化算法；運(yùn)行效率

中圖分類號(hào)：TP332.2 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2016.07.094

目前，二進(jìn)制數(shù)被廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)中。在當(dāng)前的自動(dòng)化控制系統(tǒng)中，無不以二進(jìn)制數(shù)為核心。在數(shù)據(jù)采集、傳輸、交換、運(yùn)算、錄入和輸出等所有環(huán)節(jié)中，均使用二進(jìn)制數(shù)。然而在現(xiàn)實(shí)生活中，信息交流大多使用的是十進(jìn)制，因而在機(jī)器與人之間則涉及到了數(shù)制轉(zhuǎn)換問題。隨著處理器技術(shù)的不斷發(fā)展，這些數(shù)制轉(zhuǎn)換早已不是問題。但是，在一些小型嵌入式系統(tǒng)中，通常將單片機(jī)作為主控處理器。因?yàn)槠溥\(yùn)算性能有限，如果需要頻繁地轉(zhuǎn)換數(shù)制，則會(huì)影響系統(tǒng)的正常運(yùn)行。

本文簡(jiǎn)要探討了基于MCS-51指令系統(tǒng)的微處理器作數(shù)據(jù)轉(zhuǎn)換算法的相關(guān)內(nèi)容，分析了二進(jìn)制轉(zhuǎn)十進(jìn)制的思路，并提出了一種新算法。經(jīng)過對(duì)比，結(jié)果表明，此算法具有較高的運(yùn)行效率和較強(qiáng)的實(shí)用性。

1 二進(jìn)制數(shù)轉(zhuǎn)十進(jìn)制的基本方法

二進(jìn)制轉(zhuǎn)十進(jìn)制的基本方法是使用除法運(yùn)算。以雙字節(jié)的16位二進(jìn)制整數(shù)為例，在C51編譯器中將其定義為unsigned int數(shù)據(jù)類型，其取值范圍為 0～65 535（十進(jìn)制表示），或0x0000～0xffff（十六進(jìn)制表示）。由此可見，其最大值占用十進(jìn)制數(shù)的五位，分別為個(gè)、十、百、千、萬位。在KEIL C51集成開發(fā)系統(tǒng)中，可以編寫適當(dāng)?shù)腃程序，實(shí)現(xiàn)二進(jìn)制數(shù)到十進(jìn)制數(shù)的轉(zhuǎn)換。一個(gè)典型的例子如圖1所示。

這是我們常用的一種方法，把待轉(zhuǎn)換的16位二進(jìn)制數(shù)x除以10 000，結(jié)果的整數(shù)部分即為十進(jìn)制的萬位，然后以x以10 000為模取余數(shù)，再除以1 000，得出結(jié)果的整數(shù)部分為十進(jìn)制的千位，依次類推，即可算出百位、十位和個(gè)位。

這種算法的原理很簡(jiǎn)單，在此不再贅述。將這個(gè)程序用KEIL C51編譯仿真運(yùn)行，可以得到正確的運(yùn)算結(jié)果，但是，，執(zhí)行上面的代碼程序所需的運(yùn)行時(shí)間為994個(gè)時(shí)鐘周期。經(jīng)過相關(guān)分析可知，這一段程序中需要進(jìn)行4次16位整數(shù)的除法和4次16位整數(shù)求余運(yùn)算。標(biāo)準(zhǔn)的51內(nèi)核單片機(jī)為8位機(jī)，其16位乘法、除法、求模運(yùn)算的處理效率很低。在計(jì)算過程中，該程序段多次調(diào)用KEIL C51自帶的16位除法運(yùn)算庫函數(shù)“C？UIDIV”，消耗了大量的MCU運(yùn)行時(shí)間。

查看程序1不難發(fā)現(xiàn)，當(dāng)執(zhí)行語句“x=x% 100”后，x的取值必然小于100.因此，在最后兩語句中，求十位和個(gè)位的運(yùn)算不必采用unsigned int數(shù)據(jù)類型進(jìn)行運(yùn)算，可將其強(qiáng)制轉(zhuǎn)換為unsigned char數(shù)據(jù)類型，以加快處理速度。標(biāo)準(zhǔn)MCS-51單片機(jī)內(nèi)核支持8位乘/除法運(yùn)算指令，可以高效地進(jìn)行8位的乘/除法運(yùn)算。程序1修改后如圖2所示。

通過仿真運(yùn)行可知，此次運(yùn)行時(shí)間為959時(shí)鐘周期，處理效率略有改善，但是，仍然沒有明顯提升。這是因?yàn)槌绦蛉孕枰M(jìn)行6次16位除法/求余運(yùn)算。

因此，再變通一下，改變一下運(yùn)算次序，先用x除以1 000，結(jié)果暫存于1個(gè)臨時(shí)變量temp中，temp的值代表x包含多少個(gè)1 000.至此不難得出，temp取值范圍為0～65，可以用1個(gè)unsigned char數(shù)據(jù)類型表示。如果對(duì)temp分別進(jìn)行除10和求余運(yùn)算，即可得出萬位和千位數(shù)據(jù)。具體程序如圖3所示。

程序3與程序2相比，減少了2次16位的除法/求余運(yùn)算。由編譯仿真測(cè)試結(jié)果可知，這一次運(yùn)行時(shí)間減至666時(shí)鐘周期。

由一系列的測(cè)試結(jié)果可知，程序耗時(shí)最多的是16位除法/求余的運(yùn)算，而避免16位數(shù)據(jù)運(yùn)算是提高運(yùn)行效率的有效方法之一。仔細(xì)分析程序3可知，再減少16位運(yùn)算的次數(shù)是難以實(shí)現(xiàn)的，要想進(jìn)一步提高其效率，只能改變方式，運(yùn)用其他算法達(dá)到提高效率的目的。

2 優(yōu)化算法的研究

1個(gè)16位的二進(jìn)制數(shù)可以拆解為兩部分，即高6位和低10位?，F(xiàn)在只考慮高6位部分，我們知道，210=1 024=1 K，這個(gè)“K”的單位比十進(jìn)制數(shù)的“千”多了一點(diǎn)點(diǎn)，所以，可以近似認(rèn)為“K”就是“千”。當(dāng)1個(gè)16位的二進(jìn)制數(shù)轉(zhuǎn)換為用“K”作單位時(shí)，就可以近似得出它對(duì)應(yīng)的十進(jìn)制數(shù)中有幾個(gè)“千”。將二進(jìn)制數(shù)轉(zhuǎn)換為用“K”表示的過程很簡(jiǎn)單，只需把16位的二進(jìn)制數(shù)低10位截去，剩余的6位二進(jìn)制數(shù)字就表示有多少個(gè)“K”。舉例說明：

0b 000100 0000000000=4，096；

0b 100000 0000000000=32，768；

0b 101001 0000000000=41，984.

在這3個(gè)等式中，左側(cè)二進(jìn)制數(shù)的高6位數(shù)值剛好就是右側(cè)十進(jìn)制數(shù)千位和萬位的數(shù)值。也就是說，只要把二進(jìn)制數(shù)高6位轉(zhuǎn)換為十進(jìn)制，即可求得千位和萬位的結(jié)果。不過，當(dāng)二進(jìn)制數(shù)高6位的數(shù)值大于0b 101001（十進(jìn)制41）時(shí)，對(duì)應(yīng)的十進(jìn)制數(shù)千位要多加1。這是因?yàn)槎M(jìn)制1 K比1 000多24的尾數(shù)累計(jì)結(jié)果。

按照這個(gè)思路，用C程序可以實(shí)現(xiàn)任意16位二進(jìn)制數(shù)x的高6位部分的轉(zhuǎn)換。通過簡(jiǎn)單的運(yùn)算很容易得到萬位和千位的轉(zhuǎn)換結(jié)果，即：

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

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

wan = i / 10； //計(jì)算萬位

qian = i % 10； //計(jì)算千位

之前的運(yùn)算只涉及8位除法/求余運(yùn)算，并不需要16位運(yùn)算，因而效率較高。在此需要注意的是，當(dāng)前i取值不是最終結(jié)果，考慮到x的低十位轉(zhuǎn)換過程可能產(chǎn)生進(jìn)位的情況，i的值將在之后的處理過程中修正。

現(xiàn)在考慮低10位的轉(zhuǎn)換方法，由于前面千位用近似的1 K表示，每個(gè)1 K比1 000多了24，多出部分需累加到低10位的數(shù)值中。假如低10位數(shù)值用j表示，數(shù)值j應(yīng)作累加運(yùn)算，即：

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

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

考慮j的取值為 0～1 023，超出了1個(gè)字節(jié)范圍，不便于8位機(jī)處理，所以，可把j的低二位忽略，只取高8位，則其數(shù)值相當(dāng)于縮小了4倍，使其值在256以內(nèi)，進(jìn)而用unsigned char類型表示，也便于計(jì)算。這個(gè)過程可表示為：

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

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

在此需要注意的是，這里的i*24改為i*6是因?yàn)閖縮小了4倍，因而i*24也同樣縮小4倍。同時(shí)，j經(jīng)過累加運(yùn)算后，運(yùn)算結(jié)果可能會(huì)超出8位范圍，所以，需檢測(cè)進(jìn)位標(biāo)志CY來判定是否溢出。一旦溢出，則表示j的取值大于255，也就意味著低10位累加結(jié)果大于1 023，因而需向i進(jìn)位（1 000），并讓j扣減250（1 000/4）。此運(yùn)算過程為：

if （CY == 1） //判定是否有進(jìn)位

{

i++；

j += 6； //對(duì)于8位運(yùn)算，加6與減 250 等效

}

j經(jīng)過加6運(yùn)算后，仍有可能大于或等于250.也就是說，低10位數(shù)值大于等于1 000.如果它為真，則需要再一次向i進(jìn)位，即：

if （j >= 250） //判定是否需進(jìn)位

{

i++；

j += 6； //對(duì)于8位運(yùn)算，加6與減 250 等效

}

經(jīng)過2次累加，現(xiàn)在可以保證j的值在250以內(nèi)。也就是說，低10位數(shù)值小于1 000.同時(shí)，i取值也經(jīng)過修正得到正確值，并可據(jù)此求出最終的萬位、千位數(shù)值，即：

wan = i / 10； //計(jì)算萬位

qian = i % 10； //計(jì)算千位

至此，可以計(jì)算十進(jìn)制數(shù)的百位、十位和個(gè)位。在計(jì)算百位時(shí)，只要把低10位的數(shù)據(jù)除以100，即可得出結(jié)果。但是，1 000以內(nèi)的數(shù)值除以100仍得按16位除法運(yùn)算。變通一下，現(xiàn)在j的取值是低10位數(shù)值縮小4倍（忽略低2位）的結(jié)果，所以，低10位數(shù)值除以100，等效于j/25，即可避開16位除法運(yùn)算，使用8位除法達(dá)到目的。于是有：

bai = j / 25； //計(jì)算百位

剩余的十位、個(gè)位計(jì)算比較容易，只需把j對(duì)25求余，然后重新擴(kuò)大4倍，并與最低兩位相加，即得100以內(nèi)的尾數(shù)。具體計(jì)算是：

j = （j % 25） * 4 + （x & 3）； //計(jì)算模100余數(shù)

最后，可以計(jì)算十位與個(gè)位數(shù)值了，即：

shi = j / 10； //計(jì)算十位

ge = j % 10； //計(jì)算個(gè)位

到此為止，個(gè)位、十位、百位、千位、萬位已經(jīng)全部計(jì)算完畢。計(jì)算過程稍微有些復(fù)雜，但是，在整個(gè)計(jì)算過程中，沒有使用16位除法/求余運(yùn)算，所以，程序運(yùn)行速度比較快。將文中全部的計(jì)算過程整理好，得到的程序如圖4所示。

將程序4進(jìn)行編譯仿真測(cè)試，得出運(yùn)行時(shí)間為101時(shí)鐘周期，比程序1、程序2和程序3快了6～9倍。由此可知，運(yùn)用此算法后，運(yùn)行速度明顯提升。另外，針對(duì)KEIL C51的編譯器和標(biāo)準(zhǔn)51內(nèi)核的結(jié)構(gòu)，利用內(nèi)部寄存器B還可以進(jìn)一步優(yōu)化程序，但是，程序的可移植性將變差。優(yōu)化后的程序如圖5所示。

試運(yùn)行程序5，測(cè)試結(jié)果表明，經(jīng)過優(yōu)化的程序只需要72時(shí)鐘周期，而且有效加快了運(yùn)行速度。

3 結(jié)束語

算法往往是決定程序運(yùn)行效率的最重要因素，好的算法可以讓低配置的系統(tǒng)獲得高性能。本文提及的改進(jìn)算法只是一個(gè)特例，在不同的硬件架構(gòu)、不同的編譯環(huán)境中，實(shí)現(xiàn)的方法也不相同。因此，在工作過程中，程序設(shè)計(jì)員需要根據(jù)不同系統(tǒng)的特點(diǎn)，尋求合適的最優(yōu)算法，充分發(fā)揮系統(tǒng)的性能。

〔編輯：白潔〕