Sum of Two Integers

Problem in Plain English

Compute a + b using only bitwise operators, never + or -. The method mirrors how hardware adders combine a carry-free sum with a shifted carry until nothing carries.

Problem Statement

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

Think like a hardware adder: one bitwise pass adds every position with no carry, a second pass finds where carries arise, and the two results are combined until no carry remains.

Constraints

$-1000 \le a \le 1000$
$-1000 \le b \le 1000$
Neither + nor - may appear in the solution logic.

Examples

Example 1

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

Plain addition gives 1 + 2 = 3, rebuilt here with bitwise steps.

Example 2

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

The bits of 2 and 3 combine with one carry round to reach 5.

Example 3

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

Mixed signs flow through the same carry loop to give -2 + 3 = 1.

Example 4

Input: a = -1, b = 1
Output: 0

Opposite values cancel. In a 32-bit carry loop, the carry travels through the run of 1 bits and then falls outside the word; the remaining word is zero.

Example 5

Input: a = -1000, b = 0
Output: -1000

A zero second operand requires no carry rounds or unit transfers. Python must still return the signed value when decoding the masked initial word.

Intuition

At one bit position, two different bits produce a sum bit of 1 and no carry; two 1 bits produce a sum bit of 0 and a carry into the next position. XOR gives all carry-free sum bits at once, while AND followed by a left shift places all carries into their destination positions. For a = 1 and b = 2, no positions overlap, so XOR immediately gives 3 and the carry is zero. Negative inputs require the same finite 32-bit representation throughout.

Approaches

Unit Step Loop

Solution Details

Reveal Unit Step Loop: intuition, complexity, and code

Intuition

Transfer one unit from b into a until b reaches zero, preserving their total. To honor the operator restriction in every language, build increment by flipping trailing 1 bits and then the first 0 bit; complementing around increment gives decrement. This baseline repeats that work once per unit, whereas the next approach combines all bit positions together.

Step-by-Step Logic

Define increment by clearing trailing 1 bits and setting the next 0; define decrement by complementing before and after increment.
While b is nonzero, transfer one unit toward zero. In Example 1, b = 2 is positive: increment a = 1 to 2 and decrement b = 2 to 1.
Repeat the positive transfer: a = 2 becomes 3 and b = 1 becomes 0. If b were negative, decrement a and increment b instead.
When b reaches zero, stop and return a = 3, which holds the entire original sum.

Why It Works

Increment clears the trailing run of 1 bits and sets the first 0 bit, which is precisely binary addition of one. Decrement follows the identity that complementing a value, incrementing it, then complementing again subtracts one in two's complement. When b is positive, incrementing a and decrementing b preserves the mathematical sum; when b is negative, the reverse transfer also preserves it. Each iteration reduces the magnitude of b by one, so it terminates at zero with a equal to the original sum. All intermediate totals fit 32 bits under the stated bounds.

Dry Run

Unit Step Loop: variable states at each step
iteration	a before	b before	branch	a after	b after	invariant total
start	1	2	initialize	1	2	3
first	1	2	increment a, decrement b	2	1	3
second	2	1	increment a, decrement b	3	0	3
stop	3	0	return a	3	0	answer 3

Complexity Analysis

Time Complexity

O(|b| + 1)

Space Complexity

O(1)

Here b means the original second operand. There are exactly |b| transfers, plus constant setup and return work. Each helper examines at most 32 bits, a fixed constant, so time is O(|b| + 1), including b = 0. Constant scalar words and Python temporary integer objects use O(1) auxiliary space under this fixed-width contract. For a variable width w, the conservative bound is O(w(|b| + 1)) time and O(w) bits of storage.

Code

Solution.java

1class Solution {2    private int increment(int value) {3        int bit = 1;4        // Clear trailing ones; Java shift overflow discards carry beyond bit 31.5        while ((value & bit) != 0) {6            value ^= bit;7            bit <<= 1;8        }9        return value ^ bit;10    }11    private int decrement(int value) {12        // Complementing around increment implements subtraction of one.13        return ~increment(~value);14    }15    public int getSum(int a, int b) {16        while (b != 0) {17            if (b > 0) {18                a = increment(a);19                b = decrement(b);20            } else {21                a = decrement(a);22                b = increment(b);23            }24        }25        return a;26    }27}

Hints

Hint 1

As a baseline, transfer one unit from b toward a while preserving their total. Implement each increment by flipping binary bits rather than using a forbidden arithmetic operator.

Hint 2

Notice that a ^ b adds every bit position while ignoring carries.

Hint 3

(a & b) << 1 marks exactly where carries appear, so repeating xor-then-carry until the carry is zero finishes the addition.

Edge Cases

When b is zero, the loop can stop immediately; when only a is zero, the loop still needs to incorporate b. Python must decode an initially masked negative a even when b is zero.
Negative inputs such as a = -2, b = 3 must flow through the same carry loop and yield 1.
In Python, unbounded integers need a 0xFFFFFFFF mask or the carry loop never terminates on negatives.
A carry chain such as 511 and 1 propagates across many columns; opposite signs may use all 32 rounds despite small magnitudes.
Both negative operands, including -1000 and -1000, must decode to a signed negative result, -2000.

Common Mistakes and Interview Tips

Forgetting to shift the carry left, which adds it back into the same position it came from.
Skipping the 32-bit mask in Python, so negative carries loop forever.
Testing only positives and missing that a = -1, b = 1 must give 0.
Writing ++, --, += or -= in the baseline: the operator restriction applies to both approaches and Python has no increment operator.
Computing the carry after overwriting a, so it no longer reflects the same old operands used for XOR.
Returning the masked Python word directly for a negative result, which yields a large positive integer instead.

Key Takeaway

Xor adds without carry while and-plus-shift computes the carry: looping those two steps simulates the adder circuit inside every processor.