leetcode 371. 两整数之和

╰半夏微凉° 2022-12-13 11:19 140阅读 0赞

[leetcode 371. 两整数之和][leetcode 371.]

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

输入: a = 1, b = 2
    输出: 3

示例 2:

输入: a = -2, b = 3
    输出: 1

### 递归解法 ###

*  a ^ b可以得到两数相加不进位的加法结果
 *  (a & b) << 1可以得到两数相加产生的进位

将不进位的加法结果与进位相加，即可得到两数相加的实际结果。需要注意的是：不进位加法结果与进位相加有可能再次造成进位，所以需要迭代处理，直到不再产生新的进位为止。

根据如上思路，可以比较容易地得到递归的解法

/*
    作者：hawjk
    链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/cliang-chong-jie-fa-tian-keng-wei-yun-suan-de-yue-/
    */
    int getSum(int a, int b) {
    	if (!(a & b)) return a ^ b;	// 当进位为0时，返回两数相加不进位的加法结果
        return getSum(a ^ b, ((unsigned int)(a & b)) << 1);	// 否则，递归计算不进位加法结果与进位
        之和
    }

### 非递归解法 ###

1.先做异或运算，结果为进位标志，在做与运算并左移1位，在将没有进位的结果与与运算的结果做异或运算得结果。

2.a为结果，b为进位结果，不断检查b是否为0判断是否还有进位。

class Solution {
    public:
        int getSum(int a, int b) {
    
            while(b){
                int temp = a ^ b;
                b = (unsigned int)((a & b)) << 1;
                a = temp;
            }
            return a;
        }
    };

### 一行代码解法 ###

class Solution {
    public:
        int getSum(int a, int b) {
        
            return !(a && b) ? a | b : getSum(a ^ b, (unsigned int)(a & b) << 1);
    
        }
    };

[leetcode 371.]: https://leetcode-cn.com/problems/sum-of-two-integers/