首页 > 基础算法 > 模拟法 > LeetCode-Divide Two Integers[模拟]
2014
11-19

LeetCode-Divide Two Integers[模拟]

Divide Two Integers

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

标签: Math Binary Search
分析

不能用乘、除和取模,那剩下的,还有加、减和位运算。

最简单的方法,是不断减去被除数。在这个基础上,可以做一点优化,每次把被除数翻倍,从而加速。

代码1

// LeetCode, Divide Two Integers
// 时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
    int divide(int dividend, int divisor) {
        // 当 dividend = INT_MIN时,-dividend会溢出,所以用 long long
        long long a = dividend >= 0 ? dividend : -(long long)dividend;
        long long b = divisor >= 0 ? divisor : -(long long)divisor;

        // 当 dividend = INT_MIN时,divisor = -1时,结果会溢出,所以用 long long
        long long result = 0;
        while (a >= b) {
            long long c = b;
            for (int i = 0; a >= c; ++i, c <<= 1) {
                a -= c;
                result += 1 << i;
            }
        }

        return ((dividend^divisor) >> 31) ? (-result) : (result);
    }
};

代码2

// LeetCode, Divide Two Integers
// 时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
    int divide(int dividend, int divisor) {
        int result = 0; // 当 dividend = INT_MIN时,divisor = -1时,结果会溢出
        const bool sign = (dividend > 0 && divisor < 0) ||
                (dividend < 0 && divisor > 0); // 异号

        // 当 dividend = INT_MIN时,-dividend会溢出,所以用 unsigned int
        unsigned int a = dividend >= 0 ? dividend : -dividend;
        unsigned int b = divisor >= 0 ? divisor : -divisor;

        while (a >= b) {
            int multi = 1;
            unsigned int bb = b;
            while (a >= bb) {
                a -= bb;
                result += multi;

                if (bb < INT_MAX >> 1) { // 防止溢出
                    bb += bb;
                    multi += multi;
                }
            }
        }
        if (sign) return -result;
        else return result;
    }
};

Java代码:

public class Solution {
    	 public static int divide(int dividend, int divisor) {
		 return (int)divideL(dividend,divisor);
	 }
	 
	 public static long divideL(long dividend,long divisor){
		 if(divisor == 1) return dividend;
		 if(divisor < 0) return -divideL(dividend, -divisor);
		 if(dividend < 0) return -divideL(-dividend, divisor);
		 if(divisor > dividend) return 0;
		 if(divisor == 0) return Integer.MAX_VALUE;
		 long d = divisor;
		 long bitcnt = 1;
		 long ans = 0;
		 while(d < dividend ){
			 d <<= 1;
			 bitcnt <<= 1;
		 }
		 while(d >= divisor){
			 while(dividend >= d){
				 dividend -= d;
				 ans += bitcnt;
			 }
			 d >>= 1;
			 bitcnt >>= 1;
		 }
		 return ans;
	 }
}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。