题目如下:
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
题目不难,可以采用位操作来实现,利用异或运算来计算不带进位的加法结果,利用与运算计算进位的标志,然后将这两个结果进行不带进位相加,重复上述过程,直至进位标志位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
发现当一个整数和一个负数相加时出现了死循环,其实问题出在tmp = num1^num2这条语句中。
实际上,在进行负数的按位加法时,有可能发生在最高位还要向前进一位的情形,正常来说,这种进位因为超出了一个int可以表示的最大位数,应该舍去才能得到正确的结果。因此,对于Java,c,c++这样写是正确的。而对于Python,却有点不同。
在早期版本中如Python2.7中,整数的有int和long两个类型。int类型是一个固定位数的数;long则是一个理论上可以存储无限大数的数据类型。当数大到可能溢出时,为了避免溢出,python会把int转化为long。而Python3.x之后整数只有一个可以放任意大数的int了。可是无论哪种,都是采用了特殊的方法实现了不会溢出的大整数。 所以会使程序无限的算下去,这也是Python效率低的一个原因。
改正的代码,可以每次都把num1规定成一个32位的数
# -*- 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可表示的无符号整数为4294967295,对应的有符号为-1。因此最后我们可以判断符号位是否为1做处理。