不用加减乘除做加法

思路

首先我们分析人们是如何进行十进制的加法的，比如是如何得出5+17=22的结果的？

实际上可以分三步进行：第一步只做各位相加不进位，此时相加的结果是12，第二步做进位，5+7中有进位，进位的值为10；第三步，把前面的两个结果加起来12+10的结果是22，刚好5+17=22。

求两个数之和，四则运算都不能用还能用什么？对数字做运算，除了四则运算之外，也就只剩下位运算了。位运算是针对二进制的，我们就以二进制再来分析一下前面的三步走的策略对二进制是不是也适用？

5的二进制是101，17的二进制是10001，还是试着把计算分成三步：

• 第一步各位相加但不计进位，得到的结果是10100；
• 第二步记下进位。在这个例子中只在最后一位相加时产生进位，结果是二进制的10；
• 第三步把前两步的结果相加，得到的结果是10110，转换成十进制刚好是22，由此可见三步走的策略对二进制也是适用的。

接下来把二进制的加法用位运算来替换：

• 第一步不考虑进位对每一位相加。0+0，1+1的结果都是0，1+0的结果是1，0+1的结果是1，我们注意到这和异或的结果是一样的。这一步可以用m^n实现。

• 第二步加上进位，进位如何来，用m&n可以得到m和n中都为1的bit位，而不全为1的位则全部变为了0，该位相加会发生进位，使得左边一位加1，因此(m&n)<<1可得到进位后要加的1的位置；

• 第三步将前面两步的结果相加，这里相加同样还是用异或运算来实现。相加的时候还有可能再产生进位，因此二者相加的过程可以再次重复循环步骤1和2，直到(m&n)<<1 == 0，这时候不会再产生进位，退出循环即可。

package com.zhumq.leetcode;

import org.junit.Test;

public class AddNumByBit {
    public int addNumByBit(int m,int n) {
        //不含进位的和
        int sum;
        //进位
        int add1;
        while(n!=0) {
            sum = m^n;
            add1 = (m&n)<<1;
            m = sum;
            n = add1;
        }
        return m;
    }
    @Test
    public void test1() {
        System.out.println(addNumByBit(19, 30));
    }
}