Sum of Two Integers – Solution & Complexity

• Compute a + b without using the + or - operators — you're only allowed bitwise operations.
• This is fundamentally about how binary addition works at the hardware level: each bit position produces a sum bit and a carry bit, and the carry ripples into the next position.
• a XOR b gives the sum of each bit ignoring carries; a AND b (shifted left by 1) gives exactly the carries that need to be added in.

• a ^ b computes each bit's sum as if there were no carry (since 1^1=0, 0^0=0, 1^0=1 — matches binary addition without carry-out).
• (a & b) << 1 computes the carry that must be added into the next higher bit position (a carry is produced exactly where both bits are 1, and it affects the next bit up).
• Repeat: keep adding the running sum and the new carry the same way, until there's no carry left. This is the classic "add via repeated XOR/AND" bit trick, equivalent to how a full-adder circuit ripples carries.

• Loop: carry = (a & b) << 1, a = a ^ b, b = carry, until b == 0. At that point a holds the final sum.
• In languages without arbitrary-precision integers (Java/Go/Rust), this must be done with fixed-width (32-bit) arithmetic so negative numbers and overflow wrap around exactly like two's-complement hardware addition — Python needs an explicit mask + sign-fix step since its integers are unbounded.

O(1) time in practice — bounded by the fixed bit width (32 iterations max) — and O(1) space.

• In Python, forgetting the 32-bit mask/sign-fix step: since Python ints are unbounded, the naive while b: a, b = a ^ b, (a & b) << 1 loop never terminates correctly for negative inputs without explicit masking.
• In JS, forgetting that << and ^ already operate on 32-bit signed integers, so no extra masking is needed there (unlike Python) — but using them on values outside the 32-bit range gives wrong results.
• Follow-ups: how would you implement subtraction the same way (hint: a - b == a + (~b + 1), i.e. add the two's-complement negation)? How would this generalize to 64-bit integers?