LC371 - Sum of Two Integers

Problem

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

Example

Input: a = 1, b = 2

Output: 3

Solution

Pseudocode

Time and space complexity is $O(1)$.

def getSum(self, a: int, b: int) -> int:
	while b != 0:
		tmp = (a & b) << 1
		a = a ^ b
		b = tmp
	return a

Python

Because Python integers are arbitrarily large, mask all except the rightmost 32 bits.

def getSum(self, a: int, b: int) -> int:
	mask = 0xffffffff
	while b != 0:
		tmp = (a & b) << 1
		a = (a ^ b) & mask
		b = tmp & mask

	if a > mask // 2:
		return ~(a^mask)
	return a