371. Sum of Two Integers

Description of the Problem

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

Example 1:

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

Example 2:

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

Constraints:

• -1000 <= a, b <= 1000

Solution

Tags: Bit Manipulation

Explanation

The following code explains itself if you know how to perform addition of binary numbers by yourself.

Code (Rust)

impl Solution {
    pub fn get_sum(a: i32, b: i32) -> i32 {
        let mut a = a;
        let mut b = b;
        
        while(b != 0){
            let sum = a ^ b;
            let carry = a & b;
            a = sum;
            b = carry << 1;
        }

        return a;
    }
}

Complexity (m is the length of list1 and n is the length of list2)

Time complexity:

• \(O(1)\)
  • In lowest level the time is bound by a constant since the number of bits in an integer is constant

Auxiliary Space:

• \( O(1) \)