Разделите два целых числа без использования умножения, деления и оператора мод в Java

Question

Я записываю код, который определяет частное после деления двух чисел, но без использования умножения, деления или оператора мод.

Мой код

public int divide(int dividend, int divisor) {

    int diff=0,count=0;
    int fun_dividend=dividend;
    int fun_divisor=divisor;
    int abs_dividend=abs(dividend);
    int abs_divisor=abs(divisor);

    while(abs_dividend>=abs_divisor){
        diff=abs_dividend-abs_divisor;

        abs_dividend=diff;
        count++;

    }

    if(fun_dividend<0 && fun_divisor<0){
        return count;
    }
    else if(fun_divisor<0||fun_dividend<0) {
        return (-count);
    }

    return count;

}

Мой код проходит тестовые случаи, такие как "делимое =-1", "делитель =1" или "делимое =1" и "делитель =-1". Но он не может пройти тестовый пример, такой как divnd= -2147483648 и divisor=-1. Однако у меня есть утверждение if, когда оба входа отрицательны.

  if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

Когда мои входы -2147483648 и -1, он вернул ноль. Я отладил свой код и обнаружил, что он не может достичь внутренних операторов цикла while. Он просто проверяет цикл while, завершается и выполняет

 if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

Это очень очевидно, оба входа отрицательны, поэтому я использовал Math.abs функция, чтобы сделать их позитивными. Но когда я пытаюсь увидеть значения переменных abs_dividend и abs_divisor, они показывают мне отрицательные значения.

Integer max может принимать 9-значное число. Так как я мог пройти этот контрольный пример? Согласно этому тестовому случаю дивидендом является 10-значное число, которое недопустимо для целочисленного диапазона.

Согласно тесту, вывод, который я получаю, должен быть 2147483647.

Как я мог решить ошибку?

Заранее спасибо.

Answer 1

Побежал с отладчиком и обнаружил, что abs_dividend был -2147483648.

Тогда сравнение в while (abs_dividend >= abs_divisor) { ложно и count никогда не увеличивается.

Оказывается, объяснение в Javadoc для Math.abs(int a):

Обратите внимание, что если аргумент равен значению Integer.MIN_VALUE, наиболее отрицательному представляемому значению int, результатом будет то же значение, которое является отрицательным.

Предположительно, это потому, что Integer.MAX_VALUE 2147483647, поэтому невозможно представить положительное значение 2147483648 с int, (примечание: 2147483648 будет Integer.MAX_VALUE + 1 == Integer.MIN_VALUE)

Answer 2

Попробуйте использовать битовую манипуляцию для этого следующим образом:

public static int divideUsingBits(int dividend, int divisor) {
        // handle special cases
        if (divisor == 0)
            return Integer.MAX_VALUE;
        if (divisor == -1 && dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;

        // get positive values
        long pDividend = Math.abs((long) dividend);
        long pDivisor = Math.abs((long) divisor);

        int result = 0;
        while (pDividend >= pDivisor) {
            // calculate number of left shifts
            int numShift = 0;
            while (pDividend >= (pDivisor << numShift)) {
                numShift++;
            }

            // dividend minus the largest shifted divisor
            result += 1 << (numShift - 1);
            pDividend -= (pDivisor << (numShift - 1));
        }

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            return result;
        } else {
            return -result;
        }
    }

Answer 3

Я решаю это так. Отдать предпочтение типу данныхlong над intвезде, где есть вероятность переполнения при сдвиге влево. Обрабатывайте крайний регистр в самом начале, чтобы избежать изменения входных значений в процессе. Этот алгоритм основан на технике деления, которую мы использовали в школе.

public int divide(int AA, int BB) {
    // Edge case first.    
    if (BB == -1 && AA == Integer.MIN_VALUE){
        return Integer.MAX_VALUE;   // Very Special case, since 2^31 is not inside range while -2^31 is within range.
    }
    long B = BB;
    long A = AA;

    int sign = -1;
    if ((A<0 && B<0) || (A>0 && B>0)){
        sign = 1;
    }
    if (A < 0) A = A * -1;
    if (B < 0) B = B * -1;

    int ans = 0;
    long currPos = 1; // necessary to be long. Long is better for left shifting.
    while (A >= B){
        B <<= 1; currPos <<= 1;
    }
    B >>= 1; currPos >>= 1;
    while (currPos != 0){
        if (A >= B){
            A -= B;
            ans |= currPos;
        }
        B >>= 1; currPos >>= 1;
    }
    return ans*sign;
}