> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/bit-manipulation/371.-sum-of-two-integers.md).

# 371. Sum of Two Integers

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

**Example 1:**

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

**Example 2:**

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

{% hint style="info" %}
每個carry的部分要強制讓第一個bit不為1，這樣才能left shift。
{% endhint %}

```cpp
// Iteration
int getSum(int a, int b) { // time: O(1); space: O(1)
    while (b) {
        int carry = ((a & b) & 0x7fffffff) << 1;
        a = a ^ b; // the first bit cannot be 1; otherwise, it cannot be left-shifted
        b = carry;
    }
    return a;
}
```

```cpp
// Recursion
int getSum(int a, int b) { // time: O(1); space: O(1)
    return b == 0 ? a : getSum(a ^ b, ((a & b) & 0x7fffffff) << 1);
}
```