0371._sum_of_two_integers.md

371. Sum of Two Integers

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/sum-of-two-integers/

内容描述

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

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

参考Simple explanation on how to arrive at the solution

首先来看一个例子: 2+3

  2: 0  1  0
  3: 0  1  1

2+3: 0(1)0 1

其中括号里面的1表示进位

我们抛开进位来说，在同一个bit上，如果都是1或者都是0那么最后相加的结果这一个bit肯定会变成0，否则就是1，这种变换方式就是异或(^)呀
即除了括号以外的001其实可以通过2 xor 3得到

接下来，我们考虑进位，这里我们在第二位进位了，其实这一位要加到左边那一位去，那么我们如何确定哪一位需要进位呢？我们发现，在同一个bit上，只有双方都是1才会进位，这种方式就是与(&)呀。但是要注意，当与操作完成之后，一个bit为1代表这一位其实是要加到左边那一位上的，所以我们要将结果向左移一位


     2^3: 0  0  1
     2&3: 0  1  0
2&3 << 1: 1  0  0

此时将我们的2^3 与(2&3 << 1) 做异或即为结果

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

但是java直接翻译成python却会在a和b中有负数时 tle,

class Solution:
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        while b != 0:
            tmp = a
            a = a ^ b
            b = (tmp & b) << 1
        return a

这是为什么呢？

因为python会自动转long类型

用python，从这一次往下会继续*2

但是Java就直接结束了

所以用python的话可以借助模运算来帮助结束

class Solution:
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b != 0:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

顺便看到一个comment解释了为什么b最终一定会变成0

a supplement：
A simple explanation on why b will eventually become zero:
Suppose in the first iteration a&b = 1011 0101 , pay attention to all the zero bits.
(1) the operation a&b << 1 will introduce an 0-bit and has the ability to reduce a head 1-bit. For example 1011 0101=> 0011 1010, the first 1-bit is removed and a brand new 0-bit is introduced at the end.
Thus, after assign a&b<<1 to b, b has less 1-bit and more 0-bit than a&b .
(2) Continue iterating, the operation a & b preserves all the 0-bit in b no matter what a· is, as 0&(.) = 0.

Thus, combining (1) and (2), b will hold less and less 1-bit during the iteration, and eventually become zero.