371. Sum of Two Integers

Posted on Edited on In

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:

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

Example 2:

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

Constraints:

  • -1000 <= a, b <= 1000

Hints/Notes

  • 2025/01/07
  • bit manipulation
  • No solution from 0x3F

Solution

Language: C++

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
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int getSum(int a, int b) {
        if (abs(a) < abs(b)) {
            return getSum(b, a);
        }
        int res = 0;
        if (a * b < 0) {
            // the problem becomes a - b
            int borrow = 0, x = abs(a), y = abs(b), index = 0;
            while (x) {
                int bitX = x % 2;
                int bitY = y % 2;
                int bit = bitX ^ bitY ^ borrow;
                res |= bit << index++;
                if ((bitX < bitY) || (bitX == bitY && borrow)) {
                    borrow = 1;
                } else {
                    borrow = 0;
                }
                x >>= 1;
                y >>= 1;
            }
            if (a < 0) {
                res *= -1;
            }
        } else {
            // the problem becomes a + b
            int carry = 0, x = abs(a), y = abs(b), index = 0;
            while (x || carry) {
                int bitX = x % 2;
                int bitY = y % 2;
                int bit = bitX ^ bitY ^ carry;
                res |= bit << index++;
                if ((bitX && bitY) || (bitX && carry) || (bitY && carry)) {
                    carry = 1;
                } else {
                    carry = 0;
                }
                x >>= 1;
                y >>= 1;
            }
            if (a < 0) {
                res *= -1;
            }
        }
        return res;

    }
};