Leetcode 371 - Sum of Two Integers

Table of contents

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

Explanation/Approach

To solve this problem without using + and - operators, we utilize bit manipulation. The key idea is to simulate the addition process using bitwise operations:

1. Bitwise XOR (^) Operation: This operation is used to add two numbers without carrying. For example, in binary 1 ^ 1 = 0 and 1 ^ 0 = 1. It effectively adds the bits where only one of the bits is 1.

2. Bitwise AND (&) Operation: This operation is used to find the carry. For example, 1 & 1 = 1 (carry is 1). The carry needs to be left-shifted by one, as in binary addition, a carry moves one position to the left.

3. Loop until Carry is Zero: Repeat the process until there is no carry.

Solution: Bit Manipulation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32-bit mask in hexadecimal
        mask = 0xFFFFFFFF

        # Iterate till there is no carry
        while b != 0:
            # `a` is the partially added value, `b` is the carry left-shifted by 1
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask

        # For negative numbers, convert `a` to a negative number
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Time and Memory Complexity

The time complexity is O(1), as the number of iterations is constant due to the fixed-size integer in Python (32 bits for this problem). The space complexity is O(1) since no additional space is used.

Explanation

The solution repeatedly applies bitwise XOR to sum bits and bitwise AND followed by left shift to calculate the carry, until there is no carry left. The mask 0xFFFFFFFF is used to keep the integers within 32 bits (as Python integers can have more than 32 bits). For negative numbers, the complement of the result is taken to convert the result back to a negative number.

Visual Representation

Consider the example with a = 2 and b = 3:

Initial values: a = 0010, b = 0011
Iteration 1:
   Sum without carry: a ^ b = 0001
   Carry: (a & b) << 1 = 0100
   a = 0001, b = 0100

Iteration 2:
   Sum without carry: a ^ b = 0101
   Carry: (a & b) << 1 = 0000
   a = 0101, b = 0000

No more carry, so the result is a = 5 (0101 in binary).