Sum of Two Integers
MediumXOR adds, AND finds the carries
Problem
Return the sum of two integers without using + or -.
XOR adds bits without carrying; AND shifted left is the carry — repeat until the carry is gone.
The idea
XOR gives the sum of each bit ignoring carries, while AND shifted left by one gives exactly the carries. Repeat until there are no carries left and the XOR is the answer — that is what a hardware adder does.
The trick
- sum = a ^ b, carry = (a & b) << 1; loop until the carry is 0.
- In Java, mask to 32 bits as you go to keep the loop terminating.
- Subtraction is the same loop with a borrow instead of a carry.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — a=2, b=3 Values: 2, 3.
1while b != 0:2 carry = (a & b) << 13 a = a ^ b4 b = carry5return aInput
- array
- [2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = 1, b = 2
- Output:
- 3
- Explanation:
- Add without '+': XOR gives the sum bits, AND<<1 gives carries.
Example 2
- Input:
- a = 2, b = 3
- Output:
- 5
- Explanation:
- Repeat carry-and-add until no carry remains.
Example 3
- Input:
- a = -1, b = 1
- Output:
- 0
- Explanation:
- Works for negatives via two's complement.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.