Links: Tom Edelson's home page; Tom Edelson's blog
In Java, the default integer data type is called int, and
a value of this type takes up 32 bits of computer memory. Like
almost all of the Java numeric types, an int is "signed",
which means that negative as well as positive data values can be
represented.
In
a blog
post dated April 9, 2008, I wrote that "the largest possible
positive value representable by a Java int is
231-1 (raise two the the thirty-first power, then subtract
one)." In ordinary decimal notation, 231-1 can be
written as 2,147,483,647, or somewhat over two billion.
There is no doubt in my mind that this statement is correct; one can confirm it, for example, in "The Java Language Specification, Third Edition", at http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.2.1. I am creating this page for the benefit of those who would like [at least a partial] explanation of why it is correct.
The explanation will be partial because it won't cover how negative numbers are represented, other than to say that, in a signed integer data type, one bit is used to represent the sign itself. Thus, starting with 32 bits, we now have 31 remaining. The original question is, therefore, equivalent to: "what's the largest value that could be represented in an unsigned integer data type of 31 bits?" (though you'd never find a 31-bit data type implemented in practice).
We will go on the assumption that the range of numbers representable,
in this hypothetical unsigned data type, starts at zero, and consists
of the whole numbers counted up from there. Technically, this
wouldn't have to be true: you could define a "data type" in which the
bit sequences were interpreted, not as consecutive whole numbers
starting at zero, but as, say, some collection of values containing
only prime numbers. However, that is only a theoretical
possibility; my assumption is certainly correct with regard to the
Java int type (if you restrict it to non-negative
values), and I don't know of any programming language having anything
it calls an "unsigned integer data type" for which this assumption is
not true.
You may be aware that "bit", as a computing term, is actually a contraction of "binary digit". And, where unsigned integer data types are concerned, each bit of storage is used to represent a binary digit.
That is, suppose you write a number out on paper, in binary notation, which works just like ordinary decimal notation ... except that only the two digits "0" and "1" are used. Suppose also that in writing down the number, you always write out 31 of these digits, using leading zeroes if the value isn't large enough to require 31 binary digits in conventional paper notation. (As for numbers too large to be represented in 31 binary digits, well, we'll just assume, on this page, that you're never called upon to write one of those.)
So our question is (also) equivalent to: "What's the biggest number that can be written as a 31-digit number, in binary notation [as described in the preceding paragraph]?"
To answer this, let's first look at how we'd answer questions like it, if they referred to the more-familiar decimal notation.
What's the biggest number you can write it two decimal digits? 99.
In three decimal digits? 999.
In four decimal digits? 9,999.
Note that we can also write those answers as:
Two decimal digits: 102-1.
Three decimal digits: 103-1.
Four decimal digits: 104-1.
None of that exactly explains why, but now consider. Suppose we were to talk, not about the biggest number, but about the number of different values that could be represented. Since the numbers start at zero, the total number of values is one more than the biggest value: for example, for one digit, there are ten values, namely 0 to 9.
Now look at two digits. Any value in the first digit can be paired with any value in the second. So you have:
In total, that's ten sets of ten, for a total of 100 (102) two-digit numbers (if we include zero and the one-digit numbers); in other words, 100 two-digit numbers, if we start at zero and use leading zeroes so as to make every-possible two-digit pattern that can represent a number. So this is consistent with the largest value being 102-1, or 99.
Now if we expand to three digits: again you have ten possibilities for the first digit: 0 through 9. But any of those can be followed by any of the 100 two-digit numbers. So you have ten sets of 100, or 1,000 (103), and the largest value is 999, or 103-1.
At this point, I hope it's apparent that, with decimal digits, each time you add a digit to the length of a number, you multiply the number of possible values by ten. Why ten? Because there are, each time, ten possible values for the new first digit in the number.
So, to summarize: with decimal numbers, if you have n
digits to work with, then you can represent a total of
10n values ... and the largest value is
10n-1.
I would assert that this could be formalized as a "proof by mathematical induction"; but I won't actually do that here.
All right, now what about binary numbers? As I said, they work just like decimal numbers, except that there are only two digits: 0 and 1. So of course, there are two one-digit numbers: again, zero and one.
With two digits: you can choose either of the two for the first digit, and for each choice, you have two possibilities for the second digit: two sets of two, or 4 (22) different values in all: zero through three (22-1).
So the progression is exactly like the one in the decimal numbers, except that each time you add a digit, you multiply the number of values by two, instead of ten. With three digits, the possibilities consist of two sets of four, for a total of eight, and the values represented are zero through seven (23-1).
And so on.
So in general, if you have n binary digits to work with,
then you can represent a total of 2n values:
zero through 2n-1.
And in particular, with 31 binary digits ... and assuming that they're all available to represent the magnitude, in other words, you don't have one reserved for the sign ... then the largest value you can represent is 231-1.
If you have 32 binary digits in total, but one of them is
reserved for the sign (as is the case with a Java int),
then you still have 31 bits for the magnitude, and so 231-1
is still the largest (positive) value that you can represent.
As the mathematicians say, quod erat demonstrandum (which is Latin for "That's what you get for not taking my word for it").
P.S. If you really want to know how negative numbers are (almost always) represented in a computer, and why ... and also why I didn't want to cover that, also, here ... you could take a look at the Wikipedia article on Two's complement.
This page created: 2008-04-07.