美文网首页Android进阶之路Android开发经验谈Android开发
LeetCode每日一题 之 不用加减乘除做加法

LeetCode每日一题 之 不用加减乘除做加法

作者: ZSACH | 来源:发表于2020-04-21 13:12 被阅读0次
    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;
    }
    

    相关文章

      网友评论

        本文标题:LeetCode每日一题 之 不用加减乘除做加法

        本文链接:https://www.haomeiwen.com/subject/vtjuihtx.html