HARD Lab · Binary · 21

371. Sum of Two Integers

Add two integers without using + or - by simulating a hardware adder: XOR computes the sum-without-carry each round, while (a & b) << 1 propagates the carry until it vanishes.

● MediumBit ManipulationTypeScript

PROBLEM What we're solving

Return the sum of two integers without using + or -. For example, getSum(2, 3) should return 5. In binary: 010 ^ 011 = 001 (partial sum), (010 & 011) << 1 = 100 (carry), then 001 ^ 100 = 101 = 5.

KEY IDEA XOR adds without carry; AND finds the carry

Insight → single-bit addition has two outputs: a sum bit(1 iff the inputs differ — that's XOR) and a carry bit(1 iff both inputs are 1 — that's AND). To handle multi-bit numbers, shift the carry left by one position (<< 1) so it lands in the correct column, then repeat. This is exactly what transistors do inside a CPU.

RECIPE Loop until the carry drains to zero

  • 1 · Compute carry. carry = (a & b) << 1 — AND finds positions where both bits are 1 (a carry will propagate into the next column), shift left to align it.
  • 2 · Compute partial sum. a = a ^ b — XOR adds each bit pair ignoring carries.
  • 3 · Advance b. b = carry— carry is now the new "thing to add".
  • 4 · Repeat. When b === 0 there is nothing left to add; a holds the final answer.
Classic confusion → you must compute carry before overwriting a. If you write a = a ^ b first, the old value of a is lost and (a & b) gives a wrong carry.

COST Complexity & alternatives

Naive (banned)
+ −
Disallowed by the problem constraints.
Bit-loop
O(1)
At most 32 iterations (one per bit); O(1) space.

The loop runs at most as many times as there are bit-width positions (32 for a 32-bit integer). In the worst case every iteration generates another carry, but the carry shifts left each time, so it must reach zero within 32 steps.

Pattern transfer → this XOR + carry loop is the foundation of Add Binary (LC 67), Add Strings(LC 415), and the building block for understanding how CPU arithmetic units work. The XOR trick for "difference without subtraction" also appears in Single Number (LC 136) and Missing Number (LC 268).

RUN IT XOR sums bits, (AND)<<1 propagates carry

step 0 / 5
STARTStarting with a=2 and b=3. We'll add using only bit operations: XOR computes sum-without-carry, (AND)<<1 computes the carry.
03021100+03021110
State
0010 (2)
a
0011 (3)
b
a (set bits)b (set bits)XOR result (no-carry sum)carry ((a AND b)<<1)
slowfast

TYPESCRIPT The solution, annotated

getSum.ts
function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;  // bits where both are 1 → shift left
    a = a ^ b;                    // XOR: add without carry
    b = carry;                    // carry becomes the new b
  }
  return a;
}

Reading it block by block

Line 2 — loop condition. We iterate as long as there is still a carry to add. When b (carry) reaches zero, the partial sum stored in a is the final answer.
Line 3 — compute carry first. (a & b) << 1 identifies bit positions where both values have a 1 (those columns will carry) and shifts the result one column to the left. Computed before we modify a.
Line 4 — XOR for sum-without-carry. a ^ b sets each bit where exactly one of a or b is 1 — binary addition ignoring carries. We reassign a to this value.
Line 5 — advance carry. b = carry. The carry now becomes the next value to add. On the next iteration XOR will fold it in and AND will find any new carries from it.
Line 7 — return. b === 0 means no carry remains. a is the complete sum. Return it.
Complexity → O(1) time and space — the while loop runs at most 32 times (one per bit in a 32-bit integer) because the carry shifts left each iteration and cannot exceed the word size.

INTERVIEWFollow-ups they'll ask

  • "What about negative numbers?"JavaScript bitwise operators work on 32-bit signed integers using two's complement — the same loop handles negatives correctly because XOR and AND are defined on every bit pattern.
  • "Why compute carry before XOR?" Once we overwrite a with the XOR result, the original bits are gone and we can no longer compute the correct AND.
  • "Can you do it without a loop?" A recursive approach is equivalent: getSum(a^b, (a&b)<<1) with base case b===0. Same logic, tail-recursive.
  • "What if both inputs are 0?" The loop never runs; a stays 0 and we return 0 immediately.
  • "Why does the carry always terminate?" Each iteration the carry shifts left, so the lowest set bit in b strictly increases. After 32 shifts at most, it falls off the word and becomes 0.

MNEMONIC The one-liner

"XOR is add-without-carry; AND-shift is the carry itself — loop until nothing to carry."

TRIGGERS When you see ___ → reach for ___

"no + or − operator"XOR for bits, (AND)<<1 for carry
hardware adder / ripple carrywhile (b) { carry=(a&b)<<1; a^=b; b=carry }
bit-level addition in a loopcarry shifts left, terminates in ≤32 steps
"sum without arithmetic"same pattern: XOR = diff, AND<<1 = borrow-or-carry

SKELETON The reusable shape

skeleton.ts
function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

FLASHCARDS Tap to flip

What does XOR compute in the context of addition?
The sum of each bit column ignoring any carry — "add without carry."
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What does a ^ b represent in each iteration?
QUESTION 02
What does (a & b) << 1 represent?
QUESTION 03
Why must the carry be computed BEFORE a is overwritten with a ^ b?
QUESTION 04
How many loop iterations are needed in the worst case for 32-bit integers?
QUESTION 05
getSum(5, 3) should return:
QUESTION 06
Which other LeetCode problem most directly uses the same XOR "cancel duplicates" technique?
QUESTION 07
What is the termination condition and what does it guarantee?