371. Sum of Two Integers

📝 Problem Details

• Title: 371. Sum of Two Integers
• Link: https://leetcode.com/problems/sum-of-two-integers/
• Difficulty: Medium
• Tags/Categories: Bit-Manipulation

input integers a and b return the sum of the two integers constraint: can’t use the operators + and -

💡 Explanation of Solution

Bit Manupulation:
1. Use XOR (^) to get the sum without carry
2. Use AND (&) followed by a left shift ( << ) to get the carry
3. Repeat the process until the carry is 0

⌛ Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int getSum(int a, int b) {
        while(b != 0) {
            unsigned carry = (unsigned)(a & b) << 1; // calculate carry
            a = a ^ b; // add without carry
            b = carry; // carry gets added in the next iteration
        }
        return a;
    }
};