數(shù)學上一個數(shù)的平方當然大于等于 0，但對于大多數(shù)編程語言，當 46341 <= int x <= 65535 時，x 的平方結(jié)果會是負數(shù) 。

其實出現(xiàn)這種情況的原因是「整型溢出」，這篇文章帶大家深入理解計算機對數(shù)字的表示和計算方式，弄明白「整型溢出」的原因，為什么會出現(xiàn)這么詭異的行為。

LeetCode 上有不少算法題涉及處理整型溢出的細節(jié)，在文章的最后會列舉一些常見的避免整型溢出的方法。

一、基礎(chǔ)知識

首先明確一下位（bit，音譯比特）和字節(jié)（byte）到底是什么。

它們類似米、厘米，都是大小單位。一個「位」即一個二進制位，就是一個 0 或者 1 。一個「字節(jié)」的大小是 8 個「位」，即 1 byte = 8 bit。

拿 C/C++ 為例，大部分基礎(chǔ)數(shù)據(jù)類型的大小是固定的，比如 char 類型大小為 1 byte 即 8 bit，int 類型大小為 4 byte 即 32 bit，本文主要以 int 為例進行探討。

既然一個 int 類型由 32 個二進制位組成，那么它表示數(shù)字的大小一定有上限和下限，剛才計算出的奇怪結(jié)果就和 int 的編碼方式有關(guān)。

二、補碼編碼

首先進行約定，我們以 0b 開頭代表二進制數(shù)，并且假設(shè)一個 int 類型的大小只有 4 bit 即 4 個二進制位，而不是 32 bit，以方便說明其原理。

那么，int 類型的數(shù)據(jù)可取值的范圍就是 0b0000 到 0b1111，轉(zhuǎn)化成十進制，也就是從 0 到 15。

但問題是，int 類型是有符號整數(shù)，也要表示負數(shù)啊，按上面這種直接轉(zhuǎn)換成十進制的方法，沒辦法表示負數(shù)。事實上，上面的編碼方式是 unsigned int 無符號整數(shù)類型使用的。

為了讓 int 能夠表示負數(shù)，常用的編碼方式叫做「補碼編碼」，把二進制的最高位作為符號位，即最高位系數(shù)要加一個負號。很簡單，舉幾個例子你就明白了。

通過上面的例子，你應(yīng)該能理解這種編碼方式了，這種編碼方式能夠表示的最大正數(shù) int_max = 0b0111 = 7，最小負數(shù) int_min = 0b1000 = -8，所以 int 類型能夠表示從 -8 到 7 的有符號整數(shù)。

細心的讀者可能發(fā)現(xiàn)，這種編碼方式「不對稱」，按道理最大正數(shù)和最小負數(shù)的絕對值應(yīng)該相等才對，否則如果對 int_min 取相反數(shù)會怎么樣，沒有正數(shù)可以表示出來呀？

其實，這確實是個問題，C 語言的處理方式是，-int_min 仍然等于 int_min，所以說負數(shù)的相反數(shù)不一定是正數(shù)哦，int_min 是唯一一個特例。

現(xiàn)在你理解了「補碼編碼」，掌握了計算機表示整數(shù)的方式，你也就很容易理解所謂的「整型溢出」是什么，為什么有時候兩個正數(shù)相加突然變成了負數(shù)：

試想 int_max + 1 是多少？0b0111 + 1 = 0b1000 = -8 。也就是說，「整型溢出」就是正數(shù)的增加超過了 int_max，導(dǎo)致符號位進位變?yōu)?1，變成了一個負數(shù)。

三、乘法運算

類似加法導(dǎo)致「整型溢出」，如果乘法得到的結(jié)果如果太大，也會導(dǎo)致溢出，這就是出現(xiàn)正數(shù)相乘得到負數(shù)的原因。

二進制的乘法跟十進制一模一樣的，這里我們講一種很簡單的情況：乘以二的冪。

十進制中，乘以十的冪是最簡單的，往后加 0 就行了，比如說 5 * 100 = 500，相當于把 5 左移了兩位，用 0 填補。同理，二進制中一樣的，比如 0b0011 * 0b0100 = 0b1100。因為 0b0100 就是 2 的二次冪，直接把 0b0011 左移兩位，用 0 填補即可。

那么，如果乘的不是二的冪，怎么辦呢？也很簡單，類比十進制，5 * 99 怎么計算？小學我們就學過一種巧算方法，把 99 變成 100 - 1 進行計算：

類似的，二進制也可以使用這種技巧：

  0b0011 × 0b0011 
= 0b0011 × (0b0100 - 1) 
= 0b1100 - 0b0011 
= 0b1001

從計算的角度來看，上述過程是完全正確的，但是考慮「補碼編碼」方式，仍然假設(shè) int 大小為 4 bit，你應(yīng)該可以看到問題。

這就是題目中說的詭異情況發(fā)生的原因。拿 int x = 65535 為例，實際中 int 有 32 個二進制位，65535 的二進制表示是 0b000...111，有 16 個連續(xù)的 0 接著 16 個連續(xù)的 1。類比上面的例子，通過巧算方法，后 16 位 1 會左移 16 位，導(dǎo)致作為符號位的最高位變成 1，直接導(dǎo)致結(jié)果成為負數(shù)。

四、最后總結(jié)

可見，「整型溢出」并不是啥高深的知識，無非是計算結(jié)果太大導(dǎo)致符號位發(fā)生不正常的改變而已。

如何避免整型溢出呢？最簡單的辦法就是在適當?shù)牡胤竭M行輸入數(shù)字大小測試，對溢出的風險進行處理，或者將 int 型更換成 long int 或 long long int ，即長整型。因為長整型的大小是 64 bit，雖然也會發(fā)生溢出，但是溢出的閾值會大很多，足以應(yīng)付一般的情況。

還有一個常見的防止溢出的技巧，在二分查找算法中就有用到，我們看一下二分查找算法：

int binarySearch(int[] nums, int val) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        // int mid = (lo + hi) / 2;
        int mid = lo + (hi - lo) / 2;
        // ...
    }
}

計算 int mid 變量時，為了防止 lo 和 hi 變量數(shù)值太大，導(dǎo)致 (lo + hi) 溢出得到負數(shù)，我們巧妙地避免了直接相加，仍然得到了相同的結(jié)果，這是二分查找算法的一個細節(jié)，值得學習。