Skip to content

371. Sum of Two Integers

Description

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

Solutions

Solution 1

Thinking

Add without +/-. Bitwise: the sum without carry is XOR, the carry is AND shifted left. Repeat until the carry vanishes.

Python ints are unbounded, so mask with \(0xFFFFFFFF\) to \(32\) bits. If the sign bit is set, convert two’s complement back to a negative.

1
2
3
4
5
6
7
class Solution:
    def getSum(self, a: int, b: int) -> int:
        a, b = a & 0xFFFFFFFF, b & 0xFFFFFFFF
        while b:
            carry = ((a & b) << 1) & 0xFFFFFFFF
            a, b = a ^ b, carry
        return a if a < 0x80000000 else ~(a ^ 0xFFFFFFFF)

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

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

1
2
3
4
5
6
7
8
func getSum(a int, b int) int {
    for b != 0 {
        s := a ^ b
        b = (a & b) << 1
        a = s
    }
    return a
}

Comments