leetcode 371 两个整数之和

一、问题描述

二、解题思路

整体思路

本题需要借助位运算的方法来解决。

具体思路

两数异或运算的结果为无进位加法的结果，只需要用两数异或的结果加上进位(循环到进位为0)就可以得到两数之和。我们可以通过一个例子来模拟这个过程：

例如：a=13=01101B，b=28=11100B，a+b=41

先计算a^b，再计算进位(a&b)<<1，再更新a和b的值，直到b为0，即进位为0，此时的a即为结果，具体流程如图所示：

三、代码实现

时间复杂度：T(n)=O(1)

空间复杂度：S(n)=O(1)

class Solution {
public:int getSum(int a, int b) {while(b){//异或结果即为无进位加法结果int r=a^b;//计算进位b=(a&b)<<1;a=r;}return a;}
};