十進制反碼在大數加減法計算中的應用

姜令聞

【摘 要】本文提出了十進制下反碼和補碼的概念，并將其應用到了大數加減法運算中，將減法和加法統一為加法，降低了大數運算程序代碼的復雜性。

【關鍵詞】反碼，補碼，大數加減法運算，程序設計

【中圖分類號】G633.6? 【文獻標識碼】A? 【文章編號】1671-8437（2019）34-0171-03

大數指的是數據大小超過程序設計語言基本數據類型表示范圍的整數，這種數據無法用程序設計語言提供的基本整數類型表示，需要編程者自己構造數據結構進行存儲。由于不屬于基本數據類型，因此也無法直接應用基本數據類型擁有的各種運算，需要編程者自己給出計算加、減、乘、除的相關算法，這就是所謂的大數計算。

大數計算也叫高精度計算，通常是信息競賽學習的入門內容。對學習如何構造數據結構、通過實現手算運算過程學習“模擬”算法有著重要的啟蒙意義。

大數計算所處理的數據通常具有明確的上限，因此可以用確定長度的數組表示，其中數組的每一元素用以存儲大數的每一位，大數不存在的高位視同為0。由于每一元素都只用來表示0～9十個數字，且在加減法運算中的中間結果均不超過兩位數，故數組元素可以設為char類型。由于整數運算要求逐位對齊，所以將大數個位存儲在下標為0的元素中，以便于在實現逐位對齊，按照手算的規則編寫程序。

根據初中的數學知識，在兩個整數的加減法運算規則是[1]：

加法法則：（1）同號兩數相加，取相同的符號，并把它們的絕對值相加;

（2）異號兩數相加，取絕對值大的加數的符號，并用較大的絕對值減去較小的絕對值。

減法法則：減去一個數等于加上這個數的相反數。即a-b=a+（-b）

由此不難看出，按手算規則計算兩整數加減法，需要判斷兩數的正負號以及絕對值大小關系。而進一步進行“減去”運算時可能又需要“借位”。

這樣復雜的規則給編寫程序代碼帶來了困難，不僅使得代碼難于編寫，而且程序正確性也不易得到保證。為回避這種復雜性，在涉及到大數減法時，有些書只提及較大的正整數減去一個較小的正整數的情況[2]。

減法這些令人感到棘手的問題在計算機出現后不久很快就凸顯出來了。為此，人們發明了二進制數的反碼制與補碼制，克服了這個難題，使得加法和減法都可以統一使用相同的加法器來完成，而不是分別由加法器和減法器來完成，成功地降低了計算機運算器的復雜性[3]。

這種思想，也可以用于十進制數，把減法和加法統一為加法，從而降低大數運算程序代碼的復雜性。

為此這里定義確定長度（不影響一般性文中取為L=6位）的十進制數的反碼為：非負值（[0，499999]）時為該6位數本身;負值時（[-500000，-1]）為9減去該數各位數字得到的結果。定義補碼為：非負值（[0，499999]）時為該6位數本身;負值時為反碼加1得到的結果。如，12345的反碼為012345，-12345的反碼為987654。不難發現在這種碼制下，6位長度能表示的數據范圍為[-500000，499999]，最高位小于5時表示正值，大于等于5時表示負值。

求得負值的反碼之后，再加上1就得到了其補碼（正值補碼仍為本身），與其他補碼相加就等價于減法運算。為進一步簡化程序，代碼中不再求補碼，而是把加上補碼視為初始進位值為1的加法。如，對20613-65209， -65209的反碼為934790，計算過程如圖 1所示：

得到的955404顯然是一個負值（最高位大于4），其對應的負數絕對值的求法為：減1再取反，計算過程如圖 2所示：

因而，20613-65209的計算結果為-44596。

由此可見，只要增加一個簡單的求負值反碼的步驟，就可以將減法與加法統一為相同的過程，從而達到降低代碼復雜性的目的。這種算法的正確性基于這樣一個事實，對于一個負的6位整數-d5d4d3d2d1d0（其中di為一十進制數字），加上1000000后末尾6位保持不變。而

亦即減去一個正數，在被減數、減數及差都可以用6位反碼制表示的前提下，加上減數反碼再加1得到的結果，與減法得到的差末尾6位數字相同。

下面，以[4]的問題2為例，給出了C語言的代碼實現。由于運用了反碼技術，故本代碼不受被減數必須比減數大的限制，甚至也不受是否有前導零的限制。

#include <stdio.h>

#define TOP （201）

#define UBD （TOP-1）

void input（char []）;

void swap（char *，char *） ;

void sub（char []，char []）;

void get_comp（char []，char []）;

void add（char []，char []，int）;

void output（char []）;

int main（void）

{

char pint1[TOP] = {0} ，

pint2[TOP] = {0} ;

input（pint1）; //輸入被減數

input（pint2）; //輸入減數

//相減，將差存在pint1中

sub（pint1，pint2）;

//如果pint1為負數

if （ pint1[UBD] > 4 ）

{

char tmp[TOP] = {1} ;

//為求負數絕對值先-1

sub（pint1，tmp）;

}

//輸出運算結果

output（pint1）;

return 0;

}

//輸出大數d

void output（char d[]）

{

//處理負數

if （ d[UBD] > 4 ）

{

putchar（‘-’）;

//對d取反求其絕對值

get_comp（d，d）;

}

int i = UBD ;

//跳過高位先導0

while （ i > 0 && d[i] == 0 ）

{

i-- ;

}

//由高到低輸出

do

{

printf（“%d”，d[i]）;

}

while （ i -- > 0）;

}

//d1+d2+carry => d1

void add（char d1[]，char d2[]，int carry）

{

int i ;

for （ i = 0 ; i < TOP ; i ++ ）

{

d1[i] += d2[i] + carry;

carry = d1[i] / 10 ;

d1[i] %= 10 ;

}

}

//求d反碼=>c

void get_comp（char c[]，char d[]）

{

int i ;

for （ i = 0 ; i < TOP ; i ++ ）

{

c[i] = 9 - d[i] ;

}

}

// d1-d2 =>d1

void sub（char d1[]，char d2[]）

{

char comp_9[TOP] ;//反碼

//求d2反碼=>comp_9

get_comp（comp_9，d2）;

//+反碼 +1

add（d1，comp_9，1）;

}

//交換p、q所執行數據的值

void swap（char * p ，char * q）

{

char t = * p ;

* p = * q ;

* q = t ;

}

//輸入大數 => d

void input（char d[]）

{

int pls = 0 ;

int ch ;

//由高位到低位輸入

while （ （ ch = getchar （） ） ！= ‘＼n’ ）

{

d[pls++] = ch - ‘0’ ;

}

//逆序，實現由低向高存儲

int f = 0 ， b = pls - 1 ;

while （ f < b ）

{

//前后對應位交換

swap（ d + f ++ ， d + b -- ） ;

}

}

測試結果：

輸入：

12345678998765432112345678988888

987654321

輸出：

12345678998765432112344691334567

輸入：

987654321

12345678998765432112345678988888

輸出：

-12345678998765432112344691334567

表明本文在前提出的設想得到了實現，十進制反碼確實可以簡化大數減法的運算。此外，由于函數add（）在以0作為進位實參調用時可以完成加法運算，所以本文的程序可以很容易地擴展為大數加減法混合運算。

【參考文獻】

[1]楊裕前，董林偉.七年級上冊數學（第3版）[Z].南京：江蘇鳳凰科技出版社，2012（31）.

[2]董永建.信息學奧賽一本通（C++版）[Z].北京：科學技術文獻出版社，2013.181-182.

[3]張福炎，孫志輝.大學計算機信息技術教程（2018版）[Z].南京：南京大學出版社，2018.12-13.

[4]董永建.信息學奧賽一本通（C++版）[Z].北京：科學技術文獻出版社，2013.188.