寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內不得使用+、-、*、/四則運算符號。

基本解題思路

回顧十進制加法原理

以 5 + 7 = 12 為例，分步走：

1. 相加各位的值，不算進位，得到2。
2. 計算進位值，得到10。如果這一步的進位值為0，那么第一步得到的值就是最終結果。
3. 重復上述兩步，只是相加的值變成上述兩步的得到的結果2和10，得到12。

相同思想運用于二進制加法運算

同樣我們可以用三步走的方式計算二進制值相加，：

1. 相加各位的值，不算進位，得到 010，二進制每位相加就相當于各位做異或操作，101 ^ 111。
2. 計算進位值，得到 1010，相當于各位做與操作得到 101，再向左移一位得到 1010，(101 & 111) << 1。
3. 重復上述兩步， 各位相加 010 ^ 1010 = 1000，進位值為 100 = (010 & 1010) << 1 。
4. 繼續(xù)重復上述兩步：1000 ^ 100 = 1100，進位值為 0，跳出循環(huán)，1100 為最終結果。

代碼實現(xiàn)

這里暫且沿著上述的思路，方便起見，用另一門動態(tài)語言 JavaScript 來實現(xiàn)題目的要求：

function add(num1, num2) {
    // write code here
    while (num2 !== 0) {
        let sum = num1 ^ num2
        let carray = (num1 & num2) << 1
        num1 = sum
        num2 = carray
    }
    return num1
}

從最終運行結果可以看出，上述代碼是可以通過 OJ 的測試的：

image.png

Python 遇到的問題

用 Python 初步實現(xiàn)代碼

將運行環(huán)境切換到 Python，根據(jù) JS 的代碼如法炮制：

class Solution:
    def Add(self, num1, num2):
        while num2:
            result = (num1 ^ num2)
            carry = ((num1 & num2) << 1)
            num1 = result
            num2 = carry
        return result

在 VSCode 中自行運行此段代碼出現(xiàn)了無限循環(huán)無法退出得到返回結果的情況，提交到 OJ 上自然出現(xiàn)報錯，提示如下：

不通過

您的代碼已保存
運行超時:您的程序未能在規(guī)定時間內運行結束，請檢查是否循環(huán)有錯或算法復雜度過大。
case通過率為0.00%

問題的初步分析

經(jīng)過進一步的調試分析，再經(jīng)過對 Python 的相關資料查閱，得出了此問題的根源在于 Python 中整型變量的一些特性：

在 Python 2 時代，整型有 int 類型和 long 長整型，int 長度為機器位長，通常都是 32 位，超過這個范圍的整數(shù)就自動當長整數(shù)處理，而長整數(shù)的范圍幾乎完全沒限制。

在 Python 3 后，統(tǒng)一使用了 long 長整型。這也是吸引科研人員的一部分了，適合大數(shù)據(jù)運算，不會溢出，也不會有其他語言那樣還分短整型、整型和長整型等等。因此 Python 就降低其他行業(yè)的學習門檻了。

所以最關鍵的問題就出在，Python 中的整型變量不會溢出之上。至于要理解這一點，需要復習一下 計算機組成原理 的一些基礎知識。

計算機的一些基礎知識

機器數(shù)和真值

機器數(shù)

一個數(shù)在計算機中的二進制表示形式，叫做這個數(shù)的機器數(shù)。機器數(shù)是帶符號的，在計算機用一個數(shù)的最高位存放符號，正數(shù)為 0，負數(shù)為 1。

比如，十進制中的數(shù) +3 ，假設計算機字長為 8 位，轉換成二進制就是 00000011。同理 。

那么，這里的 00000011 和 10000011 就是機器數(shù)。

真值

因為第一位是符號位，所以機器數(shù)的形式值就不等于真正的數(shù)值。例如上面的有符號數(shù) 10000011，其最高位1代表負，其真正數(shù)值是 -3 而不是形式值131（10000011轉換成十進制等于131）。所以為區(qū)別起見，將帶符號位的機器數(shù)對應的真正數(shù)值稱為機器數(shù)的真值，例如：

原碼、反碼和補碼的基礎概念和計算方法

原碼

原碼就是符號位加上真值的絕對值，即用第一位表示符號，其余位表示值。比如如果是8位二進制：

第一位是符號位。因為第一位是符號位，所以 8 位二進制數(shù)的取值范圍就是：[1111 1111, 0111 1111]，即 [-127 , 127]。原碼是人腦最容易理解和計算的表示方式。

反碼

反碼的表示方法是：正數(shù)的反碼是其本身；負數(shù)的反碼是在其原碼的基礎上，符號位不變，其余各個位取反：

可見如果一個反碼表示的是負數(shù)，人腦無法直觀的看出來它的數(shù)值。通常要將其轉換成原碼再計算。

補碼

補碼的表示方法是：正數(shù)的補碼就是其本身；負數(shù)的補碼是在其原碼的基礎上，符號位不變，其余各位取反, 最后 +1（即在反碼的基礎上 +1）：

對于負數(shù)，補碼表示方式也是人腦無法直觀看出其數(shù)值的。通常也需要轉換成原碼在計算其數(shù)值。

計算方法

人腦可以知道第一位是符號位，在計算的時候我們會根據(jù)符號位，選擇對真值區(qū)域的加減。但是對于計算機，加減乘數(shù)已經(jīng)是最基礎的運算，要設計的盡量簡單。計算機辨別 符號位 顯然會讓計算機的基礎電路設計變得十分復雜。于是人們想出了將符號位也參與運算的方法。根據(jù)運算法則減去一個正數(shù)等于加上一個負數(shù)，即：1 - 1 = 1 + (-1) = 0，所以機器可以只有加法而沒有減法，這樣計算機運算的設計就更簡單了。

原碼計算十進制的表達式：

如果用原碼表示，讓符號位也參與計算，顯然對于減法來說，結果是不正確的。這也就是為何計算機內部不使用原碼表示一個數(shù)，為了解決原碼做減法的問題, 出現(xiàn)了反碼：

發(fā)現(xiàn)用反碼計算減法，結果的真值部分是正確的。而唯一的問題其實就出現(xiàn)在 0 這個特殊的數(shù)值上。雖然人們理解上 +0 和 -0 是一樣的，但是 0 帶符號是沒有任何意義的。而且會有 和 兩個編碼表示0。

于是補碼的出現(xiàn)，解決了 0 的符號以及兩個編碼的問題：

這樣 0 用 表示，而以前出現(xiàn)問題的 -0 則不存在了。而且可以用 表示 -128：

-1 - 127 的結果應該是 -128，在用補碼運算的結果中， 就是 -128。但是注意因為實際上是使用以前的 -0 的補碼來表示 -128，所以 -128 并沒有原碼和反碼表示。(對 -128 的補碼表示 算出來的原碼是，這是不正確的。)

使用補碼，不僅僅修復了 0 的符號以及存在兩個編碼的問題，而且還能夠多表示一個最低數(shù)。這就是為什么8位二進制，使用原碼或反碼表示的范圍為 [-127, +127]，而使用補碼表示的范圍為 [-128, 127]。

尋找 Python 造成的問題

因為機器使用補碼，所以對于編程中常用到的32位int類型，可以表示范圍是：，因為第一位表示的是符號位。而使用補碼表示時又可以多保存一個最小值。

而本題的 OJ 所使用的測試用例取值范圍也正是介于 ，為了更簡單清晰地對比解釋 Python 出現(xiàn)問題的原因和背后的原理，經(jīng)過一系列實驗，我選擇了 (1, -1) 來作為例子。同時為了明了地展現(xiàn)運行的過程，這里在正常運行的 JS 代碼當中的循環(huán)結構體里加入一句打印語句，來觀測每次 num2 對應的結果：

function add(num1, num2) {
    while (num2 != 0) {
        let sum = num1 ^ num2
        let carray = (num1 & num2) << 1
        num1 = sum
        num2 = carray
        console.log(num2) //插入的打印語句
    }
    return num1
}

console.log("1 + (-1) = " + add(1, -1))
console.log("-(2^31) = " + -(2 ** 31))

打印結果如下所示：

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0
1 + (-1) = 0
-(2^31) = -2147483648

從結果可以很清晰地看出，當循環(huán)執(zhí)行到倒數(shù)第二步的時候，此刻 num2 的數(shù)值為 ，正好觸碰到了 32 位 int 類型的邊界。如果再執(zhí)行一步算數(shù)左移動 <<，那么將溢出得到 0，從而終止循環(huán)。

現(xiàn)在需要類似地執(zhí)行 Python 之前那一段不完全正確的代碼來對比結果，由于那一段代碼會陷入無限循環(huán)的狀態(tài)，所以需要打斷點調試手動來到上述的倒數(shù)第二步的位置，結果如下所示：

image.png

結果顯而易見了，同樣的地方，但是 Python 執(zhí)行出來結果為 2147483648 = ，這超出了 int 類型的邊界（）了。這就是 Python 和其他語言不太一樣的地方，就是對負數(shù)的二進制表示。Python 里的數(shù)是無所謂 Overflow 的，即沒有位數(shù)限制，因此也就無所謂補碼，因為補碼都是相對于位數(shù)來說的，32 位補碼和 16 位補碼，肯定是不一樣的。但是這樣就導致了一個問題，就是無法直接得到32位二進制補碼。

Python 中正負數(shù)的判斷及其還原

正數(shù)與邊界數(shù) 0xffffffff 按位與（&） 操作后 仍得到這個數(shù)本身：

15 & 0xffffffff —> 15

負數(shù)與邊界數(shù)按位與（&） 操作后 得到的是對應二進制數(shù)的真值：

-1 & 0xffffffff —> 4294967295

。而 1111,1111,1111,1111,1111,1111,1111,1111 正好是 -1 在 int 類型下的補碼表示。

為了便于理解，以一個小邊界為例：

-15 & 0xff —> 241

241 對應的二進制數(shù)為： 11110001，8 位狀態(tài)下 -15 的補碼。

通過查看符號位（最高位，即與 0x7ffffffff ）斷a為正數(shù)還是負數(shù)，正數(shù)則直接返回。負數(shù)則返回-((num1 - 1) ^ 0xffffffff)。所以最終的正確代碼為：

class Solution:
    def Add(self, num1, num2):
 
        while num2:
            result = (num1 ^ num2) & 0xffffffff
            carry = ((num1 & num2) << 1) & 0xffffffff
            num1 = result
            num2 = carry
        if num1 <= 0x7fffffff:
            result = num1
        else:
            result = -((num1 - 1) ^ 0xffffffff)
        return result

此題另外一種解法

可以用 ctypes 來在 Python 中定義 C 語言的數(shù)據(jù)類型：

import ctypes
class Solution:
    def Add(self, num1, num2):
        a = ctypes.c_int32(num1).value
        b = ctypes.c_int32(num2).value
        while b != 0:
            carry = ctypes.c_int32(a & b).value
            a = ctypes.c_int32(a ^ b).value
            b = ctypes.c_int32(carry << 1).value
 
        return a