剑指Offer_#65_不用加减乘除做加法

剑指offer

Contents

• • 题目
  • 思路分析
  • 解答
    • 复杂度分析

题目

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:
输入: a = 1, b = 1
输出: 2

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数

思路分析

又是一道脑筋急转弯的题目。不能用加减乘除运算，就只能用二进制位运算了。
思路是通过二进制位运算模拟十进制的加法，加法分为3步：
1. 对应位相加，得到非进位和

• 对于二进制数字来说，异或运算可以得到非进位和。
• 可以发现最后一位的进位我们没有计算进去，下一步我们考虑进位。

 10001(十进制的17)
+00101(十进制的5)
------
 10100

2. 计算进位结果，将需要进位的位置标记为1

• 两个二进制数字相加，何时产生进位？只有1和1相加会产生进位。我们联想到&运算，只有1和1相&结果是1。
• 又因为当前位进位是加到更高一位上面的，所以仅仅&运算还不够，还要将运算结果左移一位。

 10001
&00101
------
 00001 << 1 = 00010

3. 将非进位和与进位部分相加，得到最终结果

• 可以转换为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),只有常数个辅助变量