Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Sum of Two Integers

Sum of Two Integers

Master this topic with zero to advance depth.

Sum of Two Integers

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

Medium

Examples

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

Level I: Brute Force (Bit-by-Bit Simulation)

Intuition

Simulate how a half-adder or full-adder works. Iterate through each bit position (0 to 31), calculate the sum of bits and the carry, and build the result bit by bit.

Thought Process

  1. Initialize res = 0, carry = 0.
  2. For i from 0 to 31:
    • Get ii-th bits of a and b.
    • sum = bitA ^ bitB ^ carry.
    • carry = (bitA & bitB) | (carry & (bitA ^ bitB)).
    • Set ii-th bit of res to sum.
  3. Return res.

Pattern: Simulation / Logic Gates

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant space.
java
public class Solution {
    public int getSum(int a, int b) {
        int res = 0, carry = 0;
        for (int i = 0; i < 32; i++) {
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            int sum = bitA ^ bitB ^ carry;
            carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
            res |= (sum << i);
        }
        return res;
    }
}
Approach 2

Level II: Recursive XOR & AND

Intuition

The iterative logic can be expressed recursively. The sum of a and b is equivalent to the XOR of a and b (sum without carry) plus the AND of a and b shifted left (the carry).

⏱ $O(1)$ - Max 32 recursive calls.💾 $O(1)$ - Recursion stack for 32 levels.
java
class Solution {
    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
    }
}
Approach 3

Level III: Optimal (Iterative XOR & AND)

Intuition

Addition can be broken into two parts: the sum without carry (a ^ b) and the carry itself ((a & b) << 1). We repeat this process until the carry becomes zero.

Thought Process

  1. a ^ b gives the sum bits where no carry is involved.
  2. a & b gives the bits where a carry is generated.
  3. Shift the carry left by 1 to add it to the next significant bit.
  4. Repeat until carry is 0.

Pattern: Recursive Addition Logic

⏱ O(1) - Max 32 iterations (number of bits).💾 O(1) - Constant space.

Detailed Dry Run

a = 2 (10), b = 3 (11)

  • Iteration 1: sum = 10 ^ 11 = 01 (1) carry = (10 & 11) << 1 = 100 (4)
  • Iteration 2: sum = 001 ^ 100 = 101 (5) carry = (001 & 100) << 1 = 000 (0) Result: 5
java
public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}
← Previous QuestionReverse Bits
Next Question →Missing Number