十進制反碼在大數(shù)加減法計算中的應(yīng)用

姜令聞

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

【關(guān)鍵詞】反碼，補碼，大數(shù)加減法運算，程序設(shè)計

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

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

大數(shù)計算也叫高精度計算，通常是信息競賽學(xué)習(xí)的入門內(nèi)容。對學(xué)習(xí)如何構(gòu)造數(shù)據(jù)結(jié)構(gòu)、通過實現(xiàn)手算運算過程學(xué)習(xí)“模擬”算法有著重要的啟蒙意義。

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

根據(jù)初中的數(shù)學(xué)知識，在兩個整數(shù)的加減法運算規(guī)則是[1]：

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

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

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

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

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

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

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

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

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

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

因而，20613-65209的計算結(jié)果為-44596。

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

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

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

#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）; //輸入被減數(shù)

input（pint2）; //輸入減數(shù)

//相減，將差存在pint1中

sub（pint1，pint2）;

//如果pint1為負數(shù)

if （ pint1[UBD] > 4 ）

{

char tmp[TOP] = {1} ;

//為求負數(shù)絕對值先-1

sub（pint1，tmp）;

}

//輸出運算結(jié)果

output（pint1）;

return 0;

}

//輸出大數(shù)d

void output（char d[]）

{

//處理負數(shù)

if （ d[UBD] > 4 ）

{

putchar（‘-’）;

//對d取反求其絕對值

get_comp（d，d）;

}

int i = UBD ;

//跳過高位先導(dǎo)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所執(zhí)行數(shù)據(jù)的值

void swap（char * p ，char * q）

{

char t = * p ;

* p = * q ;

* q = t ;

}

//輸入大數(shù) => d

void input（char d[]）

{

int pls = 0 ;

int ch ;

//由高位到低位輸入

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

{

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

}

//逆序，實現(xiàn)由低向高存儲

int f = 0 ， b = pls - 1 ;

while （ f < b ）

{

//前后對應(yīng)位交換

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

}

}

測試結(jié)果：

輸入：

12345678998765432112345678988888

987654321

輸出：

12345678998765432112344691334567

輸入：

987654321

12345678998765432112345678988888

輸出：

-12345678998765432112344691334567

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

【參考文獻】

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

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

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

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