Problem 34.8 · Bit ManipulationMedium

Sum of Two Integers

What it teaches: Addition as XOR (sum without carry) plus AND-shift (the carries), repeated.

Practise it on judges as “Sum of Two Integers”.

The problem

Return a + b without using + or −.

Example 1

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

Constraints

−1000 ≤ a, b ≤ 1000

Pattern clues in the wording

→ Arithmetic without arithmetic operators

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int getSum(int a, int b) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	a = 1 b = 2	3
2	a = 2 b = 3	5

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Carry loop · O(32)

Carry loop

Time O(32) Space O(1)

while b ≠ 0: carry = (a & b) << 1; a = a ^ b; b = carry.

Approach 1

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
}

Verdict: How an adder circuit works.

Before you submit

Edge cases and common mistakes

Test these inputs

Negative numbers (two's complement makes them work)
One operand 0

Mistakes people make

Assuming the loop fails for negative numbers (in Java the carry shifts out within 32 steps, so it always ends).

Interview

Follow-up questions

How would you subtract?

Command Palette

The problem

Approaches

Carry loop

Edge cases and common mistakes

Follow-up questions