# Question

Formatted question description: https://leetcode.ca/all/371.html

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

# Algorithm

Bit Manipulation, when doing addition operation, after each bit is added, there may be a Carry generated, and then the next bit calculation needs to be added to the calculation together, then can the two parts be separated, let’s look at an example 759+ 674

1. If you do not consider the carry, you can get 323
2. If you only consider the carry, you can get 1110
3. Put the above two numbers holiday 323+1110=1433 is the final result

Then further analysis, if you get the first and second cases above, looking at it in binary,

• Do not consider the addition of carry, 0+0=0, 0+1=1, 1+0=1, 1+1=0, this is the operation rule of XOR,
• If you only consider the addition of carry 0+0=0, 0+1=0, 1+0=0, 1+1=1, this is actually the operation of and,
• In the third step, when the two are added, the algorithm is called recursively, and the termination condition is that when the carry is 0, the result of the first step is directly returned.

# Code

• 
public class Sum_of_Two_Integers {

public static void main(String[] args) {

Sum_of_Two_Integers out = new Sum_of_Two_Integers();
//        System.out.println(out.getSum(1, 2)); // no carry

// 2+2
// recurion-1: sum=0, carry= (10)左移1位 =(100)=4
// recursion-2: a=0,b=4
// recursion-3: b=0
System.out.println(out.getSum(2, 2)); // with carry
}

public int getSum(int a, int b) {
if(b == 0){ // complete the operation when there is no carry
return a;
}

int sum, carry;
sum = a^b; // step-1 sum
carry = (a&b)<<1; // step-2 sum

return getSum(sum, carry);
}
}

############

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

• // OJ: https://leetcode.com/problems/sum-of-two-integers/
// Time: O(1)
// Space: O(1)
class Solution {
public:
int getSum(int a, int b) {
int carry = 0, ans = 0;
for (int i = 0; i < 32; ++i) {
int x = (a >> i & 1), y = (b >> i & 1);
if (carry) {
if (x == y) {
ans |= 1 << i;
if (!x & !y) carry = 0;
}
} else {
if (x != y) ans |= 1 << i;
if (x & y) carry = 1;
}
}
return ans;
}
};

• '''
0x80000000
Taking the binary of 0x80000000 we get:
1000 0000 0000 0000 0000 0000 0000 0000

equivalent decimal value is 2,147,483,648(1's complement conversion)
https://stackoverflow.com/questions/18813875/how-is-0x80000000-equated-to-2147483648-in-java

0xffffffff
Taking the binary of 0xffffffff we get:
1111 1111 1111 1111 1111 1111 1111 1111

No sign bit in python
0xFFFFFFFF masking to detect int32 overflow

x & 0xFFFFFFFF == x
===> will return True if x doesn't oveflow and x is larger than 0.

>>> bin(0x80000000)
'0b10000000000000000000000000000000'
>>> bin(0xffffffff)
'0b11111111111111111111111111111111'

>>> 0x80000000 & 0xffffffff
2147483648
>>> 0x80000000 ^ 0xffffffff
2147483647
'''

'''
>>> 1^1
0
>>> 0^0
0
>>> 1^0
1
>>> 0^1
1
'''

class Solution:
def getSum(self, a: int, b: int) -> int:
kMax = 0x80000000
# the result of each step is passed recursively to the getSum function
# until there is no carry (b == 0)
# at that point, the function returns the final sum.
while b:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask

return a if a < kMax else ~(a ^ mask)

class Solution: # no mast, no overflow consideration
def getSum(a: int, b: int) -> int:
if b == 0:
return a

sum = a ^ b  # Step 1: sum without carry
carry = (a & b) << 1  # Step 2: calculate carry

return getSum(sum, carry)

############

class Solution(object):
def getSum(self, num1, num2):
"""
:type a: int
:type b: int
:rtype: int
"""
ans = 0
carry = 0
for i in range(0, 32):
c = carry
carry = 0
if a ^ b != 0:
if c == 1:
carry = 1
else:
else:
if a & mask > 0:
carry = 1
if c == 1:

if ans > 0x7fffffff:
return ans - 0xffffffff - 1
return ans


• func getSum(a int, b int) int {
for b != 0 {
s := a ^ b
b = (a & b) << 1
a = s
}
return a
}