371. 两整数之和

Difficulty
Medium
Tags
位运算
URL
https://leetcode-cn.com/problems/sum-of-two-integers/
Star
给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2
输出：3
示例 2：
输入：a = 2, b = 3
输出：5
提示：
  • 1000 <= a, b <= 1000

法 1位运算

思路
两个整数a, b;
a ^ b是无进位的相加；
a&b得到每一位的进位；
让无进位相加的结果与进位不断的异或， 直到进位为0；
题解
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = MAX_INT + 1
        while b != 0:
            # 计算进位
            carry = (a & b) << 1 
            # 取余范围限制在 [0, 2^32-1] 范围内
            a = (a ^ b) % MASK
            b = carry % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)
c++
public static int getSum(int a, int b) {
// a ^ b 找出需要进位的点
while ((a & b) != 0) {
    // 进位
    int t = (a & b) << 1;
    // 找出无需进位的点，相加
    b = a ^ b;
    a = t;
 }
return a ^ b;
}