Почему от 2 до 31 возвращает отрицательное значение в этой функции Java? - PullRequest
Новая
       32

Почему от 2 до 31 возвращает отрицательное значение в этой функции Java?

0 голосов
/ 06 октября 2018

Назначение:

Напишите рекурсивную функцию recPow, которая вычисляет 2n для n> = 0 в Java.Функция будет иметь следующий профиль: 

public static int recPow(int n)

Функция должна учитывать все случаи и быть тщательно протестирована.

Моя проблема

Я не понимаю, почему мой код возвращает -2147483648, когда я ввожу recPow(31) вместо 2147483648. Я знаю, что некоторые из вас могут сказать мне переключиться на long вместо int, но я полагаю, что из-засловоблудие назначения мне нужно придерживаться Int.У меня никогда не было очень хороших вычислений чисел, если кто-нибудь может помочь мне понять, почему это происходит, я действительно, очень ценю это.

Дополнительно - более крупные показатели возвращают 0 (однако я думаю, что это может иметь отношение к фактучто нам нужно использовать ints против long.)

Мой код 

public static int baseNum = 2, powResult = 1;

public static int recPow(int n) {
    //if the int is not bigger than 0 
    //must only accept ints
    if (n < 0) {
        throw new IllegalArgumentException("n has to be > 0");
    } else {
        //recursion here
        //base number = 2
        if (n==0) {
            return powResult;
        } else {
            powResult = powResult * baseNum;
            return recPow(n - 1);
        }
    }
}

Ответы [ 2 ]

0 голосов
/ 06 октября 2018

Это происходит из-за переполнения типа данных int.

Размер Java int равен 32 битам, поэтому диапазон составляет от 2 147 483 648 до 2 147 483 647.

2 ^ 31 =2147483648

Таким образом, он переполняется до -2147483648, поскольку двоичное значение 2 147 483 647 равно 01111111111111111111111111111111 (один ноль и 31 единица), где первый бит является «знаковым битом» (форма дополнения 2).

Если вы попытаетесь выйти за этот предел (2 147 483 647) на 1 (т.е. добавив к нему 1), он изменит бит знака на 1, что сделает этот int отрицательным.

станет 10000000000000000000000000000000 (1 один и 31 ноль), давая вам ответ -2147483648.

0 голосов
/ 06 октября 2018

большие экспоненты возвращают 0 (однако я думаю, что это может быть связано с тем фактом, что нам нужно использовать целые числа против длинных.)

Правильно. 

int i = (int) 2147483648L; // -2147483648 due to over flow
int j = i * 2; // 0 due to overflow.

Вы можете использовать long, однако это имеет ту же проблему, но для более высокого значения. 

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L : baseNum * recPower(baseNum, power - 1);
}

Один из способов проверить переполнение - это посмотреть 

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L : baseNum * recPower(baseNum, power - 1);
}

илипроверка на переполнение 

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L 
           : Math.multiplyExact(baseNum, recPower(baseNum, power - 1));
}

Вы можете использовать BigInteger, который имеет гораздо больший лимит.

...