Sum of two integers

XXX. Sum of Two Integers (No + Operator)

Bit Manipulation

Recursion

Problem Statement:

Calculate the sum of two integers without using the + or - operators.

• Cannot use arithmetic operators +/-
• Must handle both positive and negative numbers
• Use bit manipulation for addition

Algorithm:

1. **XOR Operation**:
   • XOR (^) gives sum without considering carry
   • Simulates addition without carry-over
2. **Carry Operation**:
   • AND (&) identifies positions where carry occurs
   • Left shift (<<1) moves carry to next position

Implementation:

public int getSum(int a, int b) {
    if (b == 0)                      // No carry left
        return a;
    
    int sum = a ^ b;                 // Add without carrying
    int carry = (a & b) << 1;        // Compute carry bits
    
    return getSum(sum, carry);       // Recursive call with new values
}

Complexity:

Time Complexity: O(log n), where n is max number of bits in input
Space Complexity: O(log n) due to recursion stack

Example Walkthrough:

Adding 2 (10) and 3 (11):

• First iteration:
  • XOR: 10 ^ 11 = 01 (1)
  • Carry: (10 & 11) << 1 = 10 << 1 = 100 (4)
• Second iteration:
  • XOR: 001 ^ 100 = 101 (5)
  • Carry: (001 & 100) << 1 = 000 (0)
• Result: 5

Key Points:

• **Binary Addition Process**:
  • XOR simulates addition without carry
  • AND with shift handles carry propagation
  • Process repeats until no carry remains
• **Base Case**:
  • When carry becomes 0
  • Sum without carry is final result