Sum of Two Integers

How it works

We need to add two integers without using + or -. Binary addition can be built from two operations:

1. Sum without carry

   • a XOR b gives the bit-by-bit sum ignoring carry (because 1 XOR 1 = 0, which matches sum without carry)

2. Carry information

   • a AND b tells us where both bits are 1, which creates a carry
   • shifting left by 1 (<< 1) moves that carry to the next higher bit

So we can repeatedly:

• compute the carry
• update the partial sum using XOR
• add the carry again (by setting b = carry)

We keep doing this until there is no carry left (b == 0).

Because many languages use fixed-width integers (like 32-bit signed integers), we use a mask to keep only the lower 32 bits at each step. Finally, if the result represents a negative number in 32-bit two's complement form, we convert it back to a signed integer.

Steps

1. Define constants for 32-bit handling:
   • mask to keep only 32 bits
   • max_int as the largest 32-bit signed integer
2. While b is not zero:
   • Compute carry:
     • carry = (a AND b) << 1
   • Compute sum without carry:
     • a = (a XOR b), then apply the 32-bit mask
   • Move carry into b (also masked to 32 bits)
3. After the loop, a holds the 32-bit result.
4. If a is within signed range, return it directly.
5. Otherwise, convert from unsigned 32-bit to a negative signed value and return it.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Forgetting to Handle Negative Numbers

When using bit manipulation to add integers, negative numbers are represented in two's complement form. In languages like Python that have arbitrary-precision integers, you must explicitly mask results to 32 bits and convert back to signed representation when the result exceeds 0x7FFFFFFF. Failing to do this will produce incorrect results for negative inputs or negative sums.

Infinite Loop with Negative Carry

In languages with fixed-width integers (like Java, C++), left-shifting a negative carry can cause issues. When b becomes negative and you compute (a & b) << 1, the carry propagates correctly due to two's complement representation. However, in Python without masking, the carry can grow indefinitely, causing an infinite loop. Always apply a 32-bit mask to both a and b in each iteration.

Confusing XOR and AND Operations

A common mistake is mixing up the roles of XOR and AND in the addition algorithm. XOR (^) computes the sum without carry, while AND (&) followed by left shift computes the carry. Swapping these operations or forgetting the left shift on the carry will produce wrong results. Remember: XOR gives you what stays, AND shifted gives you what carries over.

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

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

        return a if a <= max_int else ~(a ^ mask)

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};