LeetCode 371. Sum of Two Integers(两个数之和)
题目描述
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
解法一
思路
看到这题就想到学计算机组成原理时讲的加法器了。
看看51
和85
以二进制的形式相加:
00110011
+ 01010101
----------
10001000
注意看,由于二进制仅有0
和1
,那么出现进位的情况只能是1
和1
相加,并且进位其实相当于在其前一位加1
,那么进位产生的1
就可以表示为按位与的结果再往左移位一位,即
00110011
& 01010101
----------
00010001
<<
----------
00100010
那么不考虑进位的相加结果是什么了,其实就是按位异或了,即
00110011
^ 01010101
----------
01100110
来看看“按位与,移位”和“按位异或”相加的结果:
00100010
+ 01100110
----------
10001000
怎么样?就是最终的答案了。所以只需要重复这个按位与和按位异或的过程,直到按位与的值为0(不产生进位),那么就得到最终结果了。来模拟一下
00110011
01010101
----------
& -> 00010001 << 1 -> 00100010
^ -> 01100110
00100010
01100110
----------
& -> 00100010 << 1 -> 01000100
^ -> 01000100
01000100
01000100
----------
& -> 01000100 << 1 -> 10001000
^ -> 00000000
10001000
00000000
----------
& -> 00000000
^ -> 10001000
output: 10001000
Python
class Solution:
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
mask = 0xffffffff
sum = (a ^ b) & mask
part = a & b
while part:
a = sum
b = (part << 1) & mask
sum = (a ^ b) & mask
part = a & b
if sum & 0x80000000:
sum -= 0x100000000
return sum
Java
public class Solution {
public int getSum(int a, int b) {
int sum = a ^ b;
int part = a & b;
while (part != 0) {
int theA = sum;
int theB = part << 1;
sum = theA ^ theB;
part = theA & theB;
}
return sum;
}
}
C++
class Solution {
public:
int getSum(int a, int b) {
int sum = a ^ b;
int part = a & b;
while (part) {
int theA = sum;
int theB = part << 1;
sum = theA ^ theB;
part = theA & theB;
}
return sum;
}
};
能不能解释一下Python用的那些mask都是什么意思啊?还有最后的0x80000000和0x100000000
这个是因为这个题目假定的int是32位的,但Python的整型并没有这个限制,为了模拟出这个效果就得用固定的特殊二进制数(如0xffffffff,0x100000000)来防止“溢出”32位。你可以模拟溢出32位就知道这些多余的东西是干啥的啦~
python解法用了减法,不合格,目前还没见到合格的python解
其实严格来说Python版不需要最后减的那一步,只是为了满足OJ默认最大值为32位的特殊条件