LeetCode 371 · Medium · Bit Manipulation

Sum of Two Integers

Return a + b without using the + or − operators. The inputs may be negative; work with 32-bit two's complement integers.

O(32)time · at most 32 rounds
O(1)space
XOR + carrya half adder on every bit

two integers from −1000 to 1000

One round a ^ b adds each column ignoring carries · (a & b) << 1 is the carries, moved one column left

public int getSum(int a, int b) { while (b != 0) { // carries left to add int carry = (a & b) << 1; a = a ^ b; // sum without carries b = carry; } return a;}
a
—
b (carry in)
—
a ^ b
—
carry
—

Why it works

  1. Brute force counts: increment a by 1, b times (or decrement for negative b), using bit tricks for ±1. That is O(|b|) rounds, up to a thousand here and billions in general.
  2. Split a sum into two parts. In each column, a ^ b is the sum bit ignoring carries, and a & b marks the columns that produce a carry, which belongs one column to the left: (a & b) << 1. Their sum equals a + b, so repeat with (sum, carry) until there is no carry.
  3. At most 32 rounds: after round r, the lowest r bits of the carry are 0, so a carry can travel at most 32 columns before it falls off the top. O(1) time and space.
  4. Overflow is the point. A Java int is 32-bit two's complement and wraps silently, so a negative number is already a bit pattern, a carry shifted out of bit 31 simply disappears, and no mask is needed. The same loop ends in at most 32 rounds for any int inputs, including Integer.MIN_VALUE.
  5. Related: this is a ripple-carry adder in software. Subtraction is a + (~b + 1); Reverse Bits (190) and Number of 1 Bits (191) use the same masks and shifts.