Sum of Two Integers medium

Problem Statement

You are given two integers a and b. You must 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: 5

Steps

The key to solving this problem is to understand bit manipulation. We can use bitwise operators to simulate addition. The process involves iteratively performing the following steps:

  1. Calculate the sum without carry: This is done using the bitwise XOR operator (^). XOR gives you a 1 only when one of the bits is 1 and the other is 0 (simulating addition without considering carry).

  2. Calculate the carry: This is done using the bitwise AND operator (&) shifted to the left by one bit (<< 1). AND gives you a 1 only when both bits are 1, representing a carry.

  3. Iterate: Repeat steps 1 and 2 until there's no carry left (i.e., the carry becomes 0).

Explanation

Let's illustrate with an example: a = 3 (binary 0011) and b = 5 (binary 0101).

Iteration 1:

  • sum = a ^ b = 0011 ^ 0101 = 0110 (6) This is the sum without considering carries.
  • carry = (a & b) << 1 = (0011 & 0101) << 1 = (0001) << 1 = 0010 (2) This is the carry.

Iteration 2:

  • a = sum = 0110
  • b = carry = 0010
  • sum = a ^ b = 0110 ^ 0010 = 0100 (4)
  • carry = (a & b) << 1 = (0110 & 0010) << 1 = (0010) << 1 = 0100 (4)

Iteration 3:

  • a = sum = 0100
  • b = carry = 0100
  • sum = a ^ b = 0100 ^ 0100 = 0000 (0)
  • carry = (a & b) << 1 = (0100 & 0100) << 1 = (0100) << 1 = 1000 (8)

Iteration 4:

  • a = sum = 0000
  • b = carry = 1000
  • sum = a ^ b = 0000 ^ 1000 = 1000 (8)
  • carry = (a & b) << 1 = (0000 & 1000) << 1 = 0000 (0)

The carry is now 0, so the final sum is 1000 (binary), which is 8 in decimal. This matches 3 + 5 = 8.

Code

function getSum(a: number, b: number): number {
    while (b !== 0) {
        let carry = (a & b) << 1; // Calculate carry
        a = a ^ b; // Calculate sum without carry
        b = carry; // Update b to be the carry for the next iteration
    }
    return a;
};

Complexity

  • Time Complexity: O(log n), where n is the maximum of the absolute values of a and b. This is because the number of iterations is proportional to the number of bits needed to represent the larger number.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.