剑指 Offer 65：不用加减乘除做加法
题目
题目链接
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
解题
方法一：位运算
参考链接
由于这种解法对于负数也是可以的，负数是通过补码实现的，正数通过原码。
补充：
如果为8位整型,
+5的二进制 原码 0000 0101 (正数实现)
-5的二进制 原码 1000 0101
-5的二进制 反码 1111 1010 (除符号位，对原码取反)
-5的二进制 补码 1111 1011 (负数实现）
可以验证 ~5+1 结果就是-5
+0表示 0000 0000
-1 表示 1111 1111
比如-2+3
-2 的二进制 1111 1110
3 的二进制 0000 0011
通过相加，得到的二进制为 0000 0001 也就是1。
迭代
class Solution {
public:
int add(int a, int b) {
//后续每次循环将 非进位a与进位b，继续相加，直到无进位为止。
while(b!=0){
int c=static_cast<uint32_t>(a&b)<<1; //进位
a^=b; //非进位
b=c;
}
return a;
}
};
递归
class Solution {
public:
int add(int a, int b) {
if (b == 0) { // b=0也就是进位c=0，因此结果为非进位和n,也就是a
return a;
}
return add(a ^ b, static_cast<unsigned int>(a & b) << 1); // n=a^b，c= (a & b) << 1; 将a=n，b=c 继续递归 （注: leetcode不支持负值左移，需要强制转换(a&b)为无符号数）
}
};