Difficulty: Medium · LeetCode 371

Problem

Calculate a + b without using the operators + or -.

Understanding the problem

a ^ b computes the sum bit-by-bit ignoring carries. (a & b) << 1 produces the carry bits shifted into position. Repeat, treating the carry as the new addend, until there is no carry left.

Intuition

Binary addition: XOR gives the digit sum without carry; AND gives where carries occur, shifted left one position. Mask to 32 bits to simulate fixed-width arithmetic. Handle sign extension at the end for negative results.

Approach

Set MASK = 0xFFFFFFFF (32 bits), MAX_INT = 0x7FFFFFFF.
While b != 0: compute carry = (a & b) << 1.
a = (a ^ b) & MASK, b = carry & MASK.
If a <= MAX_INT return a, else return ~(a ^ MASK) (sign-extend negative).

Naive Solution — Brute Force

In Python, just return a + b — but this violates the constraint.

Python

class Solution:
    def getSum(self, a, b):
        return a + b  # violates constraint

C++

class Solution {
public:
    int getSum(int a, int b) {
        return a + b;  // violates constraint
    }
};

Java

class Solution {
    public int getSum(int a, int b) {
        return a + b;  // violates constraint
    }
}

JavaScript

var getSum = function(a, b) {
    return a + b;  // violates constraint
};

Time: O(1) · Space: O(1)

Optimized Code (Python 3)

Python

class Solution:
    def getSum(self, a, b):
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

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

        if a <= MAX_INT:
            return a

        return ~(a ^ MASK)

C++

class Solution {
public:
    int getSum(int a, int b) {
        // uint32_t wraps at 32 bits, doing the job of Python's MASK
        uint32_t x = a;
        uint32_t y = b;

        while (y != 0) {
            uint32_t carry = (x & y) << 1;
            x = x ^ y;
            y = carry;
        }

        // Reinterpret the 32-bit pattern as a signed int
        return (int)x;
    }
};

Java

class Solution {
    public int getSum(int a, int b) {
        // Java ints are already 32-bit two's complement, so no MASK is needed
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }

        return a;
    }
}

JavaScript

var getSum = function(a, b) {
    // JS bitwise operators work on 32-bit signed ints, so no MASK is needed
    while (b !== 0) {
        const carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }

    return a;
};

Time: O(1) — max 32 iterations · Space: O(1)

Takeaway

Pattern — XOR = addition without carry; (a & b) << 1 = carry; repeat until carry is 0