Question

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

 371	Sum of Two Integers

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

 Example:
 Given a = 1 and b = 2, return 3.

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

Java

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);//
    }
}

// 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;
    }
};

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

371 - Sum of Two Integers

Question

Algorithm

Code

All Problems

All Solutions