0%

leetcode Sum of Two Integers

leetcode 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.

传送门:leetcode Sum of Two Integers

题意:给定两个数 a和b,求它们的和。 要求不使用 +和-运算符

思路:

首先要知道,异或也被称为“模2和” ,so 这题就是运用异或的位运算啦。

我们可以每次取最低位来计算, 然后每次右移一位,注意点有:

  • 进位为两个数字1
  • 负数的情况下,右移最高位补的是1 ,因此值得注意要取到什么时候为止。 java有一个无符号右移>>>高位补0,因此结束条件可以为a!=0 b!=0(然而进位会被忽略)

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int getSum(int a, int b) {
int ans = 0, carry = 0;
for (int i = 0; i < 32; a >>= 1, b >>= 1, i++) {
int lower_a = a & 1, lower_b = b & 1;
ans |= (lower_a ^ lower_b ^ carry) << i;
carry = (carry & lower_a) | (carry & lower_b) | (lower_a & lower_b);
}
return ans;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int getSum(int a, int b) {
int ans = 0, carry = 0;
for (int i = 0; i < 32; a >>>= 1, b >>>= 1, i++) {
int lower_a = a & 1, lower_b = b & 1;
ans = (lower_a ^ lower_b ^ carry) << i;
carry = (carry & lower_a) (carry & lower_b) (lower_a & lower_b);
}
return ans;
}
}

 

第二种方法是直接进行异或操作。

a ^ b 直接算出a + b 每位上%2的结果, 进位的话可以直接 (a & b)<<1得到(只有两个位均为1才会进位嘛,左移表示进到下一位啊)

C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int c = a & b; //carry
a ^= b; //add
b = c << 1;
}
return a;
}
};

Java(和上面一样)

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int c = a & b; //carry
a ^= b; //add
b = c << 1;
}
return a;
}
}

也可以写成Oneline:

1
2
3
4
5
6
class Solution {
public:
int getSum(int a, int b) {
return b == 0 ? a : getSum(a^b, (a&b) << 1);
}
};

 

PS:

Python 表示一个数不止32位。。

Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011". 来自 https://wiki.python.org/moin/BitwiseOperators

因此。。做这题要保证两个数在正确的范围内(本题是int,32bit)

如何做到呢?我们知道32bit 可以表示的无符号整数位00xFFFFFFFF(全0全1)

因此,我们使用&来保证该数是32bit.

int的0和正整数范围为00x7FFFFFFF,int负数的范围为-0x80000000-1,因此,大于0x7FFFFFFF的其实是最高位为1(这是符号位)。这样算出来是把最高位不当成符号位,我们还需要对负数的情况进行修正。

在具体实现上,我们可以先 &0x7FFFFFFF 然后取反,这样,-1变为-0x80000000(-2147483648) -2变为了-0x7FFFFFFF(-2147483647) ,因此,在^0x7FFFFFFF即可。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
MOD = 0xFFFFFFFF
MAX_INT = 0x7FFFFFFF
while b != 0:
a, b = (a ^ b) & MOD, ((a & b) << 1) & MOD
return a if a <= MAX_INT else ~(a & MAX_INT) ^ MAX_INT

也可以看https://discuss.leetcode.com/topic/49900/python-solution/2 上的思路

或者更巧妙的用(~0 << 31) a 即可,因为只需要把31位之后的全部置1, 感谢mach7提出

本题是leetcode 371 Sum of Two Integers 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~