寫一個函數(shù)丑念，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+结蟋、-脯倚、*、/四則運算符號。
基本解題思路
回顧十進制加法原理
以 5 + 7 = 12 為例推正，分步走：
- 相加各位的值恍涂，不算進位，得到2植榕。
- 計算進位值再沧，得到10。如果這一步的進位值為0尊残，那么第一步得到的值就是最終結(jié)果炒瘸。
- 重復(fù)上述兩步，只是相加的值變成上述兩步的得到的結(jié)果2和10寝衫，得到12顷扩。
相同思想運用于二進制加法運算
同樣我們可以用三步走的方式計算二進制值相加，：
- 相加各位的值隘截，不算進位，得到 010汹胃，二進制每位相加就相當(dāng)于各位做異或操作婶芭，101 ^ 111。
- 計算進位值着饥，得到 1010雕擂，相當(dāng)于各位做與操作得到 101，再向左移一位得到 1010贱勃，(101 & 111) << 1。
- 重復(fù)上述兩步谤逼， 各位相加 010 ^ 1010 = 1000贵扰，進位值為 100 = (010 & 1010) << 1 。
- 繼續(xù)重復(fù)上述兩步：1000 ^ 100 = 1100流部，進位值為 0戚绕，跳出循環(huán)，1100 為最終結(jié)果枝冀。
代碼實現(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
}
從最終運行結(jié)果可以看出果漾，上述代碼是可以通過 OJ 的測試的：
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)無法退出得到返回結(jié)果的情況，提交到 OJ 上自然出現(xiàn)報錯绒障，提示如下：
不通過
您的代碼已保存
運行超時:您的程序未能在規(guī)定時間內(nèi)運行結(jié)束吨凑，請檢查是否循環(huán)有錯或算法復(fù)雜度過大。
case通過率為0.00%
問題的初步分析
經(jīng)過進一步的調(diào)試分析，再經(jīng)過對 Python 的相關(guān)資料查閱鸵钝，得出了此問題的根源在于 Python 中整型變量的一些特性：
在 Python 2 時代糙臼，整型有 int 類型和 long 長整型，int 長度為機器位長恩商，通常都是 32 位变逃，超過這個范圍的整數(shù)就自動當(dāng)長整數(shù)處理，而長整數(shù)的范圍幾乎完全沒限制怠堪。
在 Python 3 后揽乱，統(tǒng)一使用了 long 長整型。這也是吸引科研人員的一部分了研叫，適合大數(shù)據(jù)運算锤窑，不會溢出，也不會有其他語言那樣還分短整型嚷炉、整型和長整型等等渊啰。因此 Python 就降低其他行業(yè)的學(xué)習(xí)門檻了。
所以最關(guān)鍵的問題就出在申屹，Python 中的整型變量不會溢出之上绘证。至于要理解這一點，需要復(fù)習(xí)一下 計算機組成原理 的一些基礎(chǔ)知識哗讥。
計算機的一些基礎(chǔ)知識
機器數(shù)和真值
機器數(shù)
一個數(shù)在計算機中的二進制表示形式嚷那，叫做這個數(shù)的機器數(shù)。機器數(shù)是帶符號的杆煞，在計算機用一個數(shù)的最高位存放符號魏宽，正數(shù)為 0，負數(shù)為 1决乎。
比如队询，十進制中的數(shù) +3 ，假設(shè)計算機字長為 8 位构诚，轉(zhuǎn)換成二進制就是 00000011蚌斩。同理 。
那么范嘱，這里的 00000011 和 10000011 就是機器數(shù)送膳。
真值
因為第一位是符號位，所以機器數(shù)的形式值就不等于真正的數(shù)值丑蛤。例如上面的有符號數(shù) 10000011叠聋，其最高位1代表負，其真正數(shù)值是 -3 而不是形式值131（10000011轉(zhuǎn)換成十進制等于131）受裹。所以為區(qū)別起見晒奕，將帶符號位的機器數(shù)對應(yīng)的真正數(shù)值稱為機器數(shù)的真值，例如：
原碼、反碼和補碼的基礎(chǔ)概念和計算方法
原碼
原碼就是符號位加上真值的絕對值脑慧，即用第一位表示符號魄眉，其余位表示值。比如如果是8位二進制：
第一位是符號位闷袒。因為第一位是符號位坑律，所以 8 位二進制數(shù)的取值范圍就是：[1111 1111, 0111 1111]，即 [-127 , 127]囊骤。原碼是人腦最容易理解和計算的表示方式晃择。
反碼
反碼的表示方法是：正數(shù)的反碼是其本身；負數(shù)的反碼是在其原碼的基礎(chǔ)上也物，符號位不變宫屠，其余各個位取反：
可見如果一個反碼表示的是負數(shù)，人腦無法直觀的看出來它的數(shù)值滑蚯。通常要將其轉(zhuǎn)換成原碼再計算浪蹂。
補碼
補碼的表示方法是：正數(shù)的補碼就是其本身；負數(shù)的補碼是在其原碼的基礎(chǔ)上告材，符號位不變坤次，其余各位取反, 最后 +1（即在反碼的基礎(chǔ)上 +1）：
對于負數(shù)，補碼表示方式也是人腦無法直觀看出其數(shù)值的斥赋。通常也需要轉(zhuǎn)換成原碼在計算其數(shù)值缰猴。
計算方法
人腦可以知道第一位是符號位，在計算的時候我們會根據(jù)符號位疤剑，選擇對真值區(qū)域的加減滑绒。但是對于計算機，加減乘數(shù)已經(jīng)是最基礎(chǔ)的運算隘膘，要設(shè)計的盡量簡單疑故。計算機辨別 符號位 顯然會讓計算機的基礎(chǔ)電路設(shè)計變得十分復(fù)雜。于是人們想出了將符號位也參與運算的方法棘幸。根據(jù)運算法則減去一個正數(shù)等于加上一個負數(shù)，即：1 - 1 = 1 + (-1) = 0倦零，所以機器可以只有加法而沒有減法误续，這樣計算機運算的設(shè)計就更簡單了。
原碼計算十進制的表達式：
如果用原碼表示扫茅，讓符號位也參與計算蹋嵌，顯然對于減法來說，結(jié)果是不正確的葫隙。這也就是為何計算機內(nèi)部不使用原碼表示一個數(shù)栽烂，為了解決原碼做減法的問題, 出現(xiàn)了反碼：
發(fā)現(xiàn)用反碼計算減法，結(jié)果的真值部分是正確的。而唯一的問題其實就出現(xiàn)在 0 這個特殊的數(shù)值上腺办。雖然人們理解上 +0 和 -0 是一樣的焰手，但是 0 帶符號是沒有任何意義的。而且會有 和
兩個編碼表示0怀喉。
于是補碼的出現(xiàn)书妻，解決了 0 的符號以及兩個編碼的問題：
這樣 0 用 表示，而以前出現(xiàn)問題的 -0 則不存在了躬拢。而且可以用
表示 -128：
-1 - 127 的結(jié)果應(yīng)該是 -128躲履，在用補碼運算的結(jié)果中， 就是 -128聊闯。但是注意因為實際上是使用以前的 -0 的補碼來表示 -128工猜，所以 -128 并沒有原碼和反碼表示。(對 -128 的補碼表示
算出來的原碼是
菱蔬，這是不正確的篷帅。)
使用補碼，不僅僅修復(fù)了 0 的符號以及存在兩個編碼的問題汗销，而且還能夠多表示一個最低數(shù)犹褒。這就是為什么8位二進制，使用原碼或反碼表示的范圍為 [-127, +127]弛针，而使用補碼表示的范圍為 [-128, 127]叠骑。
尋找 Python 造成的問題
因為機器使用補碼，所以對于編程中常用到的32位int類型削茁，可以表示范圍是：宙枷，因為第一位表示的是符號位。而使用補碼表示時又可以多保存一個最小值茧跋。
而本題的 OJ 所使用的測試用例取值范圍也正是介于 慰丛，為了更簡單清晰地對比解釋 Python 出現(xiàn)問題的原因和背后的原理，經(jīng)過一系列實驗瘾杭，我選擇了 (1, -1) 來作為例子诅病。同時為了明了地展現(xiàn)運行的過程，這里在正常運行的 JS 代碼當(dāng)中的循環(huán)結(jié)構(gòu)體里加入一句打印語句粥烁，來觀測每次 num2 對應(yīng)的結(jié)果：
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))
打印結(jié)果如下所示：
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
從結(jié)果可以很清晰地看出贤笆，當(dāng)循環(huán)執(zhí)行到倒數(shù)第二步的時候，此刻 num2 的數(shù)值為 讨阻，正好觸碰到了 32 位 int 類型的邊界芥永。如果再執(zhí)行一步算數(shù)左移動 <<，那么將溢出得到 0钝吮，從而終止循環(huán)埋涧。
現(xiàn)在需要類似地執(zhí)行 Python 之前那一段不完全正確的代碼來對比結(jié)果板辽，由于那一段代碼會陷入無限循環(huán)的狀態(tài)，所以需要打斷點調(diào)試手動來到上述的倒數(shù)第二步的位置棘催，結(jié)果如下所示：
結(jié)果顯而易見了劲弦，同樣的地方，但是 Python 執(zhí)行出來結(jié)果為 2147483648 = 巧鸭，這超出了 int 類型的邊界（
）了瓶您。這就是 Python 和其他語言不太一樣的地方，就是對負數(shù)的二進制表示纲仍。Python 里的數(shù)是無所謂 Overflow 的呀袱，即沒有位數(shù)限制，因此也就無所謂補碼郑叠，因為補碼都是相對于位數(shù)來說的夜赵，32 位補碼和 16 位補碼，肯定是不一樣的乡革。但是這樣就導(dǎo)致了一個問題寇僧，就是無法直接得到32位二進制補碼。
Python 中正負數(shù)的判斷及其還原
正數(shù)與邊界數(shù) 0xffffffff 按位與（&） 操作后 仍得到這個數(shù)本身：
15 & 0xffffffff —> 15
負數(shù)與邊界數(shù)按位與（&） 操作后 得到的是對應(yīng)二進制數(shù)的真值：
-1 & 0xffffffff —> 4294967295
沸版。而 1111,1111,1111,1111,1111,1111,1111,1111 正好是 -1 在 int 類型下的補碼表示嘁傀。
為了便于理解，以一個小邊界為例：
-15 & 0xff —> 241
241 對應(yīng)的二進制數(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
