不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法

题目说明

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

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

示例

例1

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

笔者理解

此题是一道位运算问题。

解法

当笔者阅读完此题后，发现此题是一道经典的位运算题，不用运算符进行加法运算，我们可以通过异或和相与进位来计算，

例如：10011和10001，异或得到00010，相与进位得到100010，递归进行运算，得出结果。

让我们来看看具体如何实现的吧。

实现

public int add(int a, int b) {
        if(a==0){ return b;}
        if(b==0){ return a;}
        //如果a或者b为0，相加结果就是另一个树

        return add(a^b,(a&b)<<1);
        //a^b代表两个数二进制的相加（还没有计算进位），(a&b)<<1表示两个同位二进制相加产生的进位
    }