Sum of Two Integers

Problem Statement

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

Examples

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Example 3:

Input: a = 5, b = 7
Output: 12

Constraints

• -1000 <= a, b <= 1000

Solution Approach

This is a classic bit manipulation problem that simulates binary addition.

Key Insight

How do we add in binary?

  0101  (5)
+ 0111  (7)
------
  1100  (12)

For each bit position:

• 0 + 0 = 0, no carry
• 0 + 1 = 1, no carry
• 1 + 0 = 1, no carry
• 1 + 1 = 0, carry 1

Observation:

• XOR (^) gives us the sum without carry
• AND (&) finds positions where carry occurs
• Left shift ({'<'}{'<'} 1) moves carry to the next position

Algorithm

while (b != 0) {
    sum = a ^ b      // XOR gives sum without carry
    carry = (a & b) << 1   // AND finds carry, shift left
    a = sum
    b = carry
}
return a

Why this works?

• We keep adding the carry until there's no carry left
• Eventually, b (carry) becomes 0

Detailed Example: 5 + 7

Iteration 1:
a = 5 = 0101
b = 7 = 0111

XOR: 0101 ^ 0111 = 0010 (2) - sum without carry
AND: 0101 & 0111 = 0101 (5) - positions with carry
Carry: 0101 << 1 = 1010 (10) - shift carry left

Now: a = 2, b = 10

Iteration 2:
a = 2 = 0010
b = 10 = 1010

XOR: 0010 ^ 1010 = 1000 (8)
AND: 0010 & 1010 = 0010 (2)
Carry: 0010 << 1 = 0100 (4)

Now: a = 8, b = 4

Iteration 3:
a = 8 = 1000
b = 4 = 0100

XOR: 1000 ^ 0100 = 1100 (12)
AND: 1000 & 0100 = 0000 (0)
Carry: 0000 << 1 = 0000 (0)

Now: a = 12, b = 0

Since b = 0, return a = 12 ✓

Why XOR for Sum?

XOR truth table matches addition without carry:

a  b  | a^b | a+b (mod 2)
0  0  |  0  |  0
0  1  |  1  |  1
1  0  |  1  |  1
1  1  |  0  |  0  (carry happens)

Why AND for Carry?

AND finds where both bits are 1 (carry occurs):

a  b  | a&b | carry?
0  0  |  0  | No
0  1  |  0  | No
1  0  |  0  | No
1  1  |  1  | Yes!

Time & Space Complexity

• Time Complexity: O(1)

  • At most 32 iterations (for 32-bit integers)
  • Fixed number of iterations regardless of input values

• Space Complexity: O(1)

  • Only using a few variables

Java Solution

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int sum = a ^ b;        // XOR for sum without carry
            int carry = (a & b) << 1;  // AND and shift for carry
            a = sum;
            b = carry;
        }
        return a;
    }
}

Python Solution

def getSum(a: int, b: int) -> int:
    # Python requires masking for negative numbers
    # 32-bit signed integer range
    MAX = 0x7FFFFFFF  # 2^31 - 1
    MASK = 0xFFFFFFFF  # 2^32 - 1

    while b != 0:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK

    # Handle negative result
    return a if a <= MAX else ~(a ^ MASK)

Note: Python has arbitrary precision integers, so we need masks to simulate 32-bit behavior.

Recursive Solution

class Solution {
    public int getSum(int a, int b) {
        if (b == 0) return a;

        int sum = a ^ b;
        int carry = (a & b) << 1;

        return getSum(sum, carry);
    }
}

Handling Negative Numbers

In Java/C++, negative numbers are represented in two's complement:

• The algorithm works naturally for negative numbers!
• No special handling needed

Example: (-1) + 1 = 0

a = -1 = 11111111 (in 8-bit)
b =  1 = 00000001

XOR: 11111111 ^ 00000001 = 11111110
AND: 11111111 & 00000001 = 00000001
Carry: 00000001 << 1 = 00000010

a = 11111110, b = 00000010

... (continues until b = 0)

Result: 00000000 = 0 ✓

Bitwise Operator Review

| Operator | Name | Description | Example | |----------|------|-------------|---------| | ^ | XOR | 1 if bits differ | 5 ^ 3 = 6 (101 ^ 011 = 110) | | & | AND | 1 if both bits are 1 | 5 & 3 = 1 (101 & 011 = 001) | | {'<'}{'<'} | Left Shift | Shift bits left, multiply by 2 | 5 {'<'}{'<'} 1 = 10 (101 << 1 = 1010) | | {'>'}{'>'}{' '} | Right Shift | Shift bits right, divide by 2 | 5 {'>'}{'>'}{' '} 1 = 2 (101 >> 1 = 10) | | ~ | NOT | Flip all bits | ~5 = -6 (in two's complement) |

Related Problems

• Subtract Two Numbers (variation): Use a + (~b + 1) (two's complement)
• Add Binary (LeetCode 67): String addition
• Add Strings (LeetCode 415): String addition with carry
• Plus One (LeetCode 66): Increment by 1
• Missing Number (LeetCode 268): XOR trick

Pattern Recognition

This problem demonstrates:

• Bit manipulation fundamentals
• Simulation of arithmetic operations
• Iterative carry propagation
• Binary addition logic

Common Mistakes

1. ❌ Forgetting to shift carry left
2. ❌ Using | instead of ^ for sum
3. ❌ Not handling the loop condition (while b != 0)
4. ❌ In Python, not masking for 32-bit integers
5. ❌ Confusing AND with OR for carry detection
6. ❌ Trying to use + or - operators (violates constraint!)

Tips for Interviews

• Draw binary: Show small example like 5 + 7 in binary
• Explain operators: Clearly explain XOR for sum, AND for carry
• Walk through: Step-by-step simulation for one example
• Mention carry: Emphasize why we need left shift
• Handle negatives: Mention two's complement works naturally
• Complexity: O(1) time due to fixed 32 iterations max
• Follow-up: Be ready to discuss subtraction (a + (-b))

Follow-Up Questions

1. Q: How would you subtract a - b?

   • A: Compute a + (-b) where -b is two's complement: ~b + 1
   • Code: getSum(a, getSum(~b, 1))

2. Q: What about multiplication?

   • A: Use repeated addition or bit shifts (Russian peasant multiplication)

3. Q: Why does left shift equal multiply by 2?

   • A: Shifting left by 1 adds a zero to the right, doubling the value

4. Q: How many iterations in worst case?

   • A: At most 32 (or 64 for long) - the bit width of integers

Alternative: Recursive One-Liner

return b == 0 ? a : getSum(a ^ b, (a & b) << 1);

Why This Problem?

Tests understanding of:

• Bitwise operations (XOR, AND, shift)
• Binary representation of numbers
• How addition works at bit level
• Two's complement for negative numbers
• Algorithmic thinking without standard operators

This is a fundamental problem that appears in hardware design and low-level programming!

Bit Operation Patterns

This problem uses several bit manipulation patterns:

1. XOR for differences: a ^ b finds bits that differ
2. AND for commonality: a & b finds bits that match
3. Left shift for scaling: Multiply by 2
4. Carry propagation: Keep adding until no carry

These patterns appear in many bit manipulation problems!

Real-World Applications

• ALU (Arithmetic Logic Unit) in CPUs uses this exact logic
• Hardware adders implement this at gate level
• Binary calculators simulate arithmetic
• Embedded systems with limited instruction sets

Understanding this helps you understand how computers actually add numbers!