Why is this long overflowing to -1, instead of the minimum value for the type?

Question

I have the following code that returns the number of nodes in a tree when a complete Binary Tree is layer layers tall:

public static long nNodesUpToLayer(int layer) {         if (layer < 0) throw new IllegalArgumentException(             "The layer number must be positive: " + layer );          //At layer 0, there must be 1 node; the root.         if (layer == 0) return 1;          //Else, there will be 1 + 2 * (the number of nodes in the previous layer) nodes.         return 1 + (2 * nNodesUpToLayer(layer - 1)); 

The odd thing is, when I input 63 into the function (the minimum value that produces this), it gives me back -1. At 62, it gives back 9223372036854775807, so this seems to be caused by an overflow.

Shouldn't it give me back the minimum value of Java's long + the amount that it was overflowed by? Regardless of the input that I give it though (passed 62), it will always return -1 instead of a seemingly random number that I'd expect from an overflow.

I'm not entirely sure how to debug this, since it's recursive, and the value I'm interested in will only be evaluated once the the function has reached the base-case.

Answer 1

You are correct, it is an overflow error of a 64 bit signed integer. The reason it goes to -1 instead of the minimum integer value is because you are doubling it, not simply adding one.

9223372036854775807 in Two's Complement is 63 1s:

0111 1111 ... 1111 1111 

To double it in binary, simply perform a left shift:

1111 1111 ... 1111 1110 

However, this number in Two's Complement is not twice 9223372036854775807, but rather -2. Then, of course, you add 1 to that before returning to get your -1 result.

Answer 2

Actually, it is returning you the correct amount. It's just that "the amount that it was overflowed by" is exactly right to make the answer -1 :)

Consider this:
The number of nodes in a complete binary tree is 2^n - 1 for n layers. Hence its binary representation is 0000...00111...111 where the number of 1s is precisely the number of layers minus 1. As soon as you reach the length of the long you're stuck at the truncated 11...11, which is precisely -1