關(guān)于二進(jìn)制補(bǔ)碼運(yùn)算如何解決溢出問(wèn)題的研究

柏剛+程蘭

摘要：計(jì)算機(jī)中用補(bǔ)碼來(lái)表示和存儲(chǔ)數(shù)值，而在進(jìn)行數(shù)值的算術(shù)運(yùn)算時(shí)由于機(jī)器字長(zhǎng)的限制往往會(huì)出現(xiàn)補(bǔ)碼溢出，導(dǎo)致計(jì)算結(jié)果錯(cuò)誤。針對(duì)這個(gè)問(wèn)題，提出了一種根據(jù)溢出結(jié)果得到正確結(jié)果的計(jì)算方法：兩個(gè)正數(shù)相加溢出時(shí)，將錯(cuò)誤解加上2n+1即為正確解；兩個(gè)負(fù)數(shù)相加溢出時(shí)，將錯(cuò)誤解減去2n+1即為正確解，并給出了一般性證明。

關(guān)鍵詞：二進(jìn)制；有符號(hào)數(shù)；補(bǔ)碼；溢出；求補(bǔ)運(yùn)算

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）33-0208-02

Abstract：Complement is used to represent and store the value in computers.But the problem of complement overflow often happens in numerical arithmetic because of the limit of word length， which leads to calculation errors. To solve this problem， a new method is proposed to get the correct result according to the overflow result，in which the error solution can turn out to be correct by plus 2n+1 when it's two positive numbers' additive overflow or minus 2n+1 when it's two negative number's additive overflow， and gives a general proof.

Key words： Binary； Signed number ； Complement； Overflow； Complementary operation

1 補(bǔ)碼概述

二進(jìn)制補(bǔ)碼是計(jì)算機(jī)中采用的數(shù)制，用來(lái)表示有符號(hào)二進(jìn)制數(shù)。在二進(jìn)制補(bǔ)碼這一數(shù)制中，一切數(shù)（被加數(shù)、加數(shù)及和；被減數(shù)、減數(shù)及差；被乘數(shù)、乘數(shù)及積；被除數(shù)、除數(shù)、商及余數(shù)；求補(bǔ)運(yùn)算前的數(shù)及求補(bǔ)運(yùn)算后的結(jié)果等） 都是用二進(jìn)制補(bǔ)碼來(lái)表示的[1]。補(bǔ)碼問(wèn)題既是數(shù)字電子技術(shù)課程和微機(jī)原理課程的教學(xué)難點(diǎn)之一，也是軟件開(kāi)發(fā)中常常遇到的問(wèn)題之一[2]。

對(duì)于有符號(hào)數(shù)，用0表示正數(shù)的符號(hào)位，1表示負(fù)數(shù)的符號(hào)位。對(duì)于n+1（變量用斜體）位字長(zhǎng)的有符號(hào)二進(jìn)制數(shù)，其補(bǔ)碼是這樣定義的：若該數(shù)的原碼為非負(fù)數(shù)，則其補(bǔ)碼與其原碼表示相同；若該數(shù)的原碼為負(fù)，則其補(bǔ)碼的數(shù)據(jù)位為其原碼表示的數(shù)據(jù)位逐位求反后加1，而符號(hào)位為1[2]。其公式如下：（n表示數(shù)值位的位數(shù)）

2 補(bǔ)碼溢出問(wèn)題

兩個(gè)用補(bǔ)碼表示的有符號(hào)數(shù)進(jìn)行加、減運(yùn)算時(shí)，其特點(diǎn)是把符號(hào)位上表示正、負(fù)的“0”和“1”也看成數(shù)，與數(shù)值部分一起進(jìn)行運(yùn)算，所得的結(jié)果也為補(bǔ)碼形式。結(jié)果的符號(hào)位為“0”，表示正數(shù)；結(jié)果的符號(hào)位為“1”，表示負(fù)數(shù)[3]。

兩個(gè)有符號(hào)數(shù)X和Y相加時(shí)，先將兩數(shù)轉(zhuǎn)換成補(bǔ)碼形式，然后進(jìn)行補(bǔ)碼運(yùn)算，所得結(jié)果為和的補(bǔ)碼，即：[X+Y]補(bǔ)=[X]補(bǔ)+[Y]補(bǔ)。兩個(gè)有符號(hào)數(shù)X和Y相減時(shí)，可看成X+（-Y）分別將X和-Y表示成補(bǔ)碼形式再進(jìn)行運(yùn)算，所得結(jié)果為差的結(jié)果，即：[X-Y]補(bǔ)=[X]補(bǔ)+[-Y]補(bǔ)。

由于補(bǔ)碼的表示范圍為：-2n～ 2n-1。當(dāng)兩個(gè)有符號(hào)數(shù)進(jìn)行補(bǔ)碼運(yùn)算時(shí)，若結(jié)果的絕對(duì)值超出運(yùn)算裝置容量，數(shù)值部分就會(huì)發(fā)生溢出，占據(jù)符號(hào)位的位置，導(dǎo)致錯(cuò)誤的結(jié)果[3]。

因?yàn)橛?jì)算機(jī)中的減法也看作加法，因此我們只討論加法。下面分3種情況來(lái)討論兩個(gè)有符號(hào)數(shù)X和Y相加（轉(zhuǎn)換成補(bǔ)碼后，用n位數(shù)值位1位符號(hào)位表示）。

1）. X和Y均為正數(shù)，當(dāng)X+Y大于2n-1時(shí)，結(jié)果溢出。

2）. X和Y均為負(fù)數(shù)，當(dāng)X+Y小于-2n時(shí)，結(jié)果溢出。

3）. X和Y兩數(shù)中只有一個(gè)數(shù)為正，另一個(gè)數(shù)為負(fù)。符號(hào)不同的兩個(gè)數(shù)相加是不會(huì)產(chǎn)生溢出的[4]。

3 如何從補(bǔ)碼溢出結(jié)果得到正確結(jié)果

下面將討論兩種溢出的情況，并提出解決溢出問(wèn)題的方法。

1） X和Y均為正數(shù)，當(dāng)X+Y大于2n-1時(shí)，結(jié)果將溢出。

例2：使用7位數(shù)值位，1位符號(hào)位的二進(jìn)制數(shù)來(lái)表示，其補(bǔ)碼表示范圍為：-128D ～ 127D

計(jì)算70+85，由于70+85=155，155大于127，結(jié)果將溢出。

即：70+85=-1100101= -101，顯然發(fā)生溢出，結(jié)果錯(cuò)誤。

為了給出解決方法，先給出兩個(gè)結(jié)論：

結(jié)論一：兩正數(shù)相加最高位（符號(hào)位）一定不會(huì)進(jìn)位。

證明：兩正數(shù)的符號(hào)位都是零，如果符號(hào)位溢出，次高位必須要進(jìn)2，在最理想的情況（兩個(gè)數(shù)的次高位都是1），次高位要進(jìn)2必須要求次次高位進(jìn)2，以此類推，必須要求最低位進(jìn)2，才能使得較高位進(jìn)2，而最低位最多只能進(jìn)1。

由此例可知，即使數(shù)值位都為1，符號(hào)位也不會(huì)產(chǎn)生進(jìn)位。

結(jié)論二：兩正數(shù)相加溢出一定是由于次高位（數(shù)值部分最高位）向符號(hào)位有進(jìn)位。

證明：根據(jù)雙高位判別法（計(jì)算機(jī)中常用的溢出判別稱為雙高位判別法，即：最高位（符號(hào)位）有進(jìn)位而次高位無(wú)進(jìn)位或最高位（符號(hào)位）無(wú)進(jìn)位而次高位有進(jìn)位 [3]。）及結(jié)論一，可知溢出一定是因?yàn)榇胃呶挥羞M(jìn)位，而且只能進(jìn)1，所以符號(hào)位一定是1。

下面推導(dǎo)出解決正數(shù)相加溢出的公式。

設(shè)X和Y都為正數(shù)，轉(zhuǎn)換成二進(jìn)制補(bǔ)碼后用n位數(shù)值位1位符號(hào)位表示，且X+Y大于2n-1，即溢出。為了避免可能產(chǎn)生的溢出錯(cuò)誤，有必要擴(kuò)展二進(jìn)制補(bǔ)碼的碼位數(shù)，即在進(jìn)行求補(bǔ)運(yùn)算之前，使二進(jìn)制補(bǔ)碼擴(kuò)展符號(hào)位：將二進(jìn)制補(bǔ)碼的原符號(hào)位向左 （高位） 重復(fù)寫(xiě)一位，形成新的符號(hào)位。擴(kuò)展符號(hào)位以后的二進(jìn)制補(bǔ)碼，真值不變。擴(kuò)展符號(hào)位能夠保證 n位二進(jìn)制補(bǔ)碼的每一個(gè)數(shù)求補(bǔ)運(yùn)算的正確性[1]。結(jié)果將不會(huì)溢出。

即：（1）用n+1位數(shù)值位1位符號(hào)位表示[X]補(bǔ)+[Y]補(bǔ)時(shí)不會(huì)溢出，得到的結(jié)果為正確結(jié)果，令正確結(jié)果為Co。

（2）用n位數(shù)值位1位符號(hào)位表示[X]補(bǔ)+[Y]補(bǔ)時(shí)會(huì)溢出，得到的結(jié)果為錯(cuò)誤結(jié)果，令錯(cuò)誤結(jié)果為Er。

在結(jié)論一和結(jié)論二的條件下，Er是將Co的最高位當(dāng)成了符號(hào)位，把Er當(dāng)成負(fù)數(shù)，再求補(bǔ)碼從而得到原碼。即：

例4中-76+（-90）轉(zhuǎn)換成補(bǔ)碼運(yùn)算后等于+1011010即+90。

將90代入（5）式：90-28=-166，結(jié)果正確。

結(jié)論四：負(fù)數(shù)的補(bǔ)碼運(yùn)算溢出時(shí)，將溢出結(jié)果減去2n+1可以得到正確結(jié)果。

4 結(jié)論

本文討論了有符號(hào)數(shù)的補(bǔ)碼溢出問(wèn)題，并給出了根據(jù)溢出結(jié)果得到正確結(jié)果的方法。兩個(gè)正數(shù)相加溢出時(shí)，將錯(cuò)誤解加上2n+1即為正確解；兩個(gè)負(fù)數(shù)相加溢出時(shí)，將錯(cuò)誤解減去2n+1即為正確解。本文方法可以在不增加字長(zhǎng)的情況下解決溢出問(wèn)題。

參考文獻(xiàn)：

[1] 查振亞. 關(guān)于二進(jìn)制補(bǔ)碼數(shù)制中求補(bǔ)運(yùn)算的研究[J]. 華中理工大學(xué)學(xué)報(bào)， 1997（3）：106-110.

[2] 孫開(kāi)放. 對(duì)二進(jìn)制補(bǔ)碼數(shù)的進(jìn)一步研究[J]. 電氣電子教學(xué)學(xué)報(bào)，2002（3）：35-36.

[3] 馬春燕. 微機(jī)原理與接口技術(shù)（基于32位機(jī)）[M]. 北京：電子工業(yè)出版社，2013：14-17.

[4] 曹建芳. 二進(jìn)制定點(diǎn)整數(shù)補(bǔ)碼運(yùn)算中“丟失”與“溢出”問(wèn)題的研究[J]. 晉東南師范?？茖W(xué)校學(xué)報(bào)，2003（2）：68.