#371
Sum of Two Integers
Medium XOR + carry
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Add two integers without using + or -.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add without using + or -.
Why this works: XOR adds bits but forgets carries; AND finds where carries happen, and shifting left moves them into place. Repeat until there's no carry.
Example: a = 5 (101), b = 3 (011)
sum 110, carry 010sum 100, carry 100sum 000, carry 1000sum 1000, carry 0 → 8
✦Hints open one at a time
a ^ b adds bits without carrying.
(a & b) << 1 gives the carries.
Repeat until there's no carry left.
↗Approach
Keep replacing (a, b) with (a ^ b, (a & b) << 1). The carry moves left each round and eventually becomes 0. Java's two's-complement ints make negative numbers work automatically.
</>Solution (Java)
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a = a ^ b; // sum without carry
b = carry; // add the carry next round
}
return a;
}
}!Common mistake
Writing a while loop on b > 0 — the carry can be negative, so loop while b != 0.
Complexity
- Time: O(32) = O(1).
- Space: O(1).
