引言

平時(shí)的編程過程中，當(dāng)進(jìn)行整數(shù)運(yùn)算時(shí)，經(jīng)常會(huì)遇到一些奇怪的結(jié)果，比如兩個(gè)正數(shù)加出負(fù)數(shù)，兩個(gè)負(fù)數(shù)可以加出一個(gè)正數(shù)，這些都是由于數(shù)值表示的有限性導(dǎo)致的。下面我們來看看C語言和Java語言當(dāng)中的例子。

public static void main(String[] args) {
       int a = 0x7FFFFFFF;
       int b = 0x7FFFFFFF;
       System.out.println(a);
       System.out.println(b);
       System.out.println( a + b );
   }

程序當(dāng)中的a和b都是很大的正整數(shù)，結(jié)果它們相加會(huì)得到一個(gè)負(fù)數(shù)。

接下來我們?cè)賮砜纯碈語言當(dāng)中的例子，它也會(huì)具有同樣的特性。

#include <stdio.h>
   
int main(){
   int a = 0x7FFFFFFF;
   int b = 0x7FFFFFFF;
   printf("%d\n",a);
   printf("%d\n",b);
   printf("%d\n",a+b);
}

我們來看看這個(gè)程序的結(jié)果，是否與Java一致。

可以看到，在C于Java當(dāng)中，結(jié)果都是一樣的，所以我們有必要對(duì)二進(jìn)制整數(shù)的運(yùn)算做一些簡(jiǎn)單的了解。

無符號(hào)加法

這里L(fēng)Z不想按照書中的方式去介紹，我們換一種思路，來簡(jiǎn)單的了解一下吧。

小時(shí)候?qū)W習(xí)加法時(shí)，我們都是使用的畫表式，就是上面是被加數(shù)，下面是加數(shù)，然后左邊寫一個(gè)加號(hào)，逢10就進(jìn)1，然后下面畫一條橫線，橫線下面就是我們的結(jié)果。

對(duì)于我們的二進(jìn)制整數(shù)來說，其實(shí)也可以使用這種最原始的方式去計(jì)算，由此也可以認(rèn)識(shí)到，二進(jìn)制整數(shù)的加法也是非常簡(jiǎn)單的。只不過它與我們平時(shí)的十進(jìn)制算法有一個(gè)最大的區(qū)別，那就是我們?cè)谟?jì)算機(jī)當(dāng)中進(jìn)行計(jì)算時(shí)，結(jié)果的位數(shù)都是有限制的。因此在我們計(jì)算過后，可能需要對(duì)結(jié)果進(jìn)行截?cái)嗖僮鳌?/p>

前面一章我們已經(jīng)講過有關(guān)截?cái)嗟膬?nèi)容，那么很明顯這里就可以用上了。這里使用的時(shí)候有一個(gè)前提，我們可以假設(shè)是進(jìn)行w位的二進(jìn)制運(yùn)算，那么在運(yùn)算之后的實(shí)際結(jié)果也一定是w位的。這里有兩種情況，一種是結(jié)果依然是w位的，也就是w+1位為0。第二種則是達(dá)到了w+1位，這個(gè)時(shí)候我們需要將結(jié)果截?cái)嗟絯位。

第一種情況則屬于正常的加法運(yùn)算，對(duì)于第二種來說，我們根據(jù)上一章的結(jié)論可以得到，假設(shè)完整的結(jié)果為sum，則實(shí)際的結(jié)果最終為 sum mod 2w。

在書中則是給出了一個(gè)公式，它得到這個(gè)結(jié)果的一個(gè)前提是兩個(gè)操作數(shù)都滿足小于2w，它與我們上面取模的結(jié)果其實(shí)是一樣的。

這里L(fēng)Z再稍微解釋一下，對(duì)于第一種情況，x+y < 2w，則sum mod 2w是與sum一致的。對(duì)于第二種來說，當(dāng) 2w =< x+y < 2w+1，對(duì) x + y 進(jìn)行2w的取模運(yùn)算，與 x + y - 2w是等價(jià)的。

無符號(hào)的非

無符號(hào)的加法會(huì)形成一個(gè)阿貝爾群，這意味著無符號(hào)加法滿足一些特性。比如可交換，可結(jié)合等等。在這個(gè)群中，單位元為0，那么每一個(gè)群中的元素，也就是每一個(gè)無符號(hào)數(shù)u，都會(huì)擁有一個(gè)逆元u-1，滿足 u＋ u-1 = 0。這個(gè)結(jié)論的來源是，對(duì)于w位上的無符號(hào)運(yùn)算來講，倘若兩個(gè)無符號(hào)數(shù)的加法運(yùn)算結(jié)果為2w，也就是1后面跟w個(gè)0，此時(shí)截?cái)嘀蟮慕Y(jié)果則為0。

從以上的簡(jiǎn)單分析，我們可以很容易的得到一個(gè)無符號(hào)數(shù)的逆元滿足以下公式（公式中的左邊就是LZ寫的u-1，由于圖中的符號(hào)在博文中不好編輯，所以LZ以u(píng)-1替代）。

補(bǔ)碼加法

對(duì)于補(bǔ)碼的加法來講，我們會(huì)建立在無符號(hào)加法的基礎(chǔ)上來進(jìn)行，這么做的一個(gè)重要前提是，它們的位表示都是一樣的。

這里書上寫的比較復(fù)雜，LZ這里稍微介紹的簡(jiǎn)單一點(diǎn)，其實(shí)補(bǔ)碼加法就是先按照無符號(hào)加法進(jìn)行運(yùn)算，而后在進(jìn)行無符號(hào)和有符號(hào)的轉(zhuǎn)換。因此我們根據(jù)上面的結(jié)論可以得到，對(duì)于兩個(gè)補(bǔ)碼編碼的有符號(hào)數(shù)來說，他們進(jìn)行加法運(yùn)算的最終結(jié)果為，假設(shè)實(shí)際的無符號(hào)結(jié)果為sum，那么最終的實(shí)際結(jié)果為 U2Tw(sum mod 2w)。

上面的這個(gè)結(jié)果看起來很簡(jiǎn)單，但實(shí)際上它的運(yùn)算結(jié)果還是比較復(fù)雜的，書中給出了四種情況的分析，采用數(shù)學(xué)推導(dǎo)和證明的方式來說明，估計(jì)對(duì)一部分?jǐn)?shù)學(xué)基礎(chǔ)較差的猿友來講，這是一種折磨，因此LZ這里將會(huì)省去這部分分析，如果有興趣的猿友可以私底下看一下書中的原版內(nèi)容。

與無符號(hào)加法不同的是，這里會(huì)出現(xiàn)三種結(jié)果，一種是正常的結(jié)果，一種是正溢出，一種是負(fù)溢出。

對(duì)于當(dāng)正溢出的時(shí)候，我們的結(jié)果與無符號(hào)數(shù)類似，取模之后等價(jià)于減去2w。而當(dāng)負(fù)溢出的時(shí)候，則剛好相反，取模之后的結(jié)果等價(jià)于加上2w。更直觀的，由于我們最終可表示的補(bǔ)碼數(shù)范圍在-2w-1（包含）到2w-1之間，所以我們總是要試圖將最終的實(shí)際結(jié)果保持在這個(gè)范圍之內(nèi)。于是我們可以直觀的得到下面的結(jié)果。

補(bǔ)碼的非

對(duì)于補(bǔ)碼來說，它同樣的與無符號(hào)有一樣的特性，也就是對(duì)于任意一個(gè)w位的補(bǔ)碼數(shù)t來說，它都有唯一的逆元t-1，使得t + t-1 = 0。

一個(gè)w位的補(bǔ)碼數(shù)的范圍在-2w-1（包含）到2w-1之間，直觀的可以看出，對(duì)于不等于-2w-1的補(bǔ)碼數(shù)x來說，它的逆元就是-x。而對(duì)于-2w-1來說，它的二進(jìn)制位表示為1后面跟著w-1個(gè)0，我們需要找到一個(gè)數(shù)與其相加之后結(jié)果為0。

這種時(shí)候我們需要考慮的是，如果是-x，也就是2w-1，則它的位表示需要w+1位，是不存在的。因此我們需要考慮溢出的情況，對(duì)照上面的公式2.14，負(fù)溢出的時(shí)候需要加上2w，因此-2w-1的逆元就是-2w + 2w-1 = -2w-1，也就是它本身。

綜合上面的情況，最終我們可以得到補(bǔ)碼的逆元滿足以下公式（這里與上面一樣，公式左邊是LZ所說的逆元t-1）。

二進(jìn)制整數(shù)的減法

這一部分內(nèi)容在書中沒有介紹，而且書中也沒有提及為什么沒有介紹，因此LZ在這里簡(jiǎn)單的提上幾句。

減法運(yùn)算其實(shí)是可以由加法運(yùn)算替代的，我們上面已經(jīng)介紹過了無符號(hào)和補(bǔ)碼的非，其實(shí)很多CPU是沒有減法運(yùn)算器的，它們都是將減數(shù)進(jìn)行逆運(yùn)算以后送入加法器，然后進(jìn)行加法運(yùn)算，這樣得出來的結(jié)果就是減法運(yùn)算最終的結(jié)果。

比如我們考慮一種簡(jiǎn)單的情況，當(dāng)w = 4時(shí)的無符號(hào)減法運(yùn)算，對(duì)于 5 - 4這個(gè)減法運(yùn)算來說，我們可以由 5 + 4-1（其中4-1是4的逆元的意思，不是1/4的意思）來替代這個(gè)減法運(yùn)算。

為了更加直觀，LZ帶各位來算一下，首先4的逆元根據(jù)上面的公式可以得到為 4-1 = 24 - 4 = 12 。那么我們現(xiàn)在需要對(duì)5和12進(jìn)行加法運(yùn)算，它們的位表示分別為 0101和1100，結(jié)果為10001，也就是十進(jìn)制17的位表示。不過由于我們的w = 4，因此截?cái)嘀蠼Y(jié)果為0001，也就是十進(jìn)制的1。最終可以得到 5 - 4 = 1。

對(duì)于5 - 4來說，是考慮的結(jié)果為正的情況。或許有的猿友會(huì)對(duì)結(jié)果為負(fù)或者說是無符號(hào)數(shù)溢出的情況下有疑問，因此LZ這里對(duì)這種情況也做一個(gè)簡(jiǎn)單的介紹。我們考慮一個(gè)簡(jiǎn)單的計(jì)算 0 - 1，我們可以得到1-1 = 24 - 1 = 15。此時(shí)對(duì)0和15進(jìn)行加法運(yùn)算，他們的位表示分別為0000和1111，結(jié)果為1111。

看到這里估計(jì)有的猿友會(huì)奇怪了，這怎么回事，0 - 1 = 15？

當(dāng)然不是，這個(gè)結(jié)果其實(shí)是正確的。考慮使用補(bǔ)碼編碼來解析1111這個(gè)位表示，它代表的值就是-1。15是1111這個(gè)位表示在無符號(hào)編碼情況下的解析結(jié)果。

因此LZ這里也給出一個(gè)公式，就是對(duì)于兩個(gè)整數(shù)x和y來說，x - y = x + y-1。這里需要特別說明的是，這個(gè)公式代表的意義是位表示，而不是實(shí)際的數(shù)值。

文章小結(jié)

本次我們主要介紹了二進(jìn)制整數(shù)的加法運(yùn)算，除此之外LZ還多加了一部分，就是減法的簡(jiǎn)單介紹。下一章我們將繼續(xù)講解整數(shù)的乘除法運(yùn)算。