LeetEye LeetEye
Medium Bit Manipulation ~5 min

Sum of Two Integers

bit-manipulation sum-of-two-integers

Problem

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
Key Insight

XOR gives sum without carry. AND shifted left gives carry. Repeat until no carry.

XOR = sum without carry. (AND << 1) = carry bits. Add sum and carry repeatedly until carry is 0.

How to Approach This Problem

Pattern Recognition: When you see keywords like sum of two integers bit-manipulation, think Bit Manipulation.

Step-by-Step Reasoning

1 a ^ b gives:
Answer: Sum without considering carries
XOR adds bits without carry: 0+0=0, 0+1=1, 1+0=1, 1+1=0 (no carry).
2 Carry happens when:
Answer: Both bits are 1
1 + 1 = 10 in binary. Generates a carry to next position.
3 Carry from a + b is:
Answer: a & b
AND finds positions where both bits are 1 (where carries occur).
4 The carry needs to be:
Answer: Shifted left by 1
Carry from position i affects position i+1. Shift left.
5 We stop when:
Answer: Carry becomes 0
When no carry, XOR is the final answer.

Solution

def getSum(a: int, b: int) -> int:
    # Use 32-bit mask for Python (handles negatives)
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    
    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & MASK
        b = carry & MASK
    
    # Handle negative numbers
    return a if a <= MAX_INT else ~(a ^ MASK)

Complexity Analysis

Time O(1)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye