Domain 2MediumCORE

Sum of Two Integers

We are given two integers a and b. The goal is to compute their arithmetic sum. However, there is a strict constraint: we cannot use the addition (+) or subtraction (-) operators directly in our implementation logic. We must rely on bitwise operations instead.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Bit Manipulation

371. Sum of Two Integers

Model: qwen3.5:9b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 50.6%


Problem Breakdown

We are given two integers a and b. The goal is to compute their arithmetic sum. However, there is a strict constraint: we cannot use the addition (+) or subtraction (-) operators directly in our implementation logic. We must rely on bitwise operations instead.

Inputs are standard 32-bit signed integer ranges (though Python handles arbitrary precision). Constraints specify values between -1000 and 1000, so overflow isn’t a concern for the return type, but we still need to handle negative numbers correctly since they affect how bits propagate in two’s complement representation.

Intuition

If I were asked this on an interview without thinking about it first, my initial thought might be recursion: decrement a and increment b, or vice versa until one is zero. However, that still relies on the concept of addition implicitly if we use built-in math functions to adjust values.

The core insight comes from how CPUs perform hardware addition at a binary level. Addition consists of two parts:

  1. Sum without carry: This happens when bits differ (0+1=1 or 1+0=1) and both are zero (0+0=0). If we XOR (^) the numbers, a ^ b gives us exactly this sum bit-by-bit ignoring carries.
  2. Carry propagation: A carry occurs only when both bits at a position are 1. This is captured by bitwise AND (&). Since a carry affects the next higher bit (left shift), we calculate (a & b) << 1.

The algorithm iteratively updates a to be the XOR sum and b to be the new carries, repeating until there are no more carries left (b == 0). At that point, a holds the final result.

Approach

I will use a loop-based approach rather than recursion to avoid hitting Python’s default recursion limit on larger inputs (though constraints here are small). Inside the loop:

  1. Calculate the carry bits using (a & b) << 1.
  2. Update a by XORing it with b (a ^= b). This effectively adds without considering carries yet.
  3. Assign the calculated carry to b.
  4. Repeat until b is zero, meaning all carries have been resolved into a.

Complexity Analysis

  • Time Complexity: O(1)O(1) relative to input size in practical terms because integers are fixed-width (typically 64-bit or arbitrary precision). In the worst case for a number of bits kk, it takes proportional time, but given constraints (-1000 to 1000), this is constant.
  • Space Complexity: O(1)O(1) as we only use a few integer variables regardless of input size.

Solution

def getSum(a: int, b: int) -> int:
    while b != 0:
        # Calculate carry bits and shift them to the left (next position)
        carry = (a & b) << 1 
        # Add without carry using XOR; this updates 'a' with sum of current bit positions
        a ^= b
        # Move the carries into 'b' for next iteration
        b = carry
    
    return a

Edge Cases Handled

  • Negative Numbers: Python’s bitwise operators work on two’s complement representation. The logic naturally handles negative inputs because & and ^ operate bit-by-bit, correctly propagating carries across the sign boundary in arbitrary precision integers until convergence.
  • Zero Inputs: If either input is zero initially (e.g., a=0, b=-5), the loop runs only for non-zero carry propagation steps before terminating when no more carries exist.
  • Overflow/Underflow: While standard languages might overflow, Python integers have arbitrary precision. The bitwise logic naturally handles values outside 32-bit bounds if they were to occur (though constraints limit us here).