Leetcode371

Leetcode371：两整数之和

题目描述

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

示例 1:

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

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

解法一：基于递归和二进制异或的方法

/****************************************************************************************
基于递归和二进制异或的方法
利用二进制位进行运算。分两步：

不考虑进位进行相加
加上进位，直到进位为0
sum = a ^ b，得到无进位和。
a & b，得到进位，因为是进位，所以左移一位进行相加。考虑到无符号溢出问题，所以转为无符号数。
注意：最小负数左移溢出，所以转为无符号数
*****************************************************************************************/
class Solution {
public:
    int getSum(int a, int b) {  //假设a=3,b=5
        int sum, c;
        sum = a ^ b;   //3^5=0000 0011 ^ 0000 0101 = 0000 0110
        c = ((unsigned int)(a & b)) << 1; //3&5=0000 0011 & 0000 0101 = 0000 0001  再左移一位为0000 0010
        if (c != 0) {
            return getSum(sum, c);
        }
        return sum;
    }
};

解法二：基于迭代和二进制异或的方法

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

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int a, b;
    cout << "请输入a,b的大小：" << endl;
    cin >> a >> b;
    Solution answer;
    cout << "两数的和为：" << answer.getSum(a, b) << endl;

    system("pause");
    return 0;
}