Leetcode 371 Sum of Two Integer

发表于 |

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.

分析：
摆明着要用位运算，那么很容易想到只有在这种情况下 101 ^ 010 = 111（即a&b=0），^操作符等价于+操作符
那么就把a拆开，分为 和b一样的部分和 以及 和b完全不一样的部分

思路：
用&操作符取出相同部分，而相同部分相加等价于左移操作符，用^直接把不同部分的结果加出来

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        return a if not b else self.getSum(a^b,(a&b)<<1)

# O(1) time O(1) space 
13 / 13 test cases passed.
difficulty: easy
Runtime: 30 ms