38

The maximum value of an n-bit integer is 2n-1. Why do we have the "minus 1"? Why isn't the maximum just 2n?

1

12 Answers 12

80

The -1 is because integers start at 0, but our counting starts at 1.

So, 2^32-1 is the maximum value for a 32-bit unsigned integer (32 binary digits). 2^32 is the number of possible values.

To simplify why, look at decimal. 10^2-1 is the maximum value of a 2-digit decimal number (99). Because our intuitive human counting starts at 1, but integers are 0-based, 10^2 is the number of values (100).

5
  • And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? Sep 28, 2013 at 19:24
  • 1
    It doesn't matter what the platform is. The maximum value you can store in an N-bit unsigned integer that's 0-based is always 2^N-1.
    – tenfour
    Sep 28, 2013 at 23:45
  • @tenfour and so for a signed integer it would be 2^N-2. Would I be correct to say that?
    – samol
    Jan 5, 2014 at 19:03
  • The max value of a signed integer depends on how the integer is stored. A lot of times it's 2^(n-1)-1 on the positive side and -2^(n-1) on the negative side, but you should consult your documentation for your language/system. Mar 3, 2014 at 23:39
  • Generally: It doesn't matter what the base and number of digits are. The maximum value you can store in an N-digit unsigned integer in based B is always B^N-1
    – phuclv
    Dec 10, 2016 at 17:31
32

2^32 in binary:

1 00000000 00000000 00000000 00000000

2^32 - 1 in binary:

11111111 11111111 11111111 11111111

As you can see, 2^32 takes 33 bits, whereas 2^32 - 1 is the maximum value of a 32 bit integer.

The reason for the seemingly "off-by-one" error here is that the lowest bit represents a one, not a two. So the first bit is actually 2^0, the second bit is 2^1, etc...

1
  • 1
    And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? Sep 28, 2013 at 19:25
15

232 in binary is one followed by 32 zeroes, for a total of 33 bits. That doesn't fit in a 32-bit int value.

13
  • And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? Sep 28, 2013 at 19:23
  • 1
    @HardikThaker - Yes, it does. (Actually, in Java, Integer.MAX_VALUE--for 32 bit integers--is 2^31 - 1 and Long.MAX_VALUE--for 64 bit integers--is 2^63 - 1 because the sign bit is reserved.)
    – Ted Hopp
    Sep 29, 2013 at 0:03
  • @Ted Hopp What sign bit? There is no such thig as a sign bit.
    – Ingo
    Nov 5, 2013 at 8:20
  • @Ingo - "There is no such thig as a sign bit" Huh? In most languages I know there is indeed a sign bit. Java (which is what I was talking about specifically in the comment) uses a signed, two's-complement representation for most integer types (char excluded). Refer to the Wikipedia article on Two's complement and you can read all about the sign bit. Also refer to the Wikipedia article on Sign bit.
    – Ted Hopp
    Nov 5, 2013 at 12:58
  • @TedHopp Sign bit in languages? Not likely. You can call the leftmost bit the sign bit because the representation is choosen so that this bit indicates a negative sign if you use signed integers. You could also call the rightmost bit the odd bit because it indicates odd values. But neither of them is "reserved". In fact, you can do (some) unsigned computations that utilize the sign bit just fine, even in Java. For example (2* 0x40000001 - 3) should give you MAXINT. Note that the multiplication yields 0x80000002, and uses the sign bit.
    – Ingo
    Nov 5, 2013 at 13:10
13

In most programming languages, 0 is a number too.

3
  • Depends if you're talking whole or natural numbers ;) Apr 24, 2011 at 15:55
  • @Russel Well even for natural numbers 0 is often included, so not even Mathematicians ever agreed on that (but really it's just one of the more useful numbers out there - if at all we should get rid of 27 or whatever :p )
    – Voo
    Apr 24, 2011 at 15:59
  • @RussellTroywest Peano and Frege told us what natural numbers are, and of course they started from 0. Despite this, in some contexts it is understodd that the set N \ {0} is used and referred to as "natural numbers".
    – Ingo
    Nov 5, 2013 at 8:24
6

The numbers from 0 to N are not N. They are N+1. This is not obvious to the majority of people and as a result many programs have bugs because if this reason.

0
4

If you're just starting out with programming, I suggest you take a look at this wiki article on signed number representations

As Vicente has stated, the reason you subtract 1 is because 0 is also an included number. As a simple example, with 3 bits, you can represent the following non-negative integers

0 : 000
1 : 001
2 : 010
3 : 011
4 : 100
5 : 101
6 : 110
7 : 111

Anything beyond that requires more than 3 digits. Hence, the max number you can represent is 2^3-1=7. Thus, you can extend this to any n and say that you can express integers in the range [0,2^n -1]. Now you can go read that article and understand the different forms, and representing negative integers, etc.

4

It's because in computing, numbers start at 0. So if you have, for example, 32 address lines (232 addressable bytes), they will be in the range [0, 2^32).

4

Because 0 is also represented. The amount of numbers you can represent is indeed 2^n with n bits, but the maximum number is 2^n-1 because you have to start the count in 0, that is, every bit set to 0.

For 1 bit: 0, 1
For 2 bits: 0, 1, 2, 3
For 3 bits: 0, 1, 2, 3, 4, 5, 6, 7

And so on.

3

If I ask you what is the biggest value you can fit into a 2-digit number, would you say it's 102 (100) or 102-1 (99)? Obviously the latter. It follows that if I ask you what the biggest n-digit number is, it would be 10n-1. But why is there the "-1"? Quite simply, because we can represent 0 in a 2-digit number also as 00 (but everyone just writes 0).

Let's replace 10 with an arbitrary base, b. It follows that for a given base, b, the biggest n-digit number you can represent is bn-1. Using a 32-bit (n = 32) base-2 (b = 2) number, we see that the biggest value we can represent 232-1.


Another way of thinking about it is to use smaller numbers. Say we have a 1-bit number. Would you tell me the biggest value it can represent is 21 or 21-1?

3

Why do we have the "minus 1"?

Just answer the question: What is the maximum value of an 1-bit integer?

One bit integer can store only two (21) values: 0 and 1. Last value is 12 = 110

Two bit integer can store only four (22) values: 00, 01, 10 and 11. Last value is 112 = 310

Thus, when integer can stores N, values last value will be N-1 because counting starts from zero.

n bit integer can store 2n values. Where last will be 2n-1

Example: One byte can store 28 (256) values. Where first is 0 and last is 255

Why isn't the maximum just 2n?

Because counting starts from zero. Look at first value for any n bit integer.
For example byte: 00000000

This would be very confusing if:
00000001 means 2
00000000 means 1

would not? ;-)

2

In most programming languages integer is a signed value (see two's complement).

For example, in Java and .NET integer most left byte is reserved for sign:

  • 0 => positive or zero number
  • 1 => negative number

Then the maximum value for 32-bit number is limited by 231. And adding -1 we get 231 - 1.

Why does -1 appear?

Look at more simple example with unsigned Byte (8-bits):

  1  1  1  1  1  1  1  1
128 64 32 16  8  4  2  1  <-- the most right bit cannot represent 2
--- --------------------
128 + 127 = 255 

As other guys pointed out the most right bit can have a maximum value of 1, not 2, because of 0/1 values.

Int32.MaxValue = 2147483647 (.NET)
0

In the field of computing we start counting from 0.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.