An simple non-recursive Java solution, well commented


  • 0
    public int divide(int dividend, int divisor) {
            /* Corner case */
            if (divisor == 0) return Integer.MAX_VALUE;
    
            /* Determine signal */
            boolean sign0 = dividend >> 31 == 0 ? true : false;
            boolean sign1 = divisor >> 31 == 0 ? true : false;
            boolean isNeg = sign0 ^ sign1;
            long op1 = Math.abs((long) dividend), op2 = Math.abs((long) divisor);
    
            /* Prune */
            if (op1 < op2) return 0;
    
            /* Find the largest multiple ≤ dividend */
            long multiple = op2, count = 1;
            do {
                multiple += multiple;
                count += count;
            } while (multiple <= op1);
            multiple >>= 1; count >>= 1;
    
            /* Logarithmically subtract from dividend */
            long quotient = 0;
            while (count > 0) {
                if (op1 >= multiple) {
                    op1 -= multiple;
                    quotient += count;
                }
                multiple >>= 1; count >>= 1;
            }
    
            /* Handle overflow */
            int retval;
            if (quotient <= Integer.MAX_VALUE)
                retval = isNeg == true ? (int) -quotient : (int) quotient;
            else
                retval = isNeg == true ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            return retval;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.