DSA AnimatorDSA animations
Sum of Two Integers LC #371 Medium XOR · Carry
Problem

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

Example 1
Input: a = 1, b = 1
Output: 2
Explanation: 1 + 1 = 2 using XOR + carry.
Example 2
Input: a = 2, b = 3
Output: 5
Explanation: XOR gives partial sum; AND shifted left gives carry.
Constraints: -1000 ≤ a, b ≤ 1000
Try Examples
Custom:
Approach
XOR + Carry Loop
XOR gives bit-sum without carry. AND finds carry positions. Shift carry left and repeat until carry is zero (b=0). Each iteration propagates carries one position left.
Binary Representation
Variables
a
—
b
—
carry
—
iter
0
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
XOR (a^b) computes bit-sum without carry
2
AND (a&b) finds positions where carry occurs
3
Shift carry left by 1: carry << 1
4
Repeat until b=0 (no more carry to add)
Time
O(log n)
Space
O(1)
Why It Works

Binary addition works column by column. XOR at each bit gives the sum-without-carry. AND at each bit gives where two 1s overlap — that's the carry. Shifting the carry left by 1 places it in the correct next column. We repeat until there is no more carry (b becomes 0). This exactly mimics how hardware adders work.

How to solve Sum of Two Integers

LeetCode 371 · Medium · Bit Manipulation · Pattern: XOR + Carry

Why the obvious approach is slow

Adding one at a time with increments is not allowed either, and it would be slow. We can rebuild addition from bit operations, just like a circuit does.

The key idea

XOR adds two bits without the carry: 1 plus 1 gives 0. AND finds where both bits are 1, which is where a carry is produced. Shift those carries left by one, because a carry moves into the next column. Repeat with the partial sum and the carries, until no carry is left.

Remember

XOR is sum without carry, AND shifted is the carry. Repeat until the carry is zero.

Run the animation above on your own input, or watch the 1:31 video explanation of Sum of Two Integers with a dry run and Java code.

More Bit Manipulation problems