29. Divide Two Numbers

Hits: 0

Given two integers, the dividend dividend and the divisor divisor. Dividing two numbers requires no multiplication, division and mod [operators] .

Returns the quotient of dividing the dividend divided by the divisor.

The result of integer division should truncate its fractional part, for example: truncate(8.345) = 8 and truncate(-2.7335) = -2

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = truncate(3) = 3

hint:

Both dividend and divisor are 32-bit signed integers.
    The divisor is not 0.
    Suppose our environment can only store 32-bit signed integers whose values ​​are in the range [−231, 231 − 1]. In this problem, if the division result overflows, 231 − 1 is returned.

answer:

class  Solution {
     public  int  divide ( int dividend, int divisor ) {
         //Some special cases are directly preprocessed 
        if (dividend==Integer.MIN_VALUE){
             if (divisor== -1 ) return Integer.MAX_VALUE;

            if(divisor==1) return Integer.MIN_VALUE;
        }


        if(divisor==Integer.MIN_VALUE){
            return dividend==Integer.MIN_VALUE?1:0;
        }

        if(divisor==0) return 0;

        boolean navigate= false ;
         //int range -2^31~2^31-1 The divisor and dividend may have different signs, so the best way is to unify sign processing 
        //but the minimum value of negative int is -2^31 to Positive numbers overflow, so use negative numbers to process 
        if (dividend> 0 ){
            dividend=-dividend;
            navigate=!navigate;
        }

        if(divisor>0){
            divisor=-divisor;
            navigate=!navigate;
        }

        int left=1,right=Integer.MAX_VALUE,ans=0;

        while (left<=right){
             int mid=((right-left)>> 1 )+left; //>> priority not + high
            boolean check=fastMulti(dividend,divisor,mid);

            if(check){
                ans=mid;
                //left may overflow 
                if (mid==Integer.MAX_VALUE) break ;

                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return navigate?-ans:ans;
    }
    //x quotient y divisor z quotient 
    public boolean fastMulti ( int x, int y, int z ) {
         //Since multiplication needs to be converted into addition problem quotient is equivalent to the number of times the dividend needs to be added 
        //xy are all negative numbers, 
        // x<<1 x is shifted left by one z>>1 z is shifted right by one, so that the total number of times will not change, so it will eventually achieve the effect of adding z times 
        //even right shifts will not lose numbers, but odd right shifts will lose numbers So for odd numbers, we need to deal with them separately 
        int  add =y;
         int result= 0 ;
         while (z!= 0 ){
             //z&1 is 0, indicating that the last digit in binary is 1, which is odd, otherwise it is even 
            if ((z& 1 )! = 0 ){
                 //The number lost by an odd right shift is not the last digit in decimal is 1. That is to say, you only need to add add once. 
                //xy are all negative numbers result+add>x
                if(result<x-add){
                   return false;
                }

                result+=add;
            }

            if (z!= 1 ){
                 //Since xy are all negative numbers, it is already less than x before the operation is completed, indicating that the quotient z is too large 
                if ( add <x- add ){
                    return  false ;
                }

                add<<=1;
            }

            z>>=1;
        }

        return true;
    }
}

You may also like...

Leave a Reply

Your email address will not be published.