Sum of Two Integers medium

Problem Statement

Given two integers a and b, return 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 and Explanation

The core idea is to use bit manipulation to simulate addition. We can break down addition into two operations:

  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 the bits are different, the result is 1; otherwise, it's 0.

  3. Left Shift (<<): We need to shift the carry bits to the left by one position to prepare them for the next iteration.

We repeat steps 1, 2, and 3 until there are no more carry bits. Let's trace an example:

Let's add 3 (binary 0011) and 5 (binary 0101).

Iteration 1:

  • carry = a & b = 0011 & 0101 = 0001
  • sum = a ^ b = 0011 ^ 0101 = 0110
  • a = sum = 0110
  • b = carry << 1 = 0010

Iteration 2:

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

Iteration 3:

  • carry = a & b = 0100 & 0100 = 0100
  • sum = a ^ b = 0100 ^ 0100 = 0000
  • a = sum = 0000
  • b = carry << 1 = 1000

Iteration 4:

  • carry = a & b = 0000 & 1000 = 0000
  • sum = a ^ b = 0000 ^ 1000 = 1000
  • a = sum = 1000
  • b = carry << 1 = 0000

Since b (carry) is now 0, the loop terminates. The final sum (1000) is 8, which is the correct result (3 + 5 = 8).

Code

def getSum(a, b):
    """
    Calculates the sum of two integers without using '+' or '-'.

    Args:
        a: The first integer.
        b: The second integer.

    Returns:
        The sum of a and b.
    """
    while b != 0:
        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 integer. The number of iterations is proportional to the number of bits needed to represent the integers.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.