LeetCode每日一题 之 不用加减乘除做加法
2020-04-21 本文已影响0人
ZSACH
image
题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。题目地址
我感觉可以自己先做做,你说呢!!!!!!
解题思路
如果不用加减乘除,我们还能用什么运算符呢,也就只剩位运算符&、|、^等,还有位移运算符<<、<<<等。我们怎么使用这些运算符代替四则运算呢??
我看看下十进制是怎么计算的:6+8,先算不进位结果为4,需要进一位结果为10,再算4+10,重复上一步,不进位结果14,进位结果0。最终得到14。
我们只要找到在二进制怎么算各位相加,怎么判断进位即可。
二进制相加:0加1得到1,1和1进位得到0,0和0得到0。显然这和异或^的结果是一样的。
各位相加的操作符已经找到了,怎么判断进位呢?
二进制进位:0和0进位0,1和1进位1,0和1进位0,显然这和与&是一样的。
得到了进位,如果还是保持在原位上肯定是错误的,类似10进制,进一位乘10,二进制乘2即可,什么?不让使用乘,我们就用位移运算把,左移一位就是乘2。
现在在二进制中,相关的工具都已经找到,我们类比十进制的运算规律类比即可。
得到解题的办法
代码
public int add(int num1,int num2){
while(num2!=0){
//通过异或,算出不需要进位下的各位之和,类比6+8的个位结果4
int a = num1^num2;
//进位数值,为0则不需要进位,类比6+8进一位结果10
num2 = (num1&num2) << 1;
//重复计算,直到不需要进位,类比6+8中,重复计算的4+10
num1 = a;
}
return num1;
}