不用加减乘除做加法

题意

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

样例

对于 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() 方法,可以进行加法运算。

代码实现

位运算

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
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();
}
}

原题地址

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

坚持原创技术分享,您的支持将鼓励我继续创作!