Code Implementation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # Mask to get last 32 bits
        mask = 0xFFFFFFFF
        while b != 0:
            # ^ gets sum without carrying
            a, b = (a ^ b) & mask, ((a & b) & mask) << 1
        # if a is negative, get a's two's complement positive value then return its negative
        return a if a <= MAX else ~(a ^ mask)
      

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

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

var getSum = function(a, b) {
    // 32 bits integer max
    const MAX = 0x7FFFFFFF;
    const mask = 0xFFFFFFFF;
    while (b !== 0) {
        let temp = (a ^ b) & mask;
        b = ((a & b) & mask) << 1;
        a = temp;
    }
    return a <= MAX ? a : ~(a ^ mask);
};
      

Problem Description

The "Sum of Two Integers" problem asks you to compute the sum of two integers a and b without using the + or - operators. Instead, you must use bitwise operations to perform the addition. The function should return an integer representing the sum of a and b. The input values can be positive, negative, or zero, and you should consider 32-bit signed integer overflow semantics.

Thought Process

At first glance, this problem seems tricky because it forbids the most direct way to add two numbers. The brute-force idea—incrementing a by 1, b times—is inefficient and not practical for large values. Instead, we need to think about how addition works at the binary level.

In binary, addition is performed by adding each bit and carrying over when both bits are 1. Bitwise operators like ^ (XOR) can sum bits without carrying, while & can identify where carries occur. The challenge is to combine these operations to mimic normal addition.

The insight is that we can repeatedly compute the sum without carry, then add the carry in the next iteration, until no carry remains. This is a shift from thinking about numbers as whole values to working with their binary representations.

Solution Approach

To add two integers without using + or -, we use bitwise operations:

• Step 1: Compute the sum without carry using XOR (a ^ b). This adds each bit except where both are 1.
• Step 2: Compute the carry using AND (a & b) and shift it left by 1 (<< 1). This finds where a carry would occur.
• Step 3: Assign the result of step 1 to a and the result of step 2 to b. Repeat the process until b (the carry) becomes zero.
• Step 4: For languages with fixed integer sizes, mask the results to 32 bits to simulate overflow and handle negative numbers correctly.
• Step 5: Return the final value of a. If the result is negative in 32-bit representation, convert it to a signed integer.

This approach efficiently simulates addition at the binary level, avoiding the forbidden operators entirely.

Example Walkthrough

Let's walk through an example with a = 2 and b = 3:

• First iteration:
  • XOR: 2 ^ 3 = 1 (binary: 10 ^ 11 = 01)
  • Carry: (2 & 3) << 1 = 2 << 1 = 4 (binary: 10 & 11 = 10; 10 << 1 = 100)
  • Update: a = 1, b = 4
• Second iteration:
  • XOR: 1 ^ 4 = 5 (binary: 001 ^ 100 = 101)
  • Carry: (1 & 4) << 1 = 0 << 1 = 0 (binary: 001 & 100 = 000)
  • Update: a = 5, b = 0
• Since b is now zero, we stop. The answer is 5.

This process works for negative numbers too, as the bitwise operations and masking handle the sign bits correctly.

Time and Space Complexity

Brute-force approach: If you tried incrementing a by 1, b times, the time complexity would be O(b), which is inefficient for large b.

Bitwise approach (optimized): Each iteration reduces the number of carry bits. For 32-bit integers, the loop runs at most 32 times (once per bit), so the time complexity is O(1) — constant time. Space complexity is also O(1) because only a fixed number of variables are used.

Summary

The "Sum of Two Integers" problem demonstrates how bitwise operations can be used to perform arithmetic at a low level, bypassing the usual addition and subtraction operators. By decomposing addition into sum-without-carry and carry calculations, and iterating until no carry remains, we achieve a constant-time solution that works for all integer values. This approach is both efficient and elegant, leveraging core computer science concepts.