Sum of Two Integers

Compute a + b without using + or -.

Bit Manipulation

Pattern fit

The bit model is explicit: XOR gives the no-carry sum and AND-shift gives the carry, so you iteratively merge them until carry disappears.

Key observation

Sum = XOR, carry = (AND << 1). Repeat until carry is zero.

Target complexity

O(1) / O(1)

How to break down the solution cleanly

The bit model is explicit: XOR gives the no-carry sum and AND-shift gives the carry, so you iteratively merge them until carry disappears.

Sum = XOR, carry = (AND << 1). Repeat until carry is zero.

Define what each bit means.

Pick the one operation that naturally updates that meaning.

Reference implementation

Python

# Generic pattern template
x & (x - 1)        # clear lowest set bit
x & -x             # isolate lowest set bit
x | (1 << i)       # set bit i
x & ~(1 << i)      # clear bit i
x ^ (1 << i)       # toggle bit i
(x >> i) & 1       # read bit i

Common pitfalls

warning

Writing the recurrence without understanding the separate roles of sum and carry.

warning

Ignoring fixed-width behavior in some languages.

Common follow-ups

Can you explain this with a simple 1-bit truth table?

What language-specific issues arise in Python vs C++?

Continue with related problems

Build repeatable depth inside the Bit Manipulation cluster before moving on.

view_weekBack to the pattern page

#136

Single Number

Find the element that appears once when all others appear twice.

#338

Counting Bits

For every number from 0 to n, count how many set bits it has.

#238

Product of Array Except Self

Return an array where each value is the product of all other elements.