371. Sum of Two Integers

371

MediumBit ManipulationBit manipulation simulating a full adderAdd via XOR and carry

Sum of Two Integers

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

In plain English

Reproduce integer addition using only bitwise operations, correctly handling negative numbers.

Picture it like this

It is grade-school column addition in base 2: XOR is 'write the digit', AND-then-shift-left is 'carry the one to the next column'. You keep sweeping columns until nothing is left to carry.

Example

Input: a = 1, b = 2
Output: 3
Why: 1 + 2 = 3; XOR gives the sum bits (01 ^ 10 = 11 = 3) and there is no carry, so the result is 3.

Constraints

-1000 <= a, b <= 1000

Pattern lesson

See the pattern, then code

Add via XOR and carry

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. Binary addition splits into two parts: a ^ b gives the sum of each bit position ignoring carries, and (a & b) << 1 gives the carries that must ripple one position left. Repeat until there is no carry left. A 32-bit mask keeps Python's unbounded integers behaving like fixed-width two's-complement so negatives work.

New words, made simpleKnow these before the algorithm

XOR (^): Adds two bits without carry: 1^1 = 0 (with a carry handled separately).
Carry: (a & b) << 1 — a bit is carried where both inputs are 1, then moved one position left.
32-bit mask (0xFFFFFFFF): Restricts values to 32 bits so Python's big integers emulate fixed-width two's complement.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Use + directly

Forbidden by the problem constraints.

Just return a + b.

Time O(1)Space O(1)

Best choiceXOR sum with carry loop

Uses only bitwise ops and handles negatives.

Repeatedly split into carry-free sum (XOR) and carry (AND << 1) until the carry vanishes, using a 32-bit mask for signed correctness.

Time O(1)Space O(1)

The rule we keep true

Invariant

At the top of each loop iteration, a holds the running carry-free partial sum and b holds the outstanding carry; a + b (mathematically) always equals the true 32-bit sum of the original inputs.

Why this is correct

Reasoning

Each iteration replaces the pair (a, b) with (a ^ b, (a & b) << 1), which preserves the total because a + b = (a XOR b) + 2*(a AND b). The carry strictly moves toward higher bit positions and, within 32 bits, eventually shifts out to zero, so the loop terminates with the full sum in a.

The algorithm in three movesSay these aloud before coding

1Mask a and b to 32 bits

a=1 (01), b=2 (10)

2Loop while b (the carry) is nonzero: compute carry = (a & b) << 1 masked, then a = a ^ b masked, then b = carry

carry = (a & b) << 1 = 0

3Convert the masked result back to a signed integer if it exceeds the 32-bit positive range

a = a ^ b = 11 = 3, b = 0 -> stop

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

010

101

112

1 · Reada=1, b=2

2 · AskReduce to 32 bits

3 · Update statea=1, b=2

4 · ResultNo change for small positives

Key takeaway

XOR produces the carry-free sum 11; the carry is 0, so addition completes in one step.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Clamp to 32 bits
Masking makes Python integers behave like fixed-width values so carries and sign work correctly.
2
Lines 5-8Sum and carry loop
XOR builds the carry-free sum while (a & b) << 1 forms the carry; iterate until the carry is gone.
3
Lines 9Reinterpret as signed
If the masked result exceeds the positive 32-bit range, convert it back to its negative two's-complement value.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

a = 0 or b = 0 returns the other operand
One negative operand, e.g. a = -1, b = 1 returns 0
Both negative, e.g. a = -2, b = -3 returns -5 via the sign-fix branch

Common beginner mistakes

Omitting the 32-bit mask, so Python's unbounded integers loop forever on negative carries
Forgetting the final signed conversion, returning a large positive number instead of a negative
Using x & (x - 1) or other bit tricks that do not model carry propagation

Check your understanding

Why does the loop terminate even though carries can chain across many bit positions?

Sum of Two Integers

Sum of Two Integers

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation