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

If you do not consider the carry, you can get 323
If you only consider the carry, you can get 1110
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.

https://stackoverflow.com/questions/36819849/detect-int32-overflow-using-0xffffffff-masking-in-python



>>> 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:
    mask = 0xFFFFFFFF
    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
    mask = 0x01
    carry = 0
    for i in range(0, 32):
      a = num1 & mask
      b = num2 & mask
      c = carry
      carry = 0
      if a ^ b != 0:
        if c == 1:
          carry = 1
        else:
          ans |= mask
      else:
        if a & mask > 0:
          carry = 1
        if c == 1:
          ans |= mask

      mask = mask << 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
}

371 - Sum of Two Integers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions