Sum of Two Integers medium

Problem Statement

You are given two integers a and b. You need to calculate the sum of a and b without using the '+' or '-' operators.

Example 1

  • Input: a = 1, b = 2
  • Output: 3

Example 2

  • Input: a = -2, b = 3
  • Output: 1

Steps

The core idea is to use bit manipulation to simulate addition. We'll leverage the following concepts:

  1. Bitwise AND (&): This operation gives us the carry bits. If both bits are 1, the carry is 1; otherwise, it's 0.

  2. Bitwise XOR (^): This operation gives us the sum bits without considering the carry. If one bit is 1 and the other is 0, the result is 1; otherwise, it's 0.

  3. Left Shift (<<): This shifts the bits to the left by one position, effectively multiplying by 2. This is crucial for handling the carry bits.

We'll iterate until there are no more carry bits. In each iteration:

  • Calculate the carry using bitwise AND.
  • Calculate the sum without carry using bitwise XOR.
  • Left-shift the carry to prepare it for the next iteration.
  • Update a with the sum and b with the shifted carry.

Explanation

Let's trace the example a = 1, b = 2:

  1. Iteration 1:

    • carry = a & b = 1 & 2 = 0 (0001 & 0010 = 0000)
    • sum = a ^ b = 1 ^ 2 = 3 (0001 ^ 0010 = 0011)
    • carry << 1 = 0 << 1 = 0
    • a = sum = 3, b = carry << 1 = 0

  2. Iteration 2:

    • carry = a & b = 3 & 0 = 0 (0011 & 0000 = 0000)
    • sum = a ^ b = 3 ^ 0 = 3 (0011 ^ 0000 = 0011)
    • carry << 1 = 0 << 1 = 0
    • a = sum = 3, b = carry << 1 = 0

The loop terminates because b is 0. The final result is a = 3.

For negative numbers, the two's complement representation is implicitly handled by the bitwise operations.

Code

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

Complexity

  • Time Complexity: O(log n), where n is the magnitude of the larger input number. The number of iterations is proportional to the number of bits needed to represent the numbers.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.