數(shù)學(xué)上一個(gè)數(shù)的平方當(dāng)然大于等于 0，但對(duì)于大多數(shù)編程語(yǔ)言，當(dāng) 46341 <= int x <= 65535 時(shí)，x 的平方結(jié)果會(huì)是負(fù)數(shù) 。

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

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

一、基礎(chǔ)知識(shí)

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

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

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

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

二、補(bǔ)碼編碼

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

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

但問(wèn)題是，int 類(lèi)型是有符號(hào)整數(shù)，也要表示負(fù)數(shù)啊，按上面這種直接轉(zhuǎn)換成十進(jìn)制的方法，沒(méi)辦法表示負(fù)數(shù)。事實(shí)上，上面的編碼方式是 unsigned int 無(wú)符號(hào)整數(shù)類(lèi)型使用的。

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

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

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

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

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

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

三、乘法運(yùn)算

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

二進(jìn)制的乘法跟十進(jìn)制一模一樣的，這里我們講一種很簡(jiǎn)單的情況：乘以二的冪。

十進(jìn)制中，乘以十的冪是最簡(jiǎn)單的，往后加 0 就行了，比如說(shuō) 5 * 100 = 500，相當(dāng)于把 5 左移了兩位，用 0 填補(bǔ)。同理，二進(jìn)制中一樣的，比如 0b0011 * 0b0100 = 0b1100。因?yàn)?0b0100 就是 2 的二次冪，直接把 0b0011 左移兩位，用 0 填補(bǔ)即可。

那么，如果乘的不是二的冪，怎么辦呢？也很簡(jiǎn)單，類(lèi)比十進(jìn)制，5 * 99 怎么計(jì)算？小學(xué)我們就學(xué)過(guò)一種巧算方法，把 99 變成 100 - 1 進(jìn)行計(jì)算：

類(lèi)似的，二進(jìn)制也可以使用這種技巧：

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

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

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

四、最后總結(jié)

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

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

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

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;
        // ...
    }
}

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