数学

 

两个整数相除

两个整数相除

将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。

（一）利用减法。超时

public int divide(int divident, int divisor) {
    if(divident == 0){
        return 0;
    }
    if(divident == divisor){
        return 1;
    }

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

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

    int count = 0;
    int flag1 = 1;
    int flag2 = 1;

    if(divident < 0){
        flag1 = -1;
        divident = -divident;
    }

    if(divisor < 0){
        flag2 = -1;
        divisor = -divisor;
    }

    while (divident >= divisor){
        divident -= divisor;
        count += 1;
    }
    return count * flag1 * flag2;
}

（二）一次一次加会超时，改进：每次将被除数增加1倍，同时将count也增加一倍，如果超过了被除数，那么用被除数减去当前和再继续本操作。。。但这个也会超时

public int divide(int divident, int divisor) {
    if(divident == 0){
        return 0;
    }
    if(divident == divisor){
        return 1;
    }

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

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

    int count = 0;
    int flag1 = 1;
    int flag2 = 1;

    if(divident < 0){
        flag1 = -1;
        divident = -divident;
    }

    if(divisor < 0){
        flag2 = -1;
        divisor = -divisor;
    }

    while (divident >= divisor){
        int doubleDivisor = divisor;
        int count1 = 1;
        while(2 * doubleDivisor <= divident){
            count1 *= 2;
            doubleDivisor *= 2;
        }
        divident -= doubleDivisor;
        count += count1;
    }
    return count * flag1 * flag2;
}

(三）改进二的方法，利用位运算

public int divide(int dividend, int divisor) {
    if(divisor == 0)
        return Integer.MAX_VALUE;
    if(divisor == -1 && dividend == Integer.MIN_VALUE)
        return Integer.MAX_VALUE;

    int count = 0;
    long pDividend = Math.abs((long)dividend);
    long pDivisor = Math.abs((long)divisor);

    while(pDividend >= pDivisor){
        int count1 = 0;
        while((pDivisor<<count1)<= pDividend){
            count1++;
        }
        count += 1<<(count1 - 1);
        pDividend -=(pDivisor<<(count1 - 1));
    }
    if( dividend >0 && divisor >0 || dividend<0 && divisor<0)
        return count;
    else
        return -count;
}