# LeetCode 371: Sum of Two Integers

## Problem Restatement

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

The problem is asking us to implement integer addition using bit operations. The official statement gives examples such as `a = 1, b = 2`, with output `3`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `a` and `b` |
| Output | The integer sum of `a` and `b` |
| Restriction | Do not use `+` or `-` |
| Main tool | Bitwise operations |

Example function shape:

```python
def getSum(a: int, b: int) -> int:
    ...
```

## Examples

Example 1:

```python
a = 1
b = 2
```

The answer is:

```python
3
```

Example 2:

```python
a = 2
b = 3
```

Binary form:

```text
2 = 010
3 = 011
```

Adding them gives:

```text
5 = 101
```

So the answer is:

```python
5
```

Example 3:

```python
a = 2
b = -5
```

The answer is:

```python
-3
```

Negative numbers need extra care in Python because Python integers do not have a fixed bit width.

## First Thought: Use Normal Addition

Normally we would write:

```python
return a + b
```

But the problem forbids `+` and `-`.

So we need to reproduce addition at the bit level.

## Key Insight

Binary addition has two parts:

| Operation | Meaning |
|---|---|
| `a ^ b` | Sum without carry |
| `(a & b) << 1` | Carry shifted to the next bit |

For one bit:

| `a` | `b` | Sum bit | Carry |
|---:|---:|---:|---:|
| `0` | `0` | `0` | `0` |
| `0` | `1` | `1` | `0` |
| `1` | `0` | `1` | `0` |
| `1` | `1` | `0` | `1` |

The sum bit matches XOR.

The carry appears only when both bits are `1`, which matches AND. Then the carry moves one bit left.

So we repeatedly do:

```python
sum_without_carry = a ^ b
carry = (a & b) << 1
```

Then add those two parts again using the same process.

Stop when there is no carry.

## Why Python Needs a Mask

In many languages, integers have fixed width, such as 32 bits.

Python integers can grow without limit.

That causes trouble for negative numbers because their sign extension conceptually continues forever.

So we simulate 32-bit signed integer arithmetic with:

```python
MASK = 0xFFFFFFFF
MAX_INT = 0x7FFFFFFF
```

After each step, we keep only the lower 32 bits:

```python
& MASK
```

At the end:

| Condition | Meaning |
|---|---|
| `a <= MAX_INT` | Normal positive result |
| `a > MAX_INT` | Negative result in 32-bit two's complement |

To convert a 32-bit negative value back into Python's negative integer form, use:

```python
~(a ^ MASK)
```

## Algorithm

1. Set:

```python
MASK = 0xFFFFFFFF
MAX_INT = 0x7FFFFFFF
```

2. While `b` is not zero:
   - Compute carry:

```python
carry = (a & b) << 1
```

   - Compute sum without carry:

```python
a = a ^ b
```

   - Apply the mask to keep 32 bits.
   - Set `b` to the carry.

3. Convert the result back to Python signed integer form.
4. Return it.

## Correctness

At each step, `a ^ b` computes the bitwise sum without carry.

The expression `(a & b) << 1` computes every carry bit and moves it to the position where it must be added next.

Therefore, replacing `(a, b)` with:

```python
(a ^ b, (a & b) << 1)
```

preserves the total mathematical value of `a + b`.

Each iteration moves carries left. Under the 32-bit mask, the process must terminate because there are only 32 bit positions. When `b` becomes zero, no carries remain, and `a` contains the final 32-bit sum.

The final conversion interprets the 32-bit result as a signed integer. Therefore, the algorithm returns the same value as normal integer addition under the problem constraints.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | At most 32 carry propagation steps |
| Space | `O(1)` | Only a few integer variables |

## Implementation

```python
class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        max_int = 0x7FFFFFFF

        while b != 0:
            carry = ((a & b) << 1) & mask
            a = (a ^ b) & mask
            b = carry

        if a <= max_int:
            return a

        return ~(a ^ mask)
```

## Code Explanation

The mask keeps numbers inside 32 bits:

```python
mask = 0xFFFFFFFF
```

The largest positive signed 32-bit integer is:

```python
max_int = 0x7FFFFFFF
```

Inside the loop, compute carry first:

```python
carry = ((a & b) << 1) & mask
```

Then compute sum without carry:

```python
a = (a ^ b) & mask
```

Then continue adding the carry:

```python
b = carry
```

When the loop ends, `a` is the 32-bit result.

If it fits in the positive signed range, return it directly:

```python
if a <= max_int:
    return a
```

Otherwise, convert from 32-bit two's complement to Python negative integer:

```python
return ~(a ^ mask)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.getSum(1, 2) == 3
    assert s.getSum(2, 3) == 5
    assert s.getSum(-1, 1) == 0
    assert s.getSum(2, -5) == -3
    assert s.getSum(-4, -6) == -10
    assert s.getSum(0, 0) == 0
    assert s.getSum(1000, -1000) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(1, 2)` | Basic positive addition |
| `(2, 3)` | Carry occurs |
| `(-1, 1)` | Negative plus positive gives zero |
| `(2, -5)` | Negative result |
| `(-4, -6)` | Two negative numbers |
| `(0, 0)` | Zero case |
| `(1000, -1000)` | Opposite values cancel |