剑指Offer_#65_不用加减乘除做加法
Contents
题目
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数
思路分析
又是一道脑筋急转弯的题目。不能用加减乘除运算，就只能用二进制位运算了。
思路是通过二进制位运算模拟十进制的加法，加法分为3步：
1. 对应位相加，得到非进位和
- 对于二进制数字来说，异或运算可以得到非进位和。
- 可以发现最后一位的进位我们没有计算进去，下一步我们考虑进位。
10001(十进制的17)
+00101(十进制的5)
------
101002. 计算进位结果，将需要进位的位置标记为1
- 两个二进制数字相加，何时产生进位？只有1和1相加会产生进位。我们联想到
&运算，只有1和1相&结果是1。 - 又因为当前位进位是加到更高一位上面的，所以仅仅
&运算还不够，还要将运算结果左移一位。
10001
&00101
------
00001 << 1 = 000103. 将非进位和与进位部分相加，得到最终结果
- 可以转换为10进制数字验证，相加结果是正确的。
10100
+00010
------
10110（十进制的22）解答
class Solution {
public int add(int a, int b) {
int sum;//非进位和
int carry;//进位部分
//b==0说明进位结束，这时的a就是最终结果
while(b != 0){
sum = a ^ b;//异或，结果是非进位和
carry = (a & b) << 1;//与运算后左移一位，结果是进位部分
a = sum;
b = carry;
}
return a;
}
}复杂度分析
时间复杂度：O(1),最多只需要进行32次循环（即每一位都要进位的情况）,是常数
空间复杂度：O(1),只有常数个辅助变量