位运算---LC371两整数之和

一、题目链接

371. 两整数之和 - 力扣（LeetCode）

二、题目要求

给你两个整数a和b，不使用运算符+和-，计算并返回两整数之和。

示例 1：

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

示例 2：

输入：a = 2, b = 3输出：5

三、解决

思路分析：这道题要求我们求两数之和，但是又不允许使用+-运算符，所以我们可以使用位运算来解决这道问题；本体需要使用的是异或和与位运算，在位运算中存在这样两个结论：①异或的结果是无进位相加的结果 ②相与的结果是各位的进位；只需要将两个数异或的结果与相与的结果向左移一位再相加就是最终结果，但是本体又不允许使用加减运算符，而上述的两个步骤就等同于相加，所以我们只需要循环重复这两个步骤，知道进位为零就可以了。

算法原理

①异或结果为无进位相加

任何数字都可以转成二进制，在二进制中如果两个数不相同异或结果就是1，相同就是0，相同的结果有两种“00”、“11”，“00”相加结果就是0，而11相加结果是进位1，所以该位还是0；两个不同的数字“01”，异或后=1，相加也为1，所以该位就是1；由上可知异或的结果就是无进位相加的结果。

②相与的结果就是该位的进位数

这点很简单，如果两位都为1，那么两位相加就要进1，而相与后结果就是1；如果两位中有一个为0，相加后都不需要进位，与相与结果都为0；所以说相与的结果就是该位的进位数。

注意：求出相与的结果后需要向左移一位再与相异的结果相加，因为相与的结果是该位的进位，还没进呢，向左移一位就是进了。

代码展示

int getSum(int a, int b) { while(b) { int x = a ^ b; int carry = (a & b) << 1; a = x; b = carry; } return a; }