29. Divide Two Integers

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
        
        sign = (dividend < 0) is (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)

        res = 0
        while dividend >= divisor:
            count = 1
            multiply = divisor
            while (multiply << 1) <= dividend:
                count <<= 1
                multiply <<= 1
            dividend -= multiply
            res += count
        
        if not sign:
            return -res
        return res

Notes 2020:

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return 0
        
        positive = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        
        def helper(divid, divis):
            if divid == 0 or divid < divis:
                return 0
            
            accu = divis
            count = 1
            while accu + accu <= divid:
                accu += accu
                count += count

            return count + helper(divid-accu, divis)
        
        res = helper(dividend, divisor)
        
        if not positive:
            res = -res
        
        return min(res, 2**31 - 1)

======================================================================

use long to handle overflow from multipication

int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) {
            return INT_MAX;
        }
        
        int sign = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ? -1 : 1;
        long dvd = labs(dividend);
        long dvs = labs(divisor);
        
        int res = 0;
        while (dvs <= dvd) {
            int mul = 1;
            while ((dvs << 1) <= dvd) {
                dvs <<= 1;
                mul <<= 1;
            }
            res += mul;
            
            dvd -= dvs;
            dvs = labs(divisor);
        }
        return res * sign;
    }

java:

double abs(double d)
float abs(float f)
int abs(int i)
long abs(long lng)

public int divide(int dividend, int divisor) {
        int flag = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            flag = -1;
        }
        long dividend1 = Math.abs((long) dividend); // output type is determined by input type
        long divisor1 = Math.abs((long) divisor);
        
        long res = 0;
        while (divisor1 <= dividend1) {
            long accu = divisor1;
            long mul = 1;
            while ((accu << 1) <= dividend1) {
                accu <<= 1;
                mul <<= 1;
            }
            dividend1 -= accu;
            res += mul;
        }
        
        res = flag * res;
        return res <= (long) Integer.MAX_VALUE && res >= (long) Integer.MIN_VALUE ? (int) res : Integer.MAX_VALUE;
    }

29. Divide Two Integers - cocoder39/coco39_LC GitHub Wiki