Blind 75Medium

Sum of Two Integers — Bitwise Addition

Use XOR for partial sums and AND/shift for carries until no carry remains.

Bit Manipulation

View problem on LeetCode

Problem Statement

Calculate the sum of two integers without using + or - operators.

Why This Problem Matters

Demonstrates bit-level arithmetic and carry handling.
Common bit manipulation interview question.
Builds understanding of how addition works at the hardware level.

Thought Process

Compute partial sum with XOR

a XOR b adds bits without considering carries.

Compute carry with AND

a AND b identifies positions needing a carry; shift left to add in next iteration.

Iterate until carry zero

Repeat using new sum and carry until carry vanishes.

Step-by-Step Reasoning

While carry != 0: sum = a XOR b, carry = (a AND b) << 1, set a = sum, b = carry.
Return a after loop.

Dry Run

a = 5 (0101), b = 3 (0011)

sum = 0110 (6), carry = 0010 (2) → second iteration yields 8 with carry 0; returns 8 (correct).

a = -1, b = 1

Carry logic using signed ints still converges to 0.

Complexity Analysis

Time

O(1)

Space

O(1)

Why

32-bit integers converge within bounded iterations.

Annotated Solution

JAVA

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

XOR handles addition without carry, AND captures carry bits; repeating until carry zero replicates binary addition.

Common Pitfalls

Using signed shift >> for carry works but ensure you handle negative numbers carefully.
Infinite loop occurs if you forget to update a and b each iteration.
Long type may be required for languages where shifting on ints overflows—mention if asked.

Follow-Up Questions

How do you implement subtraction, multiplication, or division with bit operations?
Can you extend this to arbitrary precision integers?

Key Takeaways

Bitwise operations can emulate arithmetic operations.

Understanding carries clarifies how addition works under the hood.

Discuss overflow behaviour based on language specification.