題目如下:
寫一個函數(shù),求兩個整數(shù)之和,要求在函數(shù)體內不得使用+、-、*、/四則運算符號。
題目不難,可以采用位操作來實現(xiàn),利用異或運算來計算不帶進位的加法結果,利用與運算計算進位的標志,然后將這兩個結果進行不帶進位相加,重復上述過程,直至進位標志位0.
代碼如下
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2!=0:
tmp = num1^num2
num2 = (num1&num2)<<1
num1 = tmp
return num1
發(fā)現(xiàn)當一個整數(shù)和一個負數(shù)相加時出現(xiàn)了死循環(huán),其實問題出在tmp = num1^num2這條語句中。
實際上,在進行負數(shù)的按位加法時,有可能發(fā)生在最高位還要向前進一位的情形,正常來說,這種進位因為超出了一個int可以表示的最大位數(shù),應該舍去才能得到正確的結果。因此,對于Java,c,c++這樣寫是正確的。而對于Python,卻有點不同。
在早期版本中如Python2.7中,整數(shù)的有int和long兩個類型。int類型是一個固定位數(shù)的數(shù);long則是一個理論上可以存儲無限大數(shù)的數(shù)據類型。當數(shù)大到可能溢出時,為了避免溢出,python會把int轉化為long。而Python3.x之后整數(shù)只有一個可以放任意大數(shù)的int了。可是無論哪種,都是采用了特殊的方法實現(xiàn)了不會溢出的大整數(shù)。 所以會使程序無限的算下去,這也是Python效率低的一個原因。
改正的代碼,可以每次都把num1規(guī)定成一個32位的數(shù)
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2 != 0:
temp = num1 ^ num2
num2 = (num1 & num2) << 1
num1 = temp & 0xFFFFFFFF
return num1 if num1 >> 31 == 0 else num1 - 4294967296
32個1也就是一個int可表示的無符號整數(shù)為4294967295,對應的有符號為-1。因此最后我們可以判斷符號位是否為1做處理。