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

姜令聞

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

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

【中圖分類號(hào)】G633.6? 【文獻(xiàn)標(biāo)識(shí)碼】A? 【文章編號(hào)】1671-8437（2019）34-0171-03

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面，以[4]的問(wèn)題2為例，給出了C語(yǔ)言的代碼實(shí)現(xiàn)。由于運(yù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為負(fù)數(shù)

if （ pint1[UBD] > 4 ）

{

char tmp[TOP] = {1} ;

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

sub（pint1，tmp）;

}

//輸出運(yùn)算結(jié)果

output（pint1）;

return 0;

}

//輸出大數(shù)d

void output（char d[]）

{

//處理負(fù)數(shù)

if （ d[UBD] > 4 ）

{

putchar（‘-’）;

//對(duì)d取反求其絕對(duì)值

get_comp（d，d）;

}

int i = UBD ;

//跳過(guò)高位先導(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’ ;

}

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

int f = 0 ， b = pls - 1 ;

while （ f < b ）

{

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

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

}

}

測(cè)試結(jié)果：

輸入：

12345678998765432112345678988888

987654321

輸出：

12345678998765432112344691334567

輸入：

987654321

12345678998765432112345678988888

輸出：

-12345678998765432112344691334567

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

【參考文獻(xiàn)】

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

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

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

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