LeetCode-29:不使用乘法、除法和 mod 运算符如何求解两数之商,真实面试中遇到过

这个题目在今年初,我的一个同事去面试的时候遇到过,回来一直给我吐槽,我又不是面试的算法工程师,问的些啥问题呀?哈哈~
我相信很多人,如果没有经常学习的话,多半也会一脸懵逼,我也是其中一个:)。虽然这些问题在实际工作用能用上的机会很少,但是对于我们拓展思维,以及了解语言底层的一些逻辑运算,还是非常有帮助的。

题目描述:

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数
dividend 除以除数 divisor 得到的商。

说明:

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

举个实际例子,57/4,实际需要的商为14,余数为1。
一个比较容易想到的办法是直接用减法,使用57-4=53,而53>4;再用53-4=49一次类推,直到减出来的差值<4,而此时做减法的次数,就是我们需要的商值。这个办法很实在,最大的问题就在于效率。57这个数比较很小,如果是999999/4呢,哪这个循环次数或者递归次数就比较难受了。

参考网上大神的解法,采用位运算。
这种运算方式在我们实际开发中用的比较少,所以也不太容易想得到,但是提起来,就是,哦哦哦哦哦,我知道我知道。。。
先来看一下代码:

package com.leetcode.learning;

public class _0029Division {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean negative;
      //用异或来计算是否符号相异
        negative = (dividend ^ divisor) <0;
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        for (int i=31; i>=0;i--) {
        	//找出足够大的数2^n*divisor
            if ((t>>i)>=d) {
            	//将结果加上2^n
                result+=1<<i;
              //将被除数减去2^n*divisor
                t-=d<<i;
            }
        }
        //符号相异取反
        return negative ? -result : result;
    }
}

比较难理解的部分其实在于循环体内部,我们还是以57/4为例好了。
先将被除数做一个位运算,右移的位数从31循环到0,57>>31剩下的就只有一串0了,肯定比除数还小,不行不行,继续循环,让右移的位数减少,直到数字3出现,57>>3=7,7>=4符合要求;然后被除数替换为57-4 * 23=25,除数不变,还是4,结果从0变成23=8;再继续25>>2=6,6>=4符合要求;继续将被除数替换为25 - 4 * 22= 9,除数不变,还是4,结果从8变成8+22=12;再继续9>>1=4,4>=4符合要求;被除数替换为9 - 4 * 21=1,除数不变,还是4,结果从12变成12+21=14;再循环1>>0=1 ,1>=0不符合要求
所以最终商为14。
会不会觉得直接从代码的运算逻辑去思考,还是觉得有些不理解?
试着从商的角度去理解,被除数,除数,余数,商,任何一个商值都可以有限不重复的2n值相加来表示,比如上面的14,可以表示为2+4+8=21 + 22 + 23 = 14;换个100/3的例子,商为33,余数为1,商其实可以表示为1+32=21 + 25 =33,if判断语句中,(t>>i)>=d其实就是判断的就是该被除数是不是含有除数多个2i ,如果有,则结果累加2i,被除数也需要减去这一坨;如果没有,则判断有没有更小的2i,依次类推,知道循环到1为止。

上一篇:常用的Linux指令总结(共57个)


下一篇:python拓展知识与了解