Sum of Two Integers — Blind 75 practice

Problem

Return a + b without ever using + or - on the way there.
Both inputs are 32-bit signed integers and may be negative; the answer fits in 32 bits too.

Examples

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

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

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

Example 4:
Input: a = -1, b = -1
Output: -2

Constraints

-1000 <= a, b <= 1000

Prerequisites

Binary and two's complement — how a negative number is stored, and what a shift does at the edges.
The trick worth memorising: n & (n-1) clears the lowest set bit.

How to think about it

1. XOR Is the Sum, AND Is the Carry Optimal

Intuition

Addition without carrying IS exclusive-or; the carries are exactly the positions where both bits were set, shifted one place left. Apply both repeatedly and the carry runs out. In Java the int wraps for free; in Python the unbounded integers need a 32-bit mask every round, or a negative operand makes the carry climb forever — that non-termination is the actual lesson of writing it there.

Algorithm

1. Sum without carry: a XOR b.
2. Carry: (a AND b) shifted left one.
3. Repeat with those two until the carry is zero.
4. In Python, mask to 32 bits each round and convert the result to its signed reading.

Time & Space

Time O(32). Space O(1).