题目描述
写一个函数,求两个整数之和,要求在函数体内不得使用 +、-、×、÷ 四则运算符号。
样例
输入:num1 = 1 , num2 = 2
输出:3
算法1
(二进制) $O(1)$
不能用+-/* ,考虑用二进制:
(1) 二进制不进位的运算结果与 异或 运算结果相同
(2) 二进制进位的运算结果与各位 相与& 后左移一位的结果相同
比如A+B=CD,其中C为进位,我们有 D=A^B C=(A & B) << 1;
如果是多位,比如AB+CD=EFG 我们依然满足结果为 AB ^ CD + (AB & CD) << 1;
考虑不能用+, 故用循环处理.
由于进位的那个数每次左移一位,多出一个0,最后会变为0,故用其作循环条件
int 为32位,循环最多循环32位 复杂度$O(1)$
NOTE: 负数也使用,比如A-B, 会转化为 A + (-B) , 其中(-B)即是B的补码
C++ 代码
class Solution {
public:
int add(int num1, int num2){
while(num2){
int sum = num1 ^ num2; //异或
int carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
return num1;
}
};
C++ 代码2
class Solution {
public:
int add(int a, int b){
while(b)
{
int sum = a ^ b;
int carry = ((unsigned)(a & b) << 1);
a = sum;
b = carry;
}
return a;
}
};