Leetcode 371: Sum of Two Integers

dume0011
1 min readNov 3, 2021

--

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

  • -1000 <= a, b <= 1000

Problem Analysis:

As we can not use operators + and -. we can use ^ operator. If ith bit of a and b is 0 and 0, or 1 and 1, then after the ^ operator, the result is 0, or 1 otherwise. It is similar as + operator, except when both are 1, + operator will have a carry bit.

So we can use ^ operator to imitate + operator, add use & operator to get bits that need to carry bit.

As a and b may be minus, but minus number is inverse bits of its absolute value and plus 1, so we still can use the ^ and & operator to imitate similarly

Solution

class Solution {
public:
int getSum(int a, int b) {
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
};

time complexity is O(1)

Space complexity is O(1)

--

--

No responses yet