LeetCode · #371

Sum of Two Integers Solution

Calculate the sum of two integers without using + or -.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #371

🏗️

Pattern

Bit Manipulation — half adder

Given two integers a and b, return their sum without using operators + or -.

Example

Input: a = 1, b = 2 Output: 3

Constraints

• -1000 ≤ a, b ≤ 1000

Section Two · Approach 1

Increment/Decrement Loop

Use ++ or -- in a loop. Technically cheating (these use + and - underneath) and O(|b|) slow.

The insight: Simulate a half-adder. XOR computes the sum without carry. AND + shift-left computes the carry. Repeat until no carry remains.

Section Three · Approach 2

Bit Manipulation (Half Adder) — O(32) = O(1)

Three rules from digital logic:
• a XOR b = sum of each bit pair without carry
• (a AND b) << 1 = the carry produced by each bit pair
Repeat: a = a XOR b, b = carry, until carry == 0.

💡 Mental model: Think of how you add numbers by hand column by column. XOR gives you what digit to write down (sum without carry). AND-then-shift gives you what to carry to the next column. You keep iterating until there's nothing left to carry — then the XOR result is the final sum. At most 32 iterations for 32-bit ints.

Algorithm

While b != 0:
carry = (a AND b) << 1
a = a XOR b
b = carry
Return a.

🎯 When to recognize this pattern: "Add/subtract without arithmetic operators." This is the classic half-adder from digital circuits mapped to code. Also applies to LC 67 (Add Binary — same idea with strings) and forms the basis of CPU adder circuits.

Python note: Python integers have arbitrary precision — no 32-bit overflow. Must manually mask to 32 bits and handle sign extension. Use & 0xFFFFFFFF to keep 32 bits and convert back using ~(result ^ 0xFFFFFFFF) for negatives.

Section Four · Trace

Visual Walkthrough

Trace for a=3 (011), b=5 (101). Expected: 8 (1000).

Sum of Two Integers — Half Adder Simulation

Section Five · Implementation

Code — Java & Python

Java — Half adder loop

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

Python — 32-bit masked half adder

 class Solution:
def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
MAX  = 0x7FFFFFFF while b & MASK:
            carry = ((a & b) << 1) & MASK
            a = (a ^ b) & MASK
            b = carry
# Handle negative: if bit 31 set, extend sign return a if a <= MAX else ~(a ^ MASK)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Note
Loop ++/--	O(\|b\|)	O(1)	Cheating; slow for large b
Half adder ← optimal	O(1) (≤32 iters)	O(1)	Carry propagates at most 32 positions

Why at most 32 iterations? Each iteration, the carry shifts left by 1 bit. After 32 shifts, the carry is always 0 (for 32-bit integers). In practice, it terminates much earlier — when there are no more overlapping set bits.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
One zero	`a=5, b=0`	carry=0 immediately → return a=5.
Negative + positive	`a=-1, b=1`	Works in two's complement. XOR handles bit cancellation correctly.
Both negative	`a=-2, b=-3`	Two's complement XOR and carry logic works correctly for negatives in Java. Python needs masking.
Overflow boundary	`a=1000, b=1000`	Within 32-bit range → 2000. Fine.

⚠ Common Mistake: In Python, integers are unbounded. Without masking to 0xFFFFFFFF, the carry can grow infinitely and the loop never terminates for negative numbers. Always mask: carry = ((a & b) << 1) & 0xFFFFFFFF and a = (a ^ b) & 0xFFFFFFFF. Then sign-extend the result if the top bit is set.

← Back to Math & Bit problems

LearningTree

LC 371 · Sum of Two Integers — Solution & Explanation | DSA Guide