leetcode 29 Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目地址：leetcode Divide Two Integers

题目大意： 给两个数，要求实现除法运算，但是不能用乘法、除法和模运算。

思路

用除数每次*2（向左移动一位）去逼近被除数，被除数减去新的除数如此循环。

详见代码。

需要注意的是溢出需要返回int_max ，还有防止移位运算溢出需要用long long

C++

class Solution {
	long long bit_divide(long long &dividend, long long divisor) {
		long long res = 1;
		for (; (divisor << 1) <= dividend; res <<= 1, divisor <<= 1) ;
		dividend -= divisor;
		return res;
	}

public:
	int divide(int dividend, int divisor) {
		long long dividend_l = labs(dividend), divisor_l = labs(divisor);
		int flag = (dividend < 0) ^ (divisor < 0);
		long long ans = 0;
		while (divisor_l <= dividend_l) {
			ans += bit_divide(dividend_l, divisor_l);
			if (ans >= INT_MAX) {
				if (flag && -ans == INT_MIN) return INT_MIN;
				return INT_MAX;
			}
		}
		return flag? -ans : ans;
	}
};

Python

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        flag = (dividend < 0) ^ (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        ans = 0
        while divisor <= dividend:
            temp = 1
            div = divisor
            while (div << 1) <= dividend:
                div <<= 1
                temp <<= 1
            dividend -= div
            ans += temp
            if ans >= 0x7fffffff:
                if flag and ans == 0x80000000:
                    return -0x80000000
                return 0x7fffffff
        return ans if not flag else -ans

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/