29. 两数相除

小咪咪 2022-10-16 12:23 155阅读 0赞

>   
> 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
> 
> 返回被除数 dividend 除以除数 divisor 得到的商。
> 
> 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
> 
>  
> 
> 示例 1:
> 
> 输入: dividend = 10, divisor = 3  
> 输出: 3  
> 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3  
> 示例 2:
> 
> 输入: dividend = 7, divisor = -3  
> 输出: -2  
> 解释: 7/-3 = truncate(-2.33333..) = -2

class Solution {
        public int divide(int dividend, int divisor) {
            /**
            这个题可以使用快速乘法模板, 如果 一个数 * divisor <=dividend 取这个数的最大值即可
             */
            //判断两树相除是否是负数,如果是的话最后结果要*-1
                boolean isFu=false;
    
                //定义结果
                long res=0;
            if((dividend>0&&divisor<0)||(dividend<0&&divisor>0)){
                isFu=true;
            }
            //变成正数
           long  tempDividend=dividend,tempDivisor=divisor;
            if(tempDividend<0){
                 tempDividend=-tempDividend;  //如果不另起变量  -2147483648-> 2147483648 越int 界 所以我们用long接受
            }
            if(tempDivisor<0){
                tempDivisor=-tempDivisor;
            }
            //二分找这个数
            long left=0,right=tempDividend;
            while(left<right){
                long mid=(left+right+1)>>1;
             
                if(quickMulti(tempDivisor,mid)<=tempDividend){
    
                    left=mid;
                }else{
                    right=mid-1;
                }
            }
            //结果是否是负数
            res= isFu?-left:left;
            //是否大于整形的最大值
            if(res>Integer.MAX_VALUE||res<Integer.MIN_VALUE){
               res=Integer.MAX_VALUE;
            }
           
           
           return (int)res;
        }
        //快速乘法模板
        public long quickMulti(long a,long b){
            long sum=0;
            while(b>0){
                if((b&1)==1){
                    sum+=a;
                }
                b=b>>1;
                a+=a;
            }
            return sum;
        }
    }