深入理解計算機系統（十）：整數的運算

目錄

1、計算機整數運算的局限

2、無符號數加法運算

3、補碼加法運算　

4、無符號數乘法運算

5、補碼乘法

6、乘法優化

7、除法運算

8、總結

　　前面兩篇博客我們詳細講解了計算機中整數的表示，包括有符號和無符號（補碼編碼）的詳細介紹。那麼這篇博客我們將對它們的運算有個詳細的了解。

　　在講解之前首先看下面的一個程序，看看輸出結果是啥？

#include <stdio.h> int main(){ int i = 2147483647; printf("%d
",i+1); printf("%d
",i+i); return 0;}

　　結果是：

　　我們預期的:

i+1 = 2147483647 + 1 = 2147483648

　　i+i = 2147483647 + 2147483647 = 4 294 967 294

　　為什麼程序中的結果和我們數學中的常識會有這麼大的區別？兩個正數相加得到負數。這就需要我們理解計算機中整數的運算原理。

正文：

1、計算機整數運算的局限

　　我們知道計算機是用二進位序列來表示數的。而二進位序列的長度是和計算機本身的字長有關。不同的數據類型定義的二進位序列長度不一樣，即不同的數據類型表示數的大小範圍是不一樣的。但是不管是什麼數據類型，它定義的二進位序列長度是有限的，即它表示的數的大小範圍是有限的。

　　所以兩個數做運算，如果結果超出了定義數據類型所表示數的大小範圍，那麼結果將會出現失真。而且這個失真的結果也不是隨機的，而是有跡可循的，那麼到底是怎麼產生失真的，請接著往下面看。

　　PS：下面給出 64 位機器上C語言的整型數據類型的取值範圍。本篇博客中程序運行環境都是在64位系統中進行。

2、無符號數加法運算、

　　前面我們講過，對於一個 w 位的無符號二進位整數[xw-1 , xw-2 , … , x2 , x1 , x0]，其值大小滿足 0 <= x <= 2w-1.

如果兩個無符號數相加，那麼其結果應該是 0 <= x+y <=2w+1-2。很顯然表示這個範圍的數必須要 w+1 位二進位。

　　當我們對無符號數做加法運算的時候，如果結果超過了 2w-1，那麼這個結果就會失真。

#include <stdio.h> int main(){ unsigned short int i = 65535; unsigned short int j = i+1; printf("%u
",j); return 0;}

　　結果為：

　　對於上面的程序，我們是在64位系統中進行運算。由上面給出的圖片我們可以知道 unsigned short int 在計算機中佔用 2 個位元組。表示的數據範圍是 0——216-1，即0——65535

　　我們在程序中定義 i = 65535,那麼 i+1=65536,這個結果是超出了 unsigned short 表示的數據範圍。所以結果失真了，但是結果為什麼是 0 呢？

　　上一篇博客我們講過C語言中二進位數的截斷：

將一個 w 位的數 [xw-1 , xw-2 , … , x2 , x1 , x0] 截斷為一個 k 位數字時，我們會丟棄高 w-k 位。得到 [xk-1 , xk-2 , … , x2 , x1 , x0]

　　對於上面的 i = 65535,二進位表示為：[1111 1111 1111 1111]，加1 結果為 65536，用二進位表示為 [1 0000 0000 0000 0000],為了將結果保持在 4個位元組，即32位二進位序列，我們去掉最高位的 1，那麼結果就變成了 [0000 0000 0000 0000]，也就是列印出來的結果 0.

　　一般而言，無符號加法等價於計算和模上2w

比如上面的兩者計算和為 65536,模上 2w，即模上216=65536，結果為0

　　ps：模表示兩者相處取余

現在定義 0<= x,y <2w,那麼它們運算滿足下面關係：

　　注意：當 2w <= x+y < 2w+1，對 x + y 進行2w的取模運算，與 x + y - 2w是等價的。

所以如果兩個無符號整數作加法運算。當 x+y < 2w 時，它們的結果不變；當 2w <= x+y < 2w+1，它們的結果為 x+y-2w

3、補碼加法運算　

　　對於補碼加法運算，因為補碼編碼是表示有符號的整數。

　　對於一個 w 位的補碼二進位整數[xw-1 , xw-2 , … , x2 , x1 , x0]，其值大小滿足 -2w-1 <= x <= 2w-1-1。那麼 -2w <= x+y <=2w-1

想要表示上面的兩個數相加和的範圍，那麼可能需要 w+1 來表示。這裡我們也需要截取。

　　與無符號加法運算不同，補碼加法會出現三種情況：正溢出、正常、負溢出。定義如下：

　　　　範圍在 -2w-1 <= x，y <= 2w-1-1 做加法運算時，滿足：

　　簡單來說：補碼加法運算就是先按照無符號加法進行運算，而後在進行無符號和有符號的轉換。

這裡我們看個例子：

#include <stdio.h> int main(){ short int i = -32768; short int j = i-1; printf("%d
",j); return 0;}

　　結果為：

為什麼 -32768-1 結果會是 32767？

　　根據上面的公式：

　　我們需要先將 -32768 和 -1 分別轉換成無符號數進行加法運算，然後對得到的結果轉換成有符號數。

　　①、-32768 轉換成無符號數也就是 -32768+2^16=32768 　

　　②、-1 轉換成無符號數也就是-1+2^16=65535　

　　③、將上面兩步的結果相加，然後轉換成有符號數：

　　　　即（65535+32768）-2^16=65535+32768-65536=32767

　這個過程用到的公式分別有：

4、無符號數乘法運算

　　對於一個 w 位的無符號二進位整數[xw-1 , xw-2 , … , x2 , x1 , x0]，其值大小滿足 0 <= x <= 2w-1.

如果兩個無符號數相乘，那麼其結果應該是 0 <= x*y <=（2w-1）2=22w-2w+1+1。很顯然表示這個範圍的數可能需要 2w 位來表示。也就是 2w 位的整數乘積的低 w 位表示的值。根據我們前面講的截斷原理：可以看做是計算乘積模2w,即：

#include <stdio.h> int main(){ unsigned short int i = 2; unsigned short int j = i*2; printf("%u
",j); return 0;}

　　比如上面的程序結果是：（2*2）mod 216=4 mod 65536=4

5、補碼乘法

　　對於一個 w 位的補碼二進位整數[xw-1 , xw-2 , … , x2 , x1 , x0]，其值大小滿足 -2w-1 <= x <= 2w-1-1。

　　那麼它們的乘積x*y的取值範圍在 -2w-1*（2w-1-1）=22w-2+2w-1 到 -2w-1*2w-1=-22w-2 之間。

同理 2w 位的整數乘積的低 w 位表示的值。根據我們前面講的截斷原理：補碼乘法運算公式為

　　假設對於w位的兩個補碼數來說，它們的乘積的低w位與無符號數乘積的低w位是一樣的。這意味著計算機可以使用一個指令執行無符號和補碼的乘法運算。下面我們來證明：

　　其中x』和y』分別代表x和y的補碼編碼。

　　那麼：

（應用有符號轉為無符號公式可得）

　　即：　　　　　　　　　　

（2w mod 2w = 0）

　　由於模運算符，所有帶權重 2w 的項都丟棄了，因此我們看到 x*y 和 x』*y』 的低 w 位是相同的。

6、乘法優化

　　由於在大多數機器上，整數乘法指令相當慢，需要 10 個或多個時鐘周期，而其他整數運算（比如加法、減法、位級運算和移位）只需要 1 個時鐘周期。

　　因此編譯器使用了一項重要的優化，使用移位和加法的組合來代替乘法。

結論：對於一個w位的二進位數來說，它與2k的乘積，等同於這個二進位數左移k位，在低位補k個0。

　　證明過程如下：

　　我們前面說過，整數乘法代價要比移位和加法代價大得多。那麼C編譯器會以移位、加法、減法的組合來消除很多整數乘以常數的情況。

　　比如：

　　　　計算 x*14 的乘積。 由於 14 = 23+22+21 ，那麼編譯器會將乘法重寫為（x<<3）+（x<<2）+（x<<1）。這樣就將乘法替換為三個移位和兩個加法。無論 x 是無符號還是補碼，甚至當乘法會導致溢出時，兩個計算都會得到一樣的結果。

　　　　更好的編譯器，可能會將 14 = 24-21。那麼就會變成（x<<4）-（x<<1），只需要兩個移位和一個減法。

7、除法運算

　　實際上在大多數機器上，整數除法要比整數乘法更慢，需要 30 或更多個時鐘周期。

結論：對於除以 2 的冪可以用移位來運算。無符號除法使用邏輯移位，補碼除法使用算術移位。

　　①、邏輯右移在左端補k 個0。C語言中對於無符號數據必須邏輯右移。

　　對於位向量[xw-1,xw-2,...,x0]邏輯右移 k 位會得到位向量：[0,...,0,xw-1,xw-2,...,xk]。轉換成除法即 x/2k，從結果我們可以看出邏輯移位出現小數，總是舍入到零，比如 7/2應該是 3，而不是4

　　②、算術右移是在左端補 k 個最高有效位的值。對於一個正整數，由於最高有效位是 0 ，所以效果和邏輯右移是一樣的；對於非負數，算術右移 k 位與除以 2k 是一樣的。

　　　　對於結果不需要舍入的情況結果是正確的。但是對於結果需要舍入的時候，算術右移導致的結果是向下舍入，比如 -7/2應該是 -3，而不是 -4。這是錯誤的。

8、總結

　　那麼本篇博客結束我們對於整數的表示以及運算都已經了解了。注意整數的運算我沒有將減法，其實減法也就是轉換為補碼相加。而且計算機中也只有加法器，是沒有減法器的。我們只需要將減法轉換為加法運算即可。

　　整數的表示和運算結束了，下一篇博客我們將會講解浮點數，也就是有小數的數。