x * x >= 0 一定成立嗎？

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

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

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

一、基礎知識

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

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

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

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

二、補碼編碼

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

那么，int 類型的數據可取值的范圍就是 0b0000 到 0b1111，轉化成十進制，也就是從 0 到 15。

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

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

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

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

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

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

試想 int_max + 1 是多少？0b0111 + 1 = 0b1000 = -8 。也就是說，「整型溢出」就是正數的增加超過了 int_max，導致符號位進位變為 1，變成了一個負數。

三、乘法運算

類似加法導致「整型溢出」，如果乘法得到的結果如果太大，也會導致溢出，這就是出現正數相乘得到負數的原因。

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

十進制中，乘以十的冪是最簡單的，往后加 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

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

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

四、最后總結

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

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

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

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 變量數值太大，導致 (lo + hi) 溢出得到負數，我們巧妙地避免了直接相加，仍然得到了相同的結果，這是二分查找算法的一個細節，值得學習。