Why is 2 to the power of 31 returning a negative in this Java function?

Question

Assignment:

Write a recursive function recPow that computes 2n for n >= 0 in Java. The function will have the following profile:

public static int recPow(int n)

The function must consider all cases and be tested exhaustively.

My Problem

I don't understand why my code returns -2147483648 when I enter recPow(31) instead of 2147483648. I know some of you might tell me to switch to long instead of int, but I believe due to the assignment's verbiage I need to stick with int. I have never been very good computing numbers if any one can help me understand why this happens I would truly, greatly appreciate it.

Additionally - larger exponents return 0 (however I think this may have to do with the fact that we need to use ints vs longs.)

My Code

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);
        }
    }
}

Max int in Java is 2147483647, so you cannot represent a value of 2147483648 as an `int`. I'll try to find a helpful dup. — azurefrog, Oct 06 '18 at 18:16
Possible duplicate of [How does Java handle integer underflows and overflows and how would you check for it?](https://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo) — azurefrog, Oct 06 '18 at 18:18
and I think for more than 2^31 it is because bits for int, for example 2^31 is biggest negative number which its binary is 10000000 for example in 8 bit. if you multiply it with 2 you will shift it one level to left so it is zero (you have only 8 bit no more) as far as I know. — Amin, Oct 06 '18 at 18:20
Hi, Thank you for your response, I see, perhaps i need to make some sort of exception for this case. I am sorry I don't understand what you mean by a helpful dup? Sorry, what is this? Thank you — cdm89, Oct 06 '18 at 18:20
@cdm89 "helpful dup" is a "helpful duplicate question that explain it very good" — Amin, Oct 06 '18 at 18:21
@azurefrog thank you, I will try to implement based on this question you posted and let you know how it goes — cdm89, Oct 06 '18 at 18:35

score 4 · Accepted Answer · edited Oct 06 '18 at 18:59

This is due to overflow of the int data type.

Java's int size is 32 bits, so the range is -2,147,483,648 to 2,147,483,647.

2^31 = 2147483648

So it is overflowing to -2147483648 as the binary value of 2,147,483,647 is 01111111111111111111111111111111 (one zero and 31 ones), where the first bit is the "sign bit" (2's complement form).

If you try to go beyond this limit (2,147,483,647) by 1 (i.e. adding 1 to it), it changes the sign bit to 1, making this int negative.

So it will become 10000000000000000000000000000000 (1 one and 31 zeros), giving you the answer -2147483648.

Peter Lawrey · Answer 2 · 2018-10-06T18:26:02.077

3

larger exponents return 0 (however I think this may have to do with the fact that we need to use ints vs longs.)

Correct.

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

You can use long however this has the same problem but for a higher value.

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

One way to check for an overflow is to see

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

or to check for overflow

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));
}

You can use BigInteger which has a much, much greater limit.

edited Oct 06 '18 at 18:26

answered Oct 06 '18 at 18:19

Peter Lawrey

525,659
79
751
1,130

Hi Peter, thank you for your answer, i really appreciate the help, however i dont think for this assignment i am allowed to change the type being used since we are given the profile in the assignment. Is there a way to do this without needing to change types? I was also hoping you can explain why you do int j = i * 2? – cdm89 Oct 06 '18 at 18:26
I am not sure I completely understand the conditional statement. "if the power is 0 then return 1L, else multiplyExact() - but I think this should be if the power is larger than 30, do you agree or am I completely misunderstanding? Thank you again for the help – cdm89 Oct 06 '18 at 18:48
@cdm89 to show you what you get 0. Every time you multiply by 0 you add a 0 bit to the bottom of the number shifting. After adding 32 zero you get all 0. – Peter Lawrey Oct 07 '18 at 20:11
@cdm89 you are right if you assume the base is 2, for higher bases your limit is lower. – Peter Lawrey Oct 07 '18 at 20:12
@cdm89 it's a bit like asking, how can I double the number of days in October so I can have October the 60th? You could invent a calendar which allows this or invent a language where into has a wider range, but you are better off accepting October has 31 days and int is limited to 2^31-1. – Peter Lawrey Oct 07 '18 at 20:16

Why is 2 to the power of 31 returning a negative in this Java function?

2 Answers2