Sum of Two Integers

Problem Description

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

Examples

Constraints

• -1000 ≤ a, b ≤ 1000

Adding Bits and Carrying Overflows

To add two numbers without arithmetic operators, we must simulate binary addition at the bit level:

• Summing: The sum of two bits (without carry) is represented by the bitwise XOR operator: a ^ b. For example, 1 ^ 0 = 1, and 1 ^ 1 = 0.
• Carrying: A carry is generated only when both bits are 1. This is represented by bitwise AND: a & b. Since the carry moves to the next higher digit, we shift it left by one: (a & b) << 1.

We repeat this process: we calculate the sum (stored in a) and the carry (stored in b). In the next iteration, we add the carry b to a using the same logic. We continue until the carry b becomes 0.

Solution 1: Bitwise Addition (In-Place)

Iteratively update variables using XOR for sum and shifted AND for carry, terminating when the carry is zero.

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // compute carry bits shifted left
            a = a ^ b;                // compute sum bits without carry
            b = carry;                // update b to carry to add next
        }
        return a;
    }
}

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Python uses arbitrary precision integers, so we must mask to 32 bits
        mask = 0xFFFFFFFF

        while b != 0:
            carry = (a & b) << 1
            a = (a ^ b) & mask
            b = carry & mask

        # if a is negative in 32-bit signed representation, format it
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            // cast to unsigned to avoid signed shift overflow compile checks
            int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

Complexity Analysis:

• Time Complexity: O(1). The loop runs at most 32 times because the carry shifts left by one bit each step, eventually becoming 0 within 32 steps.
• Space Complexity: O(1) auxiliary space.

Where it breaks: In Python, integers have arbitrary precision (they do not overflow at 32 bits, but grow infinitely). This means the carry will shift left indefinitely, causing an infinite loop. We must apply a 0xFFFFFFFF mask at each step to force 32-bit truncation.

Common Mistakes

• Forgetting that Python integers have arbitrary precision. If you omit the bitmask & 0xFFFFFFFF in Python, the loop will never terminate because b will never reach 0.
• Overwriting the value of a before calculating the carry. If you do a = a ^ b first, you will calculate the next carry using the updated a value, which is incorrect. Save the carry in a temporary variable first.
• Using arithmetic sum operators inside helper blocks. Do not attempt to use + or - anywhere in the logic, as it violates the primary constraint.

Frequently Asked Questions

How does this algorithm handle negative numbers? Computers represent negative numbers using Two’s Complement representation. The bitwise addition operations (XOR and AND) perform identical calculations on two’s complement representations without needing any special signs logic.

Can we solve this recursively? Yes. The recursive translation of the loop is: return b == 0 ? a : getSum(a ^ b, (a & b) << 1). In C++, cast the carry term to unsigned to prevent compiler warnings.

What does this problem test in interviews? It tests your understanding of binary addition mechanics, bitwise shift operations, and Python’s arbitrary precision integer handling.

← All Problems