Sum of Two Integers
Medium · Bit Manipulation · Math · Bit Manipulation
Problem
Given two integers a and b, return their sum without using the operators + or -.
Treat the numbers as 32-bit signed integers, the way a processor's adder does. LeetCode keeps both inputs between -1000 and 1000; the stress tests here go out to the edges of the 32-bit range, always with a sum that still fits.
Python makes this harder than it looks. Its integers have no fixed width, so a negative number behaves as if it had infinitely many leading 1 bits, and the textbook loop never stops unless you hold every step to 32 bits yourself.
Examples
Input: a = 1, b = 2 Output: 3
01 XOR 10 is 11, and there are no carries.
Input: a = 2, b = 3 Output: 5
010 XOR 011 = 001; the carry (010 AND 011) << 1 = 100; 001 XOR 100 = 101.
Input: a = -1, b = 1 Output: 0
In 32 bits, -1 is all ones. The carry ripples out past bit 31 and is dropped.
Constraints
- -1000 <= a, b <= 1000 on LeetCode
- here, -2^31 <= a, b <= 2^31 - 1 and a + b fits in 32 bits
- no + or - on the numbers (a counter in a loop is fine)
Approaches
- The same step, as recursion — time O(1): at most 32 calls, space O(1): at most 32 frames
Follow-up
How would you subtract, multiply or divide with the same restriction? Subtraction follows from -b == ~b + 1; multiplication is shift-and-add.
Related problems
Start free on Cariara · Coding problems · System design studio
