371. Sum of Two Integers

Problem

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

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

Example 2:

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

Problem Summary

Calculate the sum of two integers ​​​​​​​a and b without using the operators + and -.

Solution Approach

• The requirement is to calculate a+b without using the addition and subtraction operators. This problem requires using the properties of the ^ and & operators. The ^ of two numbers can implement binary addition of two numbers without carry. Since addition needs to be implemented here, carry is definitely needed. So how to find the carry is the key to this problem.
• In binary, only 1 and 1 added together will produce a carry. 0 and 0, 0 and 1, and 1 and 0 will not produce a carry. The rule is that when a & b is 0, no carry is needed; when it is 1, it means a carry is needed. The carry moves forward by one bit, so a left shift operation is also needed. Therefore, the carry to be added is (a&b)<<1.

Code

package leetcode

func getSum(a int, b int) int {
	if a == 0 {
		return b
	}
	if b == 0 {
		return a
	}
	// (a & b)<<1 calculates the carry
	// a ^ b calculates addition without carry
	return getSum((a&b)<<1, a^b)
}