371. Sum of Two Integers

  • 51.2%

https://leetcode.com/problems/sum-of-two-integers/?tab=Description

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

1
2
Example:
Given a = 1 and b = 2, return 3.

方法一:

通过 a^b 可以知,1 0, 0 1均为1,0 0为0,但是1 1是0,本应该为1,且进一位。所以通过a^b之后,(a&b)<<1 与刚才的 a^b形成两个数,和都等于这两个新数字的和。

我的代码实现:

Oct 16, 2017

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int getSum(int a, int b) {
int sum = a;
while(b){
sum = a^b;
b = (a&b)<<1;
a = sum;
}
return sum;
}
};

https://discuss.leetcode.com/topic/49829/share-my-c-solutions-easy-to-understand

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int getSum(int a, int b) {
int sum = a;
while(b){
sum = a^b;
b = (a&b) << 1;
a = sum;
}
return sum;
}
};

java


https://discuss.leetcode.com/topic/49764/0ms-ac-java-solution

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int getSum(int a, int b) {
if(b==0) return a;
int sum, carry;
sum = a^b;
carry = (a&b)<<1;
return getSum(sum, carry);
}
};

https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Iterative
public int getSum(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;

while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}

return a;
}

// Iterative
public int getSubtract(int a, int b) {
while (b != 0) {
int borrow = (~a) & b;
a = a ^ b;
b = borrow << 1;
}

return a;
}

// Recursive
public int getSum(int a, int b) {
return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

// Get negative number
public int negate(int x) {
return ~x + 1;
}
谢谢你,可爱的朋友。