260. Add Without Plus
You are designing the arithmetic unit of a tiny chip that has no adder: it can only perform bitwise AND, OR, XOR, NOT and shifts on 32-bit two's-complement integers. Teach it to add. Given two signed integers a and b, return their sum a + b without using the + or - operators (nor ++, --, or library sum helpers).
Both inputs may be negative, and the sum is guaranteed to fit in a signed 32-bit integer, so no overflow handling beyond the 32-bit wrap-around of the bit pattern is needed. Your loop must terminate after at most 32 rounds for every valid input, using O(1) extra space.
Hint on the model: half adding two bits gives a sum bit by XOR and a carry bit by AND, shifted one place to the left.
Example 1
- Input:
- a = 38, b = 71
- Output:
- 109
- Explanation:
Adding 38 and 71 gives 109.
Example 2
- Input:
- a = -52, b = 17
- Output:
- -35
- Explanation:
Adding -52 and 17 gives -35.
Example 3
- Input:
- a = -1000000000, b = 999999999
- Output:
- -1
- Explanation:
Adding -1000000000 and 999999999 gives -1.
Constraints
-109 ≤ a, b ≤ 109
The true sum a + b lies in [-231, 231 - 1] (always true for these bounds).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(1)
- Space
- O(1)