二進制數轉十進制優化算法探討

歐海飛

文章編號：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 結束語

算法往往是決定程序運行效率的最重要因素，好的算法可以讓低配置的系統獲得高性能。本文提及的改進算法只是一個特例，在不同的硬件架構、不同的編譯環境中，實現的方法也不相同。因此，在工作過程中，程序設計員需要根據不同系統的特點，尋求合適的最優算法，充分發揮系統的性能。

〔編輯：白潔〕