不用加法求两数之和

原创刘蕊架构师社区

大家好，我叫阿美

是一名帝都女算法工程师

大家好，我叫阿毛

是一名混日子的帝都男后端

阿毛，咱俩做同事那么久了，出个问题考考你呗，如果你能回答上来，给你一个请我吃饭的机会

阿美，好呀，好呀，什么问题？追了你那么久，都没答应跟我吃一顿饭，非常期待呦！

不用加法，求出两个整数之和

我想了半天，也没想出答案，不用加法还想求出两个数之后，你这是故意不给我机会请你吃饭呀

阿毛，这么简单的不用加法求和运算，你都回答不上来，平常的算法是怎么学的，就这还想追我！

阿美，其实，我挺努力的，不过我平常是做后端应用的，对算法认识不够深刻，要不，你教教我

好吧，阿毛，先给你讲讲或运算！

回想一下『或』这个词在数学里的意思——『一个元素在集合A或集合B里』意味着『它只在A里』、『它只在B里』、『它在A和B的交集里』这三种情况中的一种。

阿美，喔喔，我明白了，这就是或运算的逻辑图呀，红色区域就是代表了A||B，不过这和两个数相加有啥关系呢？

阿毛，上面给你讲了或运算，确实和两个数相加没有关系，只是为了给你讲异或运算，让你更明白！

『异或』不允许『共存』的情况，所以把A且B的那一部分除掉！

喔喔，阿美，这就是异或运算呀，我是不是可以这样理解，A和B相同的部分为假，所以去掉，A和B不同的部分为真，所以保留！

是呀，阿毛，异或运算的口诀就是，同为假，异为真！，所以0和1的异或运算如下：0^0 = 0，

1^0 = 1， 0^1 = 1，1^1 = 0

再看看0和1的二进制加法，

不考虑进位：1+1=0,

1+0=1，0+1=1,0+0=0，

阿毛，你看在不考虑进位的时候，加法可以用异或实现

哇，阿美，还真是这样呢，你不这样对比，我还真没发现加法和异或还有这样的关系

阿毛，现在要考虑有进位的情况啦~！还是先看加法吧：0+0进位是0,

1+0、0+1进位是0,1+1进位是1,

再看看与运算：0&0=0; 0&1=0; 1&0=0; 1&1=1;阿毛，你发现了么？在考虑进位运算时，加法和&运算类似呦

噗！我听你讲了异或运算^和与运算&，还没有听懂怎么不用加法，求出两个数之和呢？

阿毛，你怎么那么笨呀，

那么加法运算可以这样实现：

1）先不考虑进位，按位计算各位累加（用异或实现），得到a;

2）然后计算进位，并将进位的值左移，得到值b。若b为0，则a就是加法运算的结果；若b不为0，则a+b即得结果（递归调用这个过程）。实现算法如下：

public int bitAdd(int a,int b )
{
    if(b==0)
    {
        return a;
    }
    int sum=a^b;
    int carry=(a&b)<<1;
    return bitAdd(sum,carry);
}

1661166

哇！阿美，你不仅长的这么漂亮，还这么聪明呢，以前也学过位运算，但是还真没发现它和加法有这么神奇的关系呢！话说，还有机会请你吃饭么？

走，吃饭去！