剑指Offer-面试题65-不用加减乘除做加法

2020-05-08

题目描述

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

示例:

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

提示：

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

思路

使用位运算实现加法
设两个数字的二进制形式a，b，求和s = a + b，a(i)代表a的二进制第i位，则分一下四种情况：
|a(i)|b(i)|无进位和n(i)|进位c(i+1)|
|-|-|-|-|
|0|0|0|0|
|0|1|1|0|
|1|0|1|0|
|1|1|0|1|
通过观察，无进位和与异或运算规律相同，进位和与运算规律相同（且需左移一位），因此得到无进位和n与进位c的计算公式：

1 2	n = a ^ b 非进位和：异或 c = a & b << 1 进位：与运算 + 左移一位

（和s）=（非进位和n）+（进位c）。即可将s = a + b转化为：
s = a + b => s = n + c
循环求n和c，直至进位c = 0；此时s = n，返回n即可。

代码

class Solution {
    public int add(int a, int b) {
        int tempSum = 0;    //无进位和
        int carrySum = 0;   //进位和
        while(b != 0){  //当进位!=0
            tempSum = a ^ b;    //异或求无进位和
            carrySum = (a & b) << 1;    //&+左移一位求进位和
            a = tempSum;
            b = carrySum;
        }
        return a;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。