lc-29

//Given two integers dividend and divisor, divide two integers without using mul
//tiplication, division, and mod operator. 
//
// The integer division should truncate toward zero, which means losing its frac
//tional part. For example, 8.345 would be truncated to 8, and -2.7335 would be tr
//uncated to -2. 
//
// Return the quotient after dividing dividend by divisor. 
//
// Note: Assume we are dealing with an environment that could only store integer
//s within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if 
//the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the q
//uotient is strictly less than -231, then return -231. 
//
// 
// Example 1: 
//
// 
//Input: dividend = 10, divisor = 3
//Output: 3
//Explanation: 10/3 = 3.33333.. which is truncated to 3.
// 
//
// Example 2: 
//
// 
//Input: dividend = 7, divisor = -3
//Output: -2
//Explanation: 7/-3 = -2.33333.. which is truncated to -2.
// 
//
// 
// Constraints: 
//
// 
// -231 <= dividend, divisor <= 231 - 1 
// divisor != 0 
// 
// Related Topics Math Bit Manipulation 
// 👍 3208 👎 10948


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int divide(int dividend, int divisor) {
        boolean minus = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);

        if (divisor == 1) {
            return dividend;
        }

        long dividendLong = (long)dividend;
        long divisorLong = (long)divisor;


        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }


        if (dividend < 0) {
            dividendLong = -dividendLong;
        }

        if (divisor < 0) {
            divisorLong = -divisorLong;
        }

        long times = 1l;
        int result = 0;

        while (divisorLong < dividendLong && divisorLong < Integer.MAX_VALUE) {
            divisorLong = divisorLong << 1;
            times = times << 1;
        }

        if (divisorLong > dividendLong) {
            divisorLong = divisorLong >> 1;
            times = times >> 1;
        }

        while (times > 0) {
            if (dividendLong >= divisorLong) {
                dividendLong -= divisorLong;
                result+=times;
            }

            if (dividendLong < divisorLong) {
                divisorLong = divisorLong >> 1;
                times = times >> 1;
            }
        }
        if (minus) {
            return -result;
        } else {
            return result;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)