题目描述
给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符
思路
二进制的数字用0、1表示，两数相加即对应位0、1相加，其结果无非还是0、1
存在两种情况：进位、不进位
不进位：考虑用异或。异或运算又叫：不进位相加
进位：进位的bit位，即两数与的结果为1的位。进位需要将两数与的结果左移一位。
所以两数求和，演变成异或的结果和与运算移位后的结果继续求和，考虑递归。
递归终止条件自然是与的结果为0，那么最终结果就是异或的值。
代码
class Solution {
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
if(b == 0) {
return a;
}else {
return repeat(a, b);
}
}
private int repeat(int a, int b) {
int _a = a ^ b;
int _b = (a & b) << 1;
if(b != 0) {
return repeat(_a, _b);
}else {
return _a;
}
}
};
考差点
- 递归（递归的思想：参数不同，套路相同，终止条件，逐层返回）
- 位运算（两数异或：加法不进位）
