Divide Two Integers

May 5, 2016


Divide Two Integers

题目描述

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

If it is overflow, return MAX_INT.

解法

代码如下:

public static int divide(int dividend, int divisor) {
    if(dividend == Integer.MIN_VALUE && divisor == -1)
        return Integer.MAX_VALUE;
    if(divisor == 0)
        return Integer.MAX_VALUE;
    int sign = (dividend > 0 ^ divisor > 0) ? -1 : 1;
    long dvd = dividend < 0 ? -(long)dividend : dividend;
    long dvs = divisor < 0 ? -(long)(divisor) : divisor;
    int res = 0;
    while(dvd >= dvs) {
        long temp = dvs, multiple = 1;
        while(dvd >= (temp<<1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        dvd -= temp;
        res += multiple;
    }
    return sign * res;
}

思考过程: 算法参考自这里

具体例子直接参考上面的链接。

主要思想是借助位移运算来实现计数。

时空复杂度: 时间复杂度是O(不确定), 空间复杂度是O(不确定)


上一篇博客:Vim学习笔记
下一篇博客:First Missing Positive