Math & Bit Manipulation · LC #371
Sum of Two Integers
Add two integers without using `+` or `-` by simulating a binary full adder: XOR for sum-without-carry, AND+shift for carry, repeat until carry is zero.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Calculate the sum of two integers `a` and `b` without using the operators `+` or `-`.
Sample I/O
Input: a=1, b=2 Output: 3 Input: a=2, b=3 Output: 5
Intuition
How to Think About It
Intuition
A single-bit full adder computes sum = A XOR B, carry = A AND B. For multi-bit integers, XOR gives the sum ignoring carries, while AND then left-shift by 1 produces the carries that propagate to the next bit position. Iterating until carry is zero completes the addition.
Core Concept
`while b != 0: carry = (a & b) << 1; a = a ^ b; b = carry; return a`. This directly mirrors a ripple-carry adder in hardware. Python requires a 32-bit mask (`0xFFFFFFFF`) to prevent infinite loops because Python integers have arbitrary precision (no natural 32-bit overflow).
When to use
Understanding binary arithmetic fundamentals; hardware/embedded contexts where operator overloading is restricted; demonstrating knowledge of adder circuits in interviews.
When NOT to use
Any real production code - `a + b` is clearer, faster (native instruction), and correct for all types.
Key Insights
What to Know Cold
- XOR is addition without carry: `1 XOR 1 = 0` (carry discarded), `1 XOR 0 = 1`, `0 XOR 0 = 0`.
- AND+shift is carry generation: `1 AND 1 = 1`, shifted left to the next bit position.
- The while loop terminates because carries cannot propagate beyond 32 bit positions.
- Python gotcha: Python integers never overflow; the carry loop may not terminate without a 32-bit mask. Apply `MASK = 0xFFFFFFFF` to both operands.
- Negative number handling: in Python, after masking to 32 bits, check if result > 0x7FFFFFFF and if so return `~(result ^ MASK)` to convert back to Python's signed representation.
1 example
Worked Examples
Trace a=1, b=3 (binary 01 + 11)
a=1 (01), b=3 (11)
iter1: carry=(01&11)<<1=10, a=01^11=10, b=10. iter2: carry=(10&10)<<1=100, a=10^10=00, b=100. iter3: carry=0, a=00^100=100=4, b=0. Return 4.
getSum(1, 3); // 4 // Round 1: carry=2, a=2, b=2 // Round 2: carry=4, a=0, b=4 // Round 3: carry=0, a=4, b=0 → return 4
Visualises carry propagation across 3 iterations - directly maps to ripple-carry adder.