Sum of Two Integers

Problem

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

Approach: XOR and AND with Carry Simulation

The key insight is to use XOR for sum without carry, and AND + left shift for carry.

Implementation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32-bit mask in hexadecimal
        mask = 0xFFFFFFFF

        while b != 0:
            # Calculate sum without carry (XOR)
            tmp = (a ^ b) & mask

            # Calculate carry (AND + left shift)
            carry = ((a & b) << 1) & mask

            a = tmp
            b = carry

        # Handle negative numbers
        # If a is negative (leftmost bit is 1), convert to negative
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Approach 2: Recursive

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF

        # Base case: no carry
        if b == 0:
            return a if a <= 0x7FFFFFFF else ~(a ^ mask)

        # Recursive case
        sum_without_carry = (a ^ b) & mask
        carry = ((a & b) << 1) & mask

        return self.getSum(sum_without_carry, carry)

Approach 3: Python-Specific (Handles Negative Numbers)

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF

        while b & mask:
            carry = a & b
            a = a ^ b
            b = carry << 1

        return (a & mask) if b > 0 else a

Approach 4: Simplified (May Not Work for Negative in All Languages)

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b:
            # Calculate carry
            carry = a & b

            # Calculate sum without carry
            a = a ^ b

            # Carry becomes the new b, shifted left
            b = carry << 1

        return a

Complexity Analysis

Time Complexity: O(1) or O(log n), where n is the number of bits. At most 32 iterations for 32-bit integers.
Space Complexity: O(1), only using constant variables.

Key Insights

XOR for Sum Without Carry: a ^ b gives sum of bits without considering carry (0+0=0, 1+0=1, 0+1=1, 1+1=0).
AND for Carry: a & b gives positions where carry is generated (only when both bits are 1).
Left Shift Carry: (a & b) « 1 positions the carry for the next higher bit.
Iterative Process: Repeat until there’s no carry (b becomes 0).
Example Walkthrough:
- a = 5 (101), b = 3 (011)
- sum = 101 ^ 011 = 110 (6)
- carry = (101 & 011) « 1 = 001 « 1 = 010 (2)
- a = 110, b = 010
- sum = 110 ^ 010 = 100 (4)
- carry = (110 & 010) « 1 = 010 « 1 = 100 (4)
- a = 100, b = 100
- sum = 100 ^ 100 = 000 (0)
- carry = (100 & 100) « 1 = 100 « 1 = 1000 (8)
- a = 0, b = 8
- Result: 8
Negative Number Handling: Python has arbitrary precision integers, so need mask for 32-bit simulation.
Hardware Adder: This simulates how CPUs add numbers using half-adders and full-adders.