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:
- 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 ^ bgives us exactly this sum bit-by-bit ignoring carries. - 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:
- Calculate the carry bits using
(a & b) << 1. - Update
aby XORing it withb(a ^= b). This effectively adds without considering carries yet. - Assign the calculated carry to
b. - Repeat until
bis zero, meaning all carries have been resolved intoa.
Complexity Analysis
- Time Complexity: 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 , it takes proportional time, but given constraints (-1000 to 1000), this is constant.
- Space Complexity: 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).