DSA problem

Sum of Two Integers

MediumBit ManipulationPattern: Bit Manipulationtop300AmazonAppleMicrosoft

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

The trick is to reproduce binary addition using only bitwise operations. For any two bits, their XOR a ^ b gives the sum without carry, and their AND a & b gives the positions that generate a carry. Shifting that carry left by one, (a & b) << 1, moves it to the next higher position where it must still be added in.

Repeat the process: set a to the partial sum and b to the shifted carry, looping until the carry becomes 0. At that point a holds the final sum. This mirrors how a ripple-carry adder works in hardware and naturally handles negative numbers via two's complement.

Examples

Example 1

Input: a = 1, b = 2

Output: 3

Explanation: Sum without carry: 1 ^ 2 = 3. Carry: (1 & 2) << 1 = 0. Carry is 0, so the answer is 3.

Example 2

Input: a = 2, b = 3

Output: 5

Explanation: First pass: sum 2 ^ 3 = 1, carry (2 & 3) << 1 = 4. Second pass: sum 1 ^ 4 = 5, carry (1 & 4) << 1 = 0. Result is 5.

Example 3

Input: a = -2, b = 3

Output: 1

Explanation: Using two's complement bit patterns, the carry-propagation loop converges to 1.

Constraints

-1000 <= a, b <= 1000

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

bit-manipulationmath

Browse all DSA problems