Sum of Two Integers medium

Problem Statement

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

Example 1:

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

Example 2:

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

Steps

The core idea is to use bit manipulation to simulate addition. We'll use two operations:

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

We'll iterate until there are no more carry bits.

Explanation

Let's break down how this works with an example: a = 3 (binary 0011), b = 5 (binary 0101).

  1. Iteration 1:

    • sum = a ^ b (0011 ^ 0101 = 0110) This is the sum without carry.
    • carry = (a & b) << 1 ( (0011 & 0101) << 1 = (0001) << 1 = 0010) This shifts the carry bits one position to the left.

  2. Iteration 2:

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

  3. Iteration 3:

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

  4. Iteration 4:

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

Since carry is now 0, the loop terminates, and the final sum (1000) is 8, which is 3 + 5.

Code

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // Calculate carry bits
            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 magnitude of the larger integer. 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.