【位运算】leetcode371：两整数之和

一.题目描述

两整数之和

二.思路分析

题目要求我们实现两整数相加，但是不能使用加号，应该立马想到是用位运算来解决问题。之前说过，异或就是“无进位相加”，故本题可以先将两数异或，然后想办法让得到的结果进位即可。

如何进位呢？我们知道，任意一个比特位相加只有3中情况：0+0,1+1,0+1，其中只有1+1时需要进位。而按位与的特点是有0则0，故我们可以用a&b，结果是1的比特位就是需要进位的。但进位是要进到它的下一位

故最终结果为(a ^ b) + ((a & b) << 1)。但题目禁止我们使用加号，怎么使这两部分相加呢？题目本身就让我们实现加法呀，重复以上的逻辑不就行了，所以这是一个循环的过程。循环什么时候结束呢？当不需要进位，即(a & b) << 1 == 0时就不需要加了，循环结束。

下面用13+28=41来举例

三.代码实现

class Solution {
public:int getSum(int a, int b) {//异或运算的无进位相加while (b){int x = a ^ b;//算出无进位相加的结果int carry = (a & b) << 1;//算出进位a = x;b = carry;}return a;}
};