Sum of Two Integers

• Difficulty: Medium
• Topics: Math, Bit Manipulation
• Link: https://leetcode.com/problems/sum-of-two-integers/

Problem Description

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

Example 1:

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

Example 2:

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

Constraints:

• -1000 <= a, b <= 1000

Solution

1. Problem Deconstruction

Technical Restatement
Design an algorithm to compute the sum of two integers a and b using bitwise operations exclusively, without utilizing arithmetic operators (+, -).

Beginner’s Description
Imagine you have two numbers, and you need to add them together. But you’re not allowed to use the usual plus or minus signs. Think of how binary numbers work: each bit can be added with a possible carry. This problem is about simulating that process using operations like XOR and AND.

Mathematical Formulation
Let sum = a + b. Using bitwise operations:

• sum_without_carry = a XOR b
• carry = (a AND b) << 1
  Repeat until carry = 0:
• sum = sum_without_carry + carry
  But since + is forbidden, iteratively update a and b with the new values.

Constraint Analysis

• Range -1000 to 1000: Small enough for bitwise operations in Python’s arbitrary-precision integers.
• Hidden Edge Cases: Negative numbers require careful handling of two’s complement.

2. Intuition Scaffolding

Real-World Metaphor
Like merging two streams of water, where XOR combines them without spillage, and AND calculates the overflow to carry over.

Gaming Analogy
In a game where you collect items in a grid, XOR picks up items not in both slots, and AND finds overlaps to carry to the next level.

Math Analogy
Solving a system where each bit is an equation: bit_sum = (a_i + b_i + carry_in) mod 2, and carry_out = (a_i + b_i + carry_in) // 2.

Common Pitfalls

1. Ignoring Negative Numbers: Assuming two’s complement works magically without masking.
2. Infinite Loops: Not handling Python’s arbitrary-precision leading to non-terminating carry.
3. Global Min/Max Fixation: Trying to track individual bits instead of iterative carry.

3. Approach Encyclopedia

Optimal Approach
Concept: Use XOR for sum without carry, AND + shift for carry. Mask to 32 bits for termination.
Steps:

1. Compute sum_without_carry = a ^ b.
2. Compute carry = (a & b) << 1.
3. Mask both to 32 bits to prevent infinite loops.
4. Repeat until carry = 0.
5. Adjust for negative results via two’s complement.

Pseudocode:

def getSum(a, b):  
    mask = 0xFFFFFFFF  
    max_int = 0x7FFFFFFF  
    while b != 0:  
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask  
    return a if a <= max_int else ~(a ^ mask)  

Complexity Proof

• Time: O(1) iterations (max 32 for 32-bit), each step O(1) bitwise operations.
• Space: O(1) variables.

Visualization

a = 1 (0001), b = 2 (0010)  
Iteration 1:  
sum = 0011 (3), carry = 0000 → done.  

a = -2 (1110), b = 3 (0011)  
Iteration 1: sum = 1101 (-3), carry = 0100 (4)  
... After 32 iterations, sum = 0001 (1), carry = 0000.  

4. Code Deep Dive

Line-by-Line Annotations

def getSum(a, b):  
    mask = 0xFFFFFFFF  # Restrict to 32-bit  
    max_int = 0x7FFFFFFF  # Max positive 32-bit int  
    while b != 0:  
        # Compute sum without carry and restrict to 32 bits  
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask  
    # Handle negative numbers (two's complement conversion)  
    return a if a <= max_int else ~(a ^ mask)  

Edge Case Handling

• Example 1: a=1, b=2 → Direct XOR gives 3, no carry.
• Example 2: a=2, b=3 → XOR 01, carry 100 → sum 5.

5. Complexity War Room

Hardware-Aware Analysis

• 32-bit operations fit in CPU registers, ensuring O(1) memory and cache efficiency.

Industry Comparison

Approach	Time	Space	Readability	Interview Viability
Bitwise	O(1)	O(1)	7/10	✅ Optimal

6. Pro Mode Extras

Variants

• LC 371: Same problem.
• LC 29: Divide without /, *, %.

Interview Cheat Sheet

• Always mention masking for Python’s infinite-precision.
• Test negative cases explicitly.