引言

平時的編程過程中,，當(dāng)進(jìn)行整數(shù)運(yùn)算時,，經(jīng)常會遇到一些奇怪的結(jié)果，比如兩個正數(shù)加出負(fù)數(shù),，兩個負(fù)數(shù)可以加出一個正數(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é)果它們相加會得到一個負(fù)數(shù),。

接下來我們再來看看C語言當(dāng)中的例子，它也會具有同樣的特性,。

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

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

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

無符號加法

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

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

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

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

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

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

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

無符號的非

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

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

補(bǔ)碼加法

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

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

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

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

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

補(bǔ)碼的非

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

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

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

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

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

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

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

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

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

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

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

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

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

文章小結(jié)

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