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

閆海環 劉國華 劉晨

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

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

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

1“傳統拆分”算法

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

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

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

2“二分拆分”算法

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

三位數的“二分拆分”算法軟件實現方法：假設預拆分的三位數data（569），首先進行高位數字的拆分：①三位數的有限區間為[0，999]，將該區間劃分成兩部分[0，599]和B（599，999]。數據data（569）與599進行比較，小于599，確定查找區域為[0，599]。②需要將區間[0，599]再劃分成兩部分[0，299]和（299，599]。數據data（569）與299進行比較，大于299，確定查找區域為（299，599]。③需要將區間（299，599]再劃分成兩部分（299，399]和（399，599]。數據data（569）與399進行比較，大于399，確定查找區域為（399，599]。④需要將區間（399，599]再劃分成兩部分（399，499]和（499，599]。數據data（569）與499進行比較，此時數據data（569）>499且<599，因此可以確定百位數字為5，剩余兩位數為data（569）-500。以此類推在有限區間為：[0，999]，可將數據劃分成區域10個區域，每個區域對應百位數字：[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。其次進行中間位數字的拆分：①兩位數的有限區間為[0，99]，將該區間劃分成兩部分[0，59]和B（59，99]。數據data（69）與59進行比較，大于59，確定查找區域為（59，99]。②需要將區間（59，99]再劃分成兩部分（59，79]和（79， 99]。數據data（69）與79進行比較，小于79，確定查找區域為（59，79]。③需要將區間（59，79]再劃分成兩部分（59，69]和（69，79]。數據data（69）與69進行比較，等于69，確定查找區域為（59，69]。因此可以確定中間位數字為6，剩余一位數為data（69）-60。以此類推在有限區間為：[0，99]，可將數據劃分成區域10個區域，每個區域對應百位數字：[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。最后獲得低位數字為9。

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

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

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

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

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

static void dispose_datafunc（unsigned int data） //數據拆分函數定義

{

unsigned int array[3]；

*array = data；

baiwei（array）；

shiwei（array）；

high_data = array[0]；

mid_data = array[1]；

low_data = array[2]；

}

圖1 中間數字的獲取流程 圖2 “二分拆法”與“傳統拆分”的響應時間對比

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

編寫簡單的測試程序將“二分拆分”算法與“傳統拆分”算法同時運行，采用單片機ATmega64的PA0的高低電平變換測試兩段程序的運行時間，并用示波器測量，如圖2。相同數據進行拆分，“二分拆分”算法運行時間為3us，傳統拆分算法運行時間為18us。“二分拆分”算法的效率遠遠高于傳統拆分算法。測試程序：

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

dispose_datafunc（569）； //二分法數據處理，

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

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

PORTA |= 0x01； //高電平

hex_bcd（569）； //傳統數字拆分法

PORTA &= ～0x01；

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

4結語

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

參考文獻：

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

[2]沈文，詹衛前.AVR單片機C語言開發入門指導.

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