371. Sum of Two Integers (Medium)

Problem

Calculate the sum of two integers a and b without using the + or - operators.

Example

a = 1, b = 2 → 3
a = 2, b = 3 → 5

LeetCode 371 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Bit-by-bit with carry (language-agnostic)

Simulate a full-adder one bit at a time over 32 bits.

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    result = 0
    carry = 0
    for i in range(32):                         # L1: always 32 iterations
        bit_a = (a >> i) & 1                    # L2: O(1)
        bit_b = (b >> i) & 1                    # L3: O(1)
        result |= ((bit_a ^ bit_b ^ carry) & 1) << i  # L4: O(1), sum bit
        carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry)  # L5: O(1)
    # Two's complement fix for negatives
    return result if result < (1 << 31) else result - (1 << 32)

function getSum(a: number, b: number): number {
    let result = 0;
    let carry = 0;
    for (let i = 0; i < 32; i++) {                  // L1: always 32 iterations
        const bitA = (a >> i) & 1;                  // L2: O(1)
        const bitB = (b >> i) & 1;                  // L3: O(1)
        result |= ((bitA ^ bitB ^ carry) & 1) << i; // L4: O(1), sum bit
        carry = (bitA & bitB) | (bitA & carry) | (bitB & carry); // L5: O(1)
    }
    return result | 0;  // sign-extend to 32-bit signed
}

func getSum(a int, b int) int {
    result := 0
    carry := 0
    for i := 0; i < 32; i++ {                       // L1: always 32 iterations
        bitA := (a >> i) & 1                         // L2: O(1)
        bitB := (b >> i) & 1                         // L3: O(1)
        result |= ((bitA ^ bitB ^ carry) & 1) << i  // L4: O(1), sum bit
        carry = (bitA & bitB) | (bitA & carry) | (bitB & carry) // L5: O(1)
    }
    return int(int32(result)) // reinterpret as signed 32-bit
}

final class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        let left = UInt32(bitPattern: Int32(a))
        let right = UInt32(bitPattern: Int32(b))
        var result: UInt32 = 0
        var carry: UInt32 = 0

        for bit in 0..<32 {
            let leftBit = (left >> bit) & 1
            let rightBit = (right >> bit) & 1
            let sumBit = leftBit ^ rightBit ^ carry
            result |= sumBit << bit
            carry = (leftBit & rightBit) | (carry & (leftBit ^ rightBit))
        }

        return Int(Int32(bitPattern: result))
    }
}

Where the time goes, line by line

Variables: B = 32 (fixed bit width).

Line	Per-call cost	Times executed	Contribution
L1-L5 (bit loop)	$O(1)$	32	$O(1)$ ← dominates (constant)
L2-L3 (extract bits)	$O(1)$	32	$O(1)$
L4-L5 (sum + carry)	$O(1)$	32	$O(1)$

All 32 iterations are $O(1)$ ; the whole function is effectively $O(1)$ .

Complexity

Time: $O(32)$ = $O(1)$ , driven by L1/L2-L5 (32 fixed iterations of full-adder logic).
Space: $O(1)$ .

Approach 2: XOR + carry loop (canonical)

a ^ b is “sum without carry.” (a & b) << 1 is “the carry.” Iterate until carry is 0.

In Python, integers are arbitrary-width, so we mask to 32 bits to simulate C-like overflow. TypeScript’s bitwise operators already work on 32-bit signed integers.

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    while b != 0:                               # L1: loop at most 32 times
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK  # L2: O(1) per iter
    return a if a <= MAX_INT else ~(a ^ MASK)   # L3: O(1) sign correction

function getSum(a: number, b: number): number {
    const MASK = 0xFFFFFFFF;
    const MAX_INT = 0x7FFFFFFF;
    while (b !== 0) {                                       // L1: loop at most 32 times
        const carry = ((a & b) << 1) & MASK;               // L2a: O(1), compute carry
        a = (a ^ b) & MASK;                                 // L2b: O(1), sum without carry
        b = carry;
    }
    return a <= MAX_INT ? a : ~(a ^ MASK);                  // L3: O(1) sign correction
}

func getSum(a int, b int) int {
    const MASK = 0xFFFFFFFF
    const MAX_INT = 0x7FFFFFFF
    for b != 0 {                                            // L1: loop at most 32 times
        carry := (a & b) << 1                              // L2a: O(1), compute carry
        a = (a ^ b) & MASK                                 // L2b: O(1), sum without carry
        b = carry & MASK
    }
    a &= MASK
    if a <= MAX_INT {                                       // L3: O(1) sign correction
        return a
    }
    return int(int32(a))
}

final class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var partial = UInt32(bitPattern: Int32(a))
        var carry = UInt32(bitPattern: Int32(b))
        while carry != 0 {
            let nextCarry = (partial & carry) << 1
            partial ^= carry
            carry = nextCarry
        }
        return Int(Int32(bitPattern: partial))
    }
}

Where the time goes, line by line

Variables: B = 32 (fixed bit width); loop terminates in at most B iterations.

Line	Per-call cost	Times executed	Contribution
L1, L2 (carry loop)	$O(1)$	at most 32	$O(1)$ ← dominates (constant)
L3 (sign correction)	$O(1)$	1	$O(1)$

Each iteration shifts the carry left by one bit; after at most 32 iterations the carry falls off the 32-bit window.

Complexity

Time: $O(32)$ = $O(1)$ , driven by L1/L2 (at most 32 carry-propagation iterations).
Space: $O(1)$ .

The final sign correction converts back from unsigned 32-bit to a signed integer.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Python built-ins (cheating)

def get_sum(a, b):
    return sum([a, b])

Doesn’t satisfy the problem, but shown for completeness.

Try this approach:

Swift

final class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        a + b
    }
}

Swift notes

Swift traps on ordinary signed overflow, so the bitwise approaches convert the bounded inputs to Int32 bit patterns stored in UInt32. Carry propagation then wraps within exactly 32 bits before the result is reinterpreted as signed. The built-in + version is runnable for comparison, but it violates the problem’s operator constraint.

Summary

Approach	Time	Space	Notes
Bit-by-bit full adder	$O(32)$	$O(1)$	Explicit and clear
XOR + carry loop	$O(32)$	$O(1)$	Canonical
`sum(...)`	$O(1)$	$O(1)$	Not allowed by the problem

The XOR + carry loop is the classic bitwise-arithmetic pattern. Same core idea simulates subtraction, multiplication, and division with only &, |, ^, and shifts.

Test cases

# Quick smoke tests, paste into a REPL or save as test_371.py and run.
# Uses the canonical implementation (Approach 2: XOR + carry loop).

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    while b != 0:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    return a if a <= MAX_INT else ~(a ^ MASK)

def _run_tests():
    assert get_sum(1, 2) == 3
    assert get_sum(2, 3) == 5
    assert get_sum(0, 0) == 0              # edge: both zero
    assert get_sum(-1, 1) == 0             # edge: cancel to zero
    assert get_sum(-5, 3) == -2            # negative result
    assert get_sum(2**30, 2**30) == 2**31  # large positive (fits in 64-bit Python int)
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function getSum(a: number, b: number): number {
    const MASK = 0xFFFFFFFF;
    const MAX_INT = 0x7FFFFFFF;
    while (b !== 0) {
        const carry = ((a & b) << 1) & MASK;
        a = (a ^ b) & MASK;
        b = carry;
    }
    return a <= MAX_INT ? a : ~(a ^ MASK);
}

console.assert(getSum(1, 2) === 3);
console.assert(getSum(2, 3) === 5);
console.assert(getSum(0, 0) === 0);
console.assert(getSum(-1, 1) === 0);
console.assert(getSum(-5, 3) === -2);
console.assert(getSum(2 ** 30, 2 ** 30) === 2 ** 31);
console.log("all tests pass");

func getSum(a int, b int) int {
    const MASK = 0xFFFFFFFF
    const MAX_INT = 0x7FFFFFFF
    for b != 0 {
        carry := (a & b) << 1
        a = (a ^ b) & MASK
        b = carry & MASK
    }
    a &= MASK
    if a <= MAX_INT {
        return a
    }
    return int(int32(a))
}

None.

Bit Manipulation, the binary representation pattern for masks, toggles, shifts, and arithmetic shortcuts.
Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.

371. Sum of Two Integers (Medium)

Problem

Try it yourself

Approach 1: Bit-by-bit with carry (language-agnostic)

Approach 2: XOR + carry loop (canonical)

Approach 3: Python built-ins (cheating)

Swift notes

Summary

Test cases

Related data structures

Related concepts