基于單片機數(shù)字拆分的一種高效算法

閆海環(huán) 劉國華 劉晨

【摘 要】為了提高單片機在數(shù)據(jù)拆分程序中的執(zhí)行效率，提出采用“二分拆分”算法。該方法不需要做16位的余數(shù)算法及16位的除法算法，采用簡單的判斷語句即可獲得各位對應數(shù)值。文章對該算法在數(shù)據(jù)拆分中的應用進行原理分析，同時進行了軟件設計，通過實驗驗證“二分拆分”算法的高效性。

【關鍵詞】單片機 “二分拆分”算法 效率

隨著科技的發(fā)展，在以單片機為核心的智能儀表系統(tǒng)中，常常遇到，需要將數(shù)據(jù)直觀地顯示出來，以方便人們監(jiān)視智能系統(tǒng)的工作情況或直接讀取各儀表測量的結果，此時就需要將程序中的數(shù)據(jù)進行拆分。目前國內(nèi)許多單片機書籍或網(wǎng)絡上介紹并提供了許多子程序，但程序執(zhí)行效率不高。本文重點介紹了一種“二分拆分”算法，可以大大提高數(shù)據(jù)拆分的效率。

1“傳統(tǒng)拆分”算法

“傳統(tǒng)拆分”算法思想：兩個整型數(shù)據(jù)進行除法或求余運算。C語言中，兩個整數(shù)相除、求余運算的結果是整數(shù)。

三位數(shù)的“傳統(tǒng)拆分”算法軟件實現(xiàn)：假設預拆分的三位數(shù)data（569），首先進行高位數(shù)字的拆分：data（569）/100，得到高位數(shù)字5；其次進行中間位數(shù)字的拆分：data（569）% 100得到數(shù)據(jù)69，69/10得到中間位數(shù)字6；最后低位數(shù)據(jù)的拆分：data（569）% 10，得到低位數(shù)字9。

“傳統(tǒng)拆分”算法C語言代碼簡單。但是大部分的C編譯器的求余運算都是調(diào)用子程序來完成，代碼長，執(zhí)行速度慢。

2“二分拆分”算法

“二分拆分”的思想：首先確定有限區(qū)間，將區(qū)間分成兩部分，通過判斷數(shù)據(jù)的單調(diào)性，逐步將有限區(qū)間縮小，直至有限區(qū)間在所求范圍內(nèi)，便可拆分出滿足要求的數(shù)值。“二分拆分”算法主要采用“if（表達式）語句1 else 語句2”，每次判斷即可篩掉一半數(shù)據(jù)。針對單片機來說， “二分拆分”算法的效率遠遠高于全遍歷的線性判斷及傳統(tǒng)的取余算法。

三位數(shù)的“二分拆分”算法軟件實現(xiàn)方法：假設預拆分的三位數(shù)data（569），首先進行高位數(shù)字的拆分：①三位數(shù)的有限區(qū)間為[0，999]，將該區(qū)間劃分成兩部分[0，599]和B（599，999]。數(shù)據(jù)data（569）與599進行比較，小于599，確定查找區(qū)域為[0，599]。②需要將區(qū)間[0，599]再劃分成兩部分[0，299]和（299，599]。數(shù)據(jù)data（569）與299進行比較，大于299，確定查找區(qū)域為（299，599]。③需要將區(qū)間（299，599]再劃分成兩部分（299，399]和（399，599]。數(shù)據(jù)data（569）與399進行比較，大于399，確定查找區(qū)域為（399，599]。④需要將區(qū)間（399，599]再劃分成兩部分（399，499]和（499，599]。數(shù)據(jù)data（569）與499進行比較，此時數(shù)據(jù)data（569）>499且<599，因此可以確定百位數(shù)字為5，剩余兩位數(shù)為data（569）-500。以此類推在有限區(qū)間為：[0，999]，可將數(shù)據(jù)劃分成區(qū)域10個區(qū)域，每個區(qū)域對應百位數(shù)字：[0，99]→0，（99，199]→1，（199，299]→2，（299，399]→3，（399，499]→4，（499，599]→5，（599，699]→6，（699，799]→7，（799，899]→8，（899，999]→9。其次進行中間位數(shù)字的拆分：①兩位數(shù)的有限區(qū)間為[0，99]，將該區(qū)間劃分成兩部分[0，59]和B（59，99]。數(shù)據(jù)data（69）與59進行比較，大于59，確定查找區(qū)域為（59，99]。②需要將區(qū)間（59，99]再劃分成兩部分（59，79]和（79， 99]。數(shù)據(jù)data（69）與79進行比較，小于79，確定查找區(qū)域為（59，79]。③需要將區(qū)間（59，79]再劃分成兩部分（59，69]和（69，79]。數(shù)據(jù)data（69）與69進行比較，等于69，確定查找區(qū)域為（59，69]。因此可以確定中間位數(shù)字為6，剩余一位數(shù)為data（69）-60。以此類推在有限區(qū)間為：[0，99]，可將數(shù)據(jù)劃分成區(qū)域10個區(qū)域，每個區(qū)域對應百位數(shù)字：[0，9]→0，（9，19]→1，（19，29]→2，（29，39]→3，（39，49]→4，（49，59]→5，（59，69]→6，（69，79]→7，（79，89]→8，（89，99]→9。最后獲得低位數(shù)字為9。

高位數(shù)字、中間位數(shù)字的拆分函數(shù)，采用數(shù)組名作為函數(shù)參數(shù)，由于數(shù)組名代表的是數(shù)組元素的首地址，傳遞的值是地址，因此要求形參為數(shù)組名或指針變量。通俗理解，形參指針變量與實參數(shù)組共占同一段內(nèi)存單元，在調(diào)用函數(shù)期間，如果改變了形參數(shù)組的值，也就改變了實參數(shù)組的值。中間數(shù)字的拆分函數(shù)需特別注意：形參獲得的地址是數(shù)組首地址，此時需要將形參地址+1，并賦給形參。如圖1。

在C語言中，用指針編寫的程序比用數(shù)組下標編寫的程序執(zhí)行速度快。因此形參采用指針變量。

static unsigned int high_data， mid_data， low_data； //高位、中間位、低位數(shù)字定義

static void baiwei（unsigned int *p）； //高位數(shù)字的拆分函數(shù)

static void shiwei（unsigned int *p）； //中間數(shù)字的拆分函數(shù)

static void dispose_datafunc（unsigned int data） //數(shù)據(jù)拆分函數(shù)定義

{

unsigned int array[3]；

*array = data；

baiwei（array）；

shiwei（array）；

high_data = array[0]；

mid_data = array[1]；

low_data = array[2]；

}

圖1 中間數(shù)字的獲取流程 圖2 “二分拆法”與“傳統(tǒng)拆分”的響應時間對比

3“二分拆分”算法的實驗驗證

編寫簡單的測試程序將“二分拆分”算法與“傳統(tǒng)拆分”算法同時運行，采用單片機ATmega64的PA0的高低電平變換測試兩段程序的運行時間，并用示波器測量，如圖2。相同數(shù)據(jù)進行拆分，“二分拆分”算法運行時間為3us，傳統(tǒng)拆分算法運行時間為18us?！岸植鸱帧彼惴ǖ男蔬h遠高于傳統(tǒng)拆分算法。測試程序：

PORTA |= 0x01； //高電平開始

dispose_datafunc（569）； //二分法數(shù)據(jù)處理，

PORTA &= ～0x01； //低電平

for （i=0；i<10；i++） delay_1us（）；

PORTA |= 0x01； //高電平

hex_bcd（569）； //傳統(tǒng)數(shù)字拆分法

PORTA &= ～0x01；

for （i=0；i<30；i++） delay_1us（）；

4結語

通過實驗驗證，“二分拆法”算法確實較“傳統(tǒng)拆分”算法大大提高了MCU的執(zhí)行效率。由此看來，好的單片機代碼，并不是僅僅局限于各種功能的實現(xiàn)，還應該從執(zhí)行效率、減少運算的強度、便于移植等方面綜合考慮，選擇合適的算法。

參考文獻：

[1]鄧勇，劉琪.智能儀表多字節(jié)二進制數(shù)轉換BCD碼.《電子產(chǎn)品世界》，1999年12期.

[2]沈文，詹衛(wèi)前.AVR單片機C語言開發(fā)入門指導.

作者簡介：閆海環(huán)（1982一），女，漢族，山西省交城縣，本科，助理工程師，從事逆變電源的開發(fā)。