- `-1000 <= a, b <= 1000`

class Solution {
public:
    int getSum(int a, int b) {
        if(b==0)
            return a;
        else
            return getSum(a^b,(a&b)<<1);
    }
};

| Algorithm        | Time Complexity | Space Complexity |
| ---------------- | --------------- | ---------------- |
| Bit Manipulation | O(1)            | O(1)             |

- How can we add two numbers in binary form?
- To add two bits we can use XOR operation.
- This will handle the case where there is no carry being generated

  - Example: 2+1
  - 2 -> 10
  - 1 -> 01
  - 2^1 -> 11

- To handle the carry we can use AND operation.
  - Example: 3+2
  - 3-> 011
  - 2-> 010
  - 3^2 = 001 here carry goes missing hence we need to use and operator and shift it by 1
  - (3&2)<<1 = 100
  - so 3+2 = (3&2)<<1 ^ 3^2 = 100 ^ 001 = 101 = 5

We need to do this until there is no carry left.

- If `b` is 0 then return `a`
- Else return the sum of `a^b` and `(a&b)<<1`

class Solution {
    public int getSum(int a, int b) {
        int ans=0;
        int carry=0;
        while(b!=0){
            ans = a^b;
            carry = (a&b)<<1;
            a=ans;
            b=carry;
        }
        return a;
    }
}