分析
参考计组学的加法器的原理, a + b 由 a + b 的不进位和和进位组成, 不进位和就是 a ^ b, 而 a & b 中为 1 的位置代表产生了进位,产生的进位到下一位,因此还要左移一位。
因此 add(a, b) = add(a ^ b, (a & b)<<1), 递归终点是第二个参数等于 0.
而 (a & b) << 1 每次一定会多产生一个 0, 最多 32 次第二个参数就会变成 0.
因此时间和空间都是 O(1)O(1)O(1)的。
代码
class Solution {
public:
int add(int num1, int num2){
if(num1 == 0)return num2;
if(num2 == 0)return num1;
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
return add(sum, carry);
}
};