【算法】位运算算法——两整数之和
题解：两整数之和(位运算算法)
目录
- 1.题目
- 2.位运算算法
- 3.参考代码
- 4.总结
1.题目
题目链接：LINK
2.位运算算法
这个题目难点就在于不能用+、-
那什么能够代替加号呢？
既然数的层面不能用+号，那二进制的角度去用+号即可。
恰好，就有两个这种运算符恰好满足我们的需求。
按位异或，对不存在进位的数字进行相加。
按位与，对需要进位的数字取1
当我们对a^b进行异或的时候，
我们发现：
如果1和0不同的位数异或是我们想要的结果，但两个二进制都是1的时候进行异或就不对(红色代表不满足我们预期，绿色代表满足我们预期)
结论：错误的都是需要进位的二进制
那如何进行进位呢？
怎么确定哪几个二进制位需要进位？ ——按位与
按位与恰好可以解决我们这个问题，两个1的二进制位肯定是需要进位的啊(黄色代表需要进位的地方)。
那如何把这个黄色的位进到a^b上去呢？
我们可以把a&b向左移动一位，表示向其更高位进行进位。
然后我们再对a^b 和 (a&b)>>1再进行异或运算，看看能不能进上一位。
我们发现好像有个1进位成功，还一个没能成功，但是没关系，继续以此循环即可。
总过程如下：
3.参考代码
//一般版本
class Solution {
public:int getSum(int a, int b) {int Carry = 1;while(Carry){int add = a ^ b;Carry = (a & b) << 1;a = add;b = Carry;}return a; }
};
//语法优化
class Solution {
public:int getSum(int a, int b) {do{a = a ^ b;b = (((a^b) & b) << 1);}while(b);return a; }
};
4.总结
我们本道题首先题目规定不能用+号，所以我们想到直接去二进制层面进行操作，用^代替无进位相加，用&代替进位，两者结合即可模拟出二进制层面加法的操作。
EOF