題目
難度：★★☆☆☆
類型：數(shù)學(xué)
不使用運(yùn)算符 + 和 - ???????迟杂，計(jì)算兩整數(shù) ???????a 、b ???????之和本慕。
示例
示例 1:
輸入: a = 1, b = 2
輸出: 3
示例 2:
輸入: a = -2, b = 3
輸出: 1
解答
這道題目就是實(shí)現(xiàn)：
class Solution(object):
def getSum(self, num1, num2):
return num1 + num2
雖然這么寫肯定是可以通過的排拷，但是這個(gè)“+”就是題目想讓我們實(shí)現(xiàn)的。
無符號(hào)整數(shù)相加
我們先來看一下無符號(hào)整數(shù)在計(jì)算機(jī)內(nèi)部是如何進(jìn)行加法計(jì)算的锅尘。
和十進(jìn)制相同监氢，二進(jìn)制也是通過從低位到高位依次相加實(shí)現(xiàn)加法計(jì)算，這里我們編寫了三個(gè)函數(shù)：
補(bǔ)零函數(shù)（add_zero）：為了將兩個(gè)二進(jìn)制數(shù)變成同樣的長度鉴象，通過向較小數(shù)高位補(bǔ)零實(shí)現(xiàn)忙菠；
一位全加器（add_bit）：實(shí)現(xiàn)一位的加法計(jì)算，這個(gè)在數(shù)字電路中是實(shí)現(xiàn)加法計(jì)算的基礎(chǔ)纺弊，它的輸入有三個(gè)，其中兩個(gè)是加數(shù)bit1和bit2（0或1）骡男，另一個(gè)是上一位的進(jìn)位carry淆游，輸出有兩個(gè)，一個(gè)是當(dāng)前位的計(jì)算結(jié)果cur_res，另一個(gè)是當(dāng)前計(jì)算的進(jìn)位（cur_carry）犹菱，狀態(tài)轉(zhuǎn)移矩陣為：
| bit1 | bit2 | carry | cur_res | cur_carry |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
- 一個(gè)4字節(jié)全加器（add_unsigned_nums）：通過組合多個(gè)一位全加器實(shí)現(xiàn)拾稳，實(shí)現(xiàn)兩個(gè)無符號(hào)整數(shù)之和。
class Solution(object):
def getSum(self, a, b):
def add_zero(num1, num2):
"""
兩個(gè)二進(jìn)制字符串中較短的最高位補(bǔ)零腊脱，補(bǔ)到和較長的一樣長度访得。
:param num1:
:param num2:
:return:
"""
if len(num1) > len(num2):
num2 = '0' * (len(num2) - len(num1)) + num2
elif len(num2) > len(num1):
num1 = '0' * (len(num1) - len(num2)) + num1
return num1, num2
def add_bit(bit1, bit2, carry):
"""
模擬數(shù)字電路，我們也來實(shí)現(xiàn)一個(gè)一位的全加器陕凹，這里我們輸入和輸出都是字符串形式悍抑。
:param bit1: 第一個(gè)數(shù)，0或1
:param bit2: 第二個(gè)數(shù)杜耙，0或1
:param carry: 上一步的進(jìn)位
:return: cur_res: 當(dāng)前位的計(jì)算結(jié)果
:return: cur_carry: 進(jìn)位
"""
if bit1 == '0' and bit2 == '0': # 如果輸入兩個(gè)數(shù)均為零
cur_res = carry # 結(jié)果即為上一步進(jìn)位
cur_carry = '0' # 當(dāng)前進(jìn)位是零
elif bit1 == '1' and bit2 == '1': # 如果輸入兩個(gè)數(shù)均為一
cur_res = carry # 結(jié)果還是上一步進(jìn)位
cur_carry = '1' # 當(dāng)前進(jìn)位是一
else: # 如果輸入一個(gè)是一搜骡，另一個(gè)是零
if carry == '0': # 此時(shí)如果上一步進(jìn)位為零
cur_res = '1' # 當(dāng)前結(jié)果是一
cur_carry = '0' # 進(jìn)位是零
else: # 此時(shí)如果上一步進(jìn)位為一
cur_res = '0' # 當(dāng)前結(jié)果為零
cur_carry = '1' # 進(jìn)位為一
return cur_res, cur_carry # 返回計(jì)算結(jié)果和進(jìn)位
def add_unsigned_nums(num1, num2):
"""
相加兩個(gè)無符號(hào)二進(jìn)制整數(shù)（字符串）
:param num1:
:param num2:
:return:
"""
res = ''
carry = '0'
for bit1, bit2 in reversed(list(zip(num1, num2))):
cur_res, carry = add_bit(bit1, bit2, carry) # 計(jì)算當(dāng)前位
res = cur_res + res
if carry == '1': # 如果還有進(jìn)位
res = carry + res # 記得加到最高位
return res # 返回結(jié)果
def add_nums(num1, num2):
num1, num2 = bin(num1)[2:], bin(num2)[2:] # 十進(jìn)制轉(zhuǎn)二進(jìn)制（字符串）
num1, num2 = add_zero(num1, num2) # 短數(shù)補(bǔ)零與長數(shù)對(duì)齊
res = add_unsigned_nums(num1, num2) # 二進(jìn)制求和
return int(res, base=2)
return add_nums(a, b)
有符號(hào)整數(shù)
我們使用類似的方法，實(shí)現(xiàn)有符號(hào)32位整數(shù)的相加佑女，這里需要注意的是记靡，32位有符號(hào)整數(shù)的范圍是-2^31 ~ 2^31-1，負(fù)數(shù)用補(bǔ)碼表示团驱；如果計(jì)算結(jié)果超過整數(shù)范圍摸吠，說明計(jì)算結(jié)果為負(fù)數(shù)，需要進(jìn)行換算嚎花。
下面已經(jīng)為讀者寫好了函數(shù)蜕便，這里我們使用掩碼進(jìn)行當(dāng)前計(jì)算位的選擇，讀者如果希望觀察計(jì)算流程贩幻，可以把打印開關(guān)（print_log）打開轿腺。
def oct2bin(num):
"""
32位有符號(hào)整數(shù)轉(zhuǎn)為對(duì)應(yīng)的二進(jìn)制字符串
:param num:
:return:
"""
mask = 0x01
res = ''
for i in range(32):
cur = '1' if num & mask != 0 else '0'
res = cur + res
mask = mask << 1
return res
class Solution(object):
def getSum(self, num1, num2, print_log=False):
print('當(dāng)前加數(shù)為：{}'.format(oct2bin(num1)))
print('當(dāng)前加數(shù)為：{}'.format(oct2bin(num2)))
ans = 0 # 結(jié)果變量
mask = 0x01 # 這個(gè)掩碼是用來提取指定位的值的
carry = 0 # 進(jìn)位
for i in range(0, 32): # 32位中遍歷
a = num1 & mask # 提取當(dāng)前位
b = num2 & mask # 提取當(dāng)前位
c = carry # 提取上一步進(jìn)位
carry = 0 # 當(dāng)前步進(jìn)位歸零
if a ^ b != 0: # 如果兩個(gè)計(jì)算數(shù)中有一個(gè)為一，另一個(gè)是零
if c == 1: # 上一步進(jìn)位為一
carry = 1 # 則當(dāng)前一定會(huì)產(chǎn)生進(jìn)位丛楚，當(dāng)前位計(jì)算結(jié)果為零族壳，ans不用動(dòng)
else: # 上一步進(jìn)位為零
ans |= mask # 當(dāng)前不產(chǎn)生進(jìn)位，當(dāng)前位計(jì)算結(jié)果為一
else: # 如果兩個(gè)計(jì)算數(shù)中均為一或者均為零
if a & mask > 0: # 研究兩個(gè)計(jì)算數(shù)均為一的情況
carry = 1 # 進(jìn)位肯定是要的
if c == 1: # 如果上一步有一個(gè)進(jìn)位
ans |= mask # 那么當(dāng)前結(jié)果就是一
mask = mask << 1 # 我們把掩碼向左移動(dòng)一位趣些，開始研究更高的一位
if print_log: # 打印記錄
print('\n當(dāng)前遍歷到了從低向高第{}位仿荆。'.format(i))
print('當(dāng)前掩碼為：{}'.format(oct2bin(mask)))
print('當(dāng)前加數(shù)一：{}'.format(oct2bin(a)))
print('當(dāng)前加數(shù)二：{}'.format(oct2bin(b)))
print('當(dāng)前結(jié)果為：{}'.format(oct2bin(ans)))
if ans > 0x7fffffff: # 這種情況說明可能得到了負(fù)數(shù)
return ans - 0xffffffff - 1 # 返回負(fù)數(shù)的計(jì)算結(jié)果
return ans # 返回最終結(jié)果
if __name__ == "__main__":
s = Solution()
print(s.getSum(1, 5, True))
刁鉆技巧
網(wǎng)上流傳一種一句話實(shí)現(xiàn)的遞歸調(diào)用法，供讀者參考坏平。
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
return a if b == 0 else self.getSum(a ^ b, (a & b) << 1)
如有疑問或建議拢操，歡迎評(píng)論區(qū)留言~
