371. Sum of Two Integers

Description

The task is to calculate the sum of two integers a and b without using the + or - operators. The solution leverages bitwise operations to achieve this. This is often useful in low-level programming and systems where addition needs to be optimized.

Intuition

The idea behind the solution is that the bitwise XOR operation (^) can be used to add numbers without carrying, while the bitwise AND operation (&) followed by a left shift (<<) can be used to calculate the carry. By repeatedly applying these operations, we can compute the sum of the two numbers as though we were manually adding them, bit by bit.

• XOR (^) gives us the sum of bits where there is no carry.
• AND (&) followed by a left shift gives us the carry.
• We repeat the process until there is no carry left, at which point a will hold the final result.

Approach

1. Use the XOR operator (^) to calculate the sum without carry. This is equivalent to adding two numbers as if carry does not exist.
2. Use the AND operator (&) followed by a left shift (<<) to calculate the carry.
3. Repeat steps 1 and 2 until there is no carry left (b == 0).
4. Return the result, which will be stored in a.

Complexity

Time Complexity:

O(1) in the best case when there are no carry bits, but in general, it is O(log(max(a, b))) since each step reduces the number of bits involved in the calculation.

Space Complexity:

O(1), as we are using a constant amount of extra space.

Code

C++

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int tmp = (a & b) << 1; // carry calculation
            a = a ^ b; // sum without carry
            b = tmp; // carry shifted left
        }
        return a;
    }
};

Python

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MAX = 0x7FFFFFFF  # Maximum positive int (32-bit)
        MASK = 0xFFFFFFFF  # Mask to get last 32 bits
        
        while b != 0:
            tmp = (a & b) << 1  # carry calculation
            a = (a ^ b) & MASK  # sum without carry (limit to 32 bits)
            b = tmp & MASK  # carry shifted left (limit to 32 bits)
        
        # If a is greater than MAX, it's a negative number in 32-bit representation
        return a if a <= MAX else ~(a ^ MASK)

Java

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int tmp = (a & b) << 1; // carry calculation
            a = a ^ b; // sum without carry
            b = tmp; // carry shifted left
        }
        return a;
    }
}

JavaScript

var getSum = function(a, b) {
    while(b !=0)
    {
        let tmp = (a& b) <<1;
        a = a^b;
        b = tmp;
    }
    return a;

};