欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

不使用乘法、除法和mod,实现两数相除

程序员文章站 2023-11-17 08:39:58
保证数据在int范围。被除数÷除数=商+余数需要注意的问题:int 的范围是[-2^31,2^31-1],也就是【-2147483648,2147483647】,如果-2147483648/-1结果会超出int 范围。除法,乘法和mod都不能使用,那可以使用加减,移位。只需保留商即可解法一:每次自增除数当然被除数减去除数也可以。如 10/3,除数自增,10在【3+3+3,3+3+3+3】范围里面。如果被除数取得很大,除数取得很小,那么会很慢。(二者同号情况下)class Soluti...

被除数÷除数=商+余数
需要注意的问题:

  1. int 的范围是[-2^31,2^31-1],也就是【-2147483648,2147483647】,如果-2147483648/-1结果会超出int 范围。
  2. 除法,乘法和mod都不能使用,那可以使用加减,移位。
  3. 只需保留商即可
  4. 保证数据在int范围。

电脑做二进制除法的时候,是让被除数连续减去几次除数(减去n倍除数),直到差小于除数时为止,这样减去的次数就是商,剩下的差就是余数。
可以借鉴这个思想。

解法一:每次自增除数

当然被除数减去除数也可以。
如 10/3,除数自增,10在【3+3+3,3+3+3+3】范围里面。
如果被除数取得很大,除数取得很小,那么会很慢。(二者同号情况下)
下面代码有个错误,就是int会溢出。

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        if(dividend==Integer.MIN_VALUE&&divisor==-1){
            return Integer.MAX_VALUE;
        }
        int ans=1;//商
        int f=-1;//两个数是否异号
        if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
        if(f==-1){
        	//异号的话,全部变为正数。
            dividend=Math.abs(dividend);
            divisor=Math.abs(divisor);
        }
        int temp=0;
        int d=divisor;
        while(true){
            if(divisor==dividend) return f==-1?-ans:ans;
            if(divisor>dividend&&temp<dividend){
            	//找到结果
                ans--;
                return f==-1?-ans:ans;
            }
            temp=divisor;
            divisor+=d;
            ans++;
        }
    }
}

解法二

注意Math.abs()源码

public static int abs(int a) {
        return (a < 0) ? -a : a;
    }
****************************************
  public static long abs(long a) {
        return (a < 0) ? -a : a;
    }
    所以参数需要强转一下。

dividend/2^n来减少减法的次数。(加法和减法的原理一样)
dividend/2^n>=divisor的时候,说明dividend-divisor*2^n>=0
于是可以用dividend-=divisor*2^n来简化。
这样每次最多循环32次。

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
        int ans=0;
        int f=-1;
        if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
        long c_divisor=Math.abs((long)divisor);
        long c_dividend=Math.abs((long)dividend);
        for(int i=31;i>=0;i--){
            if((c_dividend>>i)>=c_divisor){
              ans+=(1<<i);
              c_dividend=c_dividend-(c_divisor<<i);
            }
        }
        return f*ans;
    }
}

那这个算法的正确性如何呢?
解法二和解法三一个是>>,一个是<<。
道理一样。

解法三

大致思路:每次让dividend=dividend-n*divisor(且每次的n取值尽可能大)
此题限制,我们可以用位移运算,此时的n一定是2的倍数。那么和解法二差不多。
所以首先让diviosor>dividend,然后开始计算。

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
        int ans=0;
        int f=-1;
        if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
        long c_divisor=Math.abs((long)divisor);
        long c_dividend=Math.abs((long)dividend);
        int count=0;
        while(c_divisor<=c_dividend){
       		//使c_divisor大于c_dividend
            count++;
            c_divisor=c_divisor<<1;//这里如果不使用log就会溢出。
        }
        while(count>0){
            count--;
            c_divisor=c_divisor>>1;
            if(c_divisor<=c_dividend){
                ans+=1<<count;
                c_dividend-=c_divisor;
            }
        }
        return f*ans;
    }
}

当然注意题目所说的数据都是int范围的,所以不用long

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
        int ans=0;
        int f=-1;
        if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
        if(dividend==Integer.MIN_VALUE) {
            if (divisor < 0) {
                dividend -= divisor;
                ans++;
            } else {
                dividend += divisor;
                ans++;
            }
            if(dividend==0) return ans*f;
        }else if(divisor==Integer.MIN_VALUE) return 0;
        int c_divisor=Math.abs(divisor);
        int c_dividend=Math.abs(dividend);
        for(int i=31;i>=0;i--){
            if((c_dividend>>i)>=c_divisor){
                ans+=(1<<i);
                //System.out.println(ans);
                c_dividend=c_dividend-(c_divisor<<i);
            }
        }
        return f*ans;
    }
}

本文地址:https://blog.csdn.net/qq_43179428/article/details/107035003