Sum of Two Integers

Share

Given two integers a and b, return the sum of the two integers without using the operators + or -.

Example 1
Input: a = 1, b = 2
Output: 3
Explanation: 1 + 2 = 3, computed using XOR and carry.
Example 2
Input: a = 2, b = 3
Output: 5
Explanation: 2 (010) XOR 3 (011) = 001, carry = 100; 001 XOR 100 = 101 = 5.

Solution Approach

Binary addition works in two steps: XOR gives the sum without carry, and (a & b) << 1 gives the carry. Repeat until there is no carry.

  • XOR a and b to get the sum without carry.
  • AND a and b then shift left to get the carry.
  • Set a = sum, b = carry and repeat until carry is 0.
  • Return a when b becomes 0.
Java
class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}
Complexity Analysis:

Time complexity: O(1). Bounded by 32 bit positions.
Space complexity: O(1). Constant extra space.