不用加减乘除做加法

题意

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

样例

对于 num1 = 15， num2 = 17，返回 32。

思路

位运算

首先先来看下十进制是如何计算的：

1. 相加各位的值，不进位，结果是 22, （5 + 7 = 12，舍弃进位就是2, 1 + 1 = 2 没有进位就是 22）
2. 计算进位值，得到 10。
3. 然后将上述两步得到的值重复步骤 1 和 2 。直到进位置为 0，返回不进位的值即可。

那么对于二进制也可以用这种方式计算：

1. 相加各位的值，不进位，15 (1111) + 17 (10001) = 11110，其实就是将不同的位保留，相同的位归0，那么这正是位运算中的异或运算的规则，所以 15 ^ 17 即可得到不进位的值。
2. 计算进位置其实就是将只保留相同的位，也就是 15 (1111) + 17 (10001) = 00001，既然是进位值，还应该左移一位，也就是 00010，这两个小操作对应的就是位运算中的 & 和 <<，即 (num1 & num2) << 1。
3. 然后将上述两步得到的值重复步骤 1 和 2 。直到进位置为 0，返回不进位的值即可。

BigInteger

Java 对于高精度运算有一个类是 BigInteger，其中有一个 add() 方法，可以进行加法运算。

代码实现

位运算

public class Solution {
    public int Add(int num1,int num2) {
        while (num2 != 0) {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
}

BigInteger

import java.math.BigInteger;
public class Solution {
    public int Add(int num1,int num2) {
        BigInteger b1 = new BigInteger(String.valueOf(num1));
        BigInteger b2 = new BigInteger(String.valueOf(num2));
        return b1.add(b2).intValue();
    }
}

原题地址

牛客网：不用加减乘除做加法