第1章 整數

1.1 整數的基礎知識

整數是一種基本的數據類型。編程語言可能會提供占據不同內存空間的整數類型，每種類型能表示的整數的范圍也不相同。例如，Java中有4種不同的整數類型，分別為8位的byte（-2⁷～2⁷-1）、16位的short（-2¹⁵～2¹⁵-1）、32位的int（-2³¹～2³¹-1）和64位的long（-2⁶³～2⁶³-1）。

Java中的整數類型都是有符號整數，即如果整數的二進制表示的最高位為0則表示其為正數，如果整數的二進制表示的最高位為1則表示其為負數。有些語言（如C/C++）支持無符號整數。無符號整數無論二進制表示的最高位是0還是1，都表示其為一個正數。無符號的32位整數的范圍是0～2³²-1。

通常，編程語言中的整數運算都遵循四則運算規則，可以使用任意嵌套的小括號。需要注意的是，由于整數的范圍限制，如果計算結果超出了范圍就會產生溢出。產生溢出時運行不會出錯，但結果可能會出乎意料。如果除數為0，那么整數的除法在運行時將報錯。

面試題1：整數除法

分析：這個題目限制我們不能使用乘號和除號進行運算。一個直觀的解法是基于減法實現除法。例如，為了求得15/2的商，可以不斷地從15里減去2，當減去7個2之后余數是1，此時不能再減去更多的2，因此15/2的商是7。我們可以用一個循環實現這個過程。

但這個直觀的解法存在一個問題。當被除數很大但除數很小時，減法操作執行的次數會很多。例如，求（2³¹-1）/1，減1的操作將執行2³²-1次，需要很長的時間。如果被除數是n，那么這種解法的時間復雜度為O（n）。我們需要對這種解法進行優化。

可以將上述解法稍做調整。當被除數大于除數時，繼續比較判斷被除數是否大于除數的2倍，如果是，則繼續判斷被除數是否大于除數的4倍、8倍等。如果被除數最多大于除數的2^k倍，那么將被除數減去除數的2^k倍，然后將剩余的被除數重復前面的步驟。由于每次將除數翻倍，因此優化后的時間復雜度是O（logn）。

下面以15/2為例討論計算的過程。15大于2，也大于2的2倍（即4），還大于2的4倍（即8），但小于2的8倍（即16）。于是先將15減去8，還剩余7。由于減去的是除數的4倍，減去這部分對應的商是4。接下來對剩余的7和除數2進行比較，7大于2，大于2的2倍（即4），但小于2的4倍（即8），于是將7減去4，還剩余3。這一次減去的是除數2的2倍，對應的商是2。然后對剩余的3和除數2進行比較，3大于2，但小于2的2倍（即4），于是將3減去2，還剩余1。這一次減去的是除數的1倍，對應的商是1。最后剩余的數字是1，比除數小，不能再減去除數了。于是15/2的商是4+2+1，即7。

上述討論假設被除數和除數都是正整數。如果有負數則可以將它們先轉換成正數，計算正數的除法之后再根據需要調整商的正負號。例如，如果計算-15/2，則可以先計算15/2，得到的商是7。由于被除數和除數中有一個負數，因此商應該是負數，于是商應該是-7。

將負數轉換成正數存在一個小問題。對于32位的整數而言，最小的整數是-2³¹，最大的整數是2³¹-1。因此，如果將-2³¹轉換為正數則會導致溢出。由于將任意正數轉換為負數都不會溢出，因此可以先將正數都轉換成負數，用前面優化之后的減法計算兩個負數的除法，然后根據需要調整商的正負號。

最后討論可能的溢出。由于是整數的除法并且除數不等于0，因此商的絕對值一定小于或等于被除數的絕對值。因此，int型整數的除法只有一種情況會導致溢出，即（-2³¹）/（-1）。這是因為最大的正數為2³¹-1，2³¹超出了正數的范圍。

在全面地分析了使用減法實現除法的細節之后，我們可以開始編寫代碼。參考代碼如下所示：

上述代碼中的0x80000000為最小的int型整數，即-2³¹，0xc0000000是它的一半，即-2³⁰。

函數divideCore使用減法實現兩個負數的除法。當除數和被除數中有一個負數時，商為負數。因此，在使用函數divideCore計算商之后，需要再根據除數和被除數的負數的個數調整商的正負號。