Why is the maximum value of an unsigned n-bit integer 2ⁿ-1 and not 2ⁿ?

Question

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

Balmuth

possible duplicate of What is “2's Complement”? – Monkhood

Answer 1

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).

Lysander

And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? – Subphylum

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. – Lysander

@Lysander and so for a signed integer it would be 2^N-2. Would I be correct to say that? – Closestool

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. – Voluntaryism

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 – Kelle

Answer 2

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...

Berneicebernelle

And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? – Subphylum

Answer 3

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

Marcellus

And what if I have 64 bit machine and OS and Java ?? Does it increases to 2 ^ 64 - 1 ?? – Subphylum

@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.) – Marcellus

@Ted Hopp What sign bit? There is no such thig as a sign bit. – Benz

@Benz - "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. – Marcellus

@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. – Benz

@Benz The Java Language Specification (section 4.2) says, "The integral types are byte, short, int, and long, whose values are 8-bit, 16-bit, 32-bit and 64-bit signed two's-complement integers, respectively" The sign bit is part of the language specification because a sign bit is part of the definition of "signed two's-complement integers". It's only because Java does not signal integer overflow/underflow (also per the Java spec) that your little example works. It would fail in some other languages. – Marcellus

@TedHopp I told you before that the sign bit is sloppy language for sign indication bit (at best). And it is in no way "reserved" (for what?). The fact that Java uses signed integers and the fact that the above computation gives the correct result nevertheless should give you something to think about. – Benz

@Benz - I'm sorry, but that's simple pedantry. Do you also claim that the IEEE 754 standard for floating-point arithmetic uses "sloppy language"? After all, it has an entire section (6.3) titled "The sign bit" and it doesn't mention "sign indication bit" at all. The fact that your computation gives the correct result is also part of the JLS (15.17.1): "If an integer multiplication overflows, then the result is the low-order bits of the mathematical product as represented in some sufficiently large two's-complement format." (Similar language in 15.18.2 for addition; my emphasis.) – Marcellus

See, @TedHopp, the floating point "sign bit" is a completely different story: en.wikipedia.org/wiki/… This is exactly unlike 2's complement, where you cannot simply turn the "sign bit" to negate a number. My comment is exactly to carve out the difference between a real sign bit, and a bit that merely indicates the sign. Does it even occur to you that a sign-magnitude representation of integers would as well be possible? And why it is not used? – Benz

@Benz - The very Wikipedia article you cite uses "sign bit" when discussing two's-complement integer representation (and does not mention "sign indication bit" at all). Also consider the C89 ANSI C standard: "The handling of overflow, divide check and other exceptions in expression evaluation is not defined by the language. Most existing implementations of C ignore overflow in evaluation of signed integral expressions and assignments, but this behavior is not guaranteed." (My emphasis.) Your little example could easily fail in a C environment (depending on the implementation). – Marcellus

@Benz - I should add that Ada would signal integer overflow with your sample calculation. This is true for some other languages as well. It is simply wrong to assume that the sign bit is unreserved in general. – Marcellus

@TedHopp I am sorry to say that, but you're confusing too many things. First, from the wiki article you cited (emphasis by me): "The most significant bit determines the sign of the number and is sometimes called the sign bit. **Unlike in sign-and-magnitude representation, the sign bit also has the weight −(2N − 1) ** shown above." And regarding C: contrary to Java, the C standard does not require or guarantee 2's complement. Hence, yes, it could fail in C. Irrelevant for our discussion of signed 2's complement. – Benz

@TedHopp The article I linket to does not use the term sign bit when discussing 2's complement. It only uses the term 3 times (according to my browser) in the discussion of the sign-magnitude representation, which is, I say it the last time for today, entirely different than 2's complement. (For example, it has a sign bit.) – Benz

Answer 4

In most programming languages, 0 is a number too.

Stun

Depends if you're talking whole or natural numbers ;) – Trinitrotoluene

@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 ) – Depend

@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". – Benz

Answer 5

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.

Siccative

Answer 6

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

Eley

Answer 7

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.

Araujo

Answer 8

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.

Philosophism

Answer 9

If I ask you what is the biggest value you can fit into a 2-digit number, would you say it's 10² (100) or 10²-1 (99)? Obviously the latter. It follows that if I ask you what the biggest n-digit number is, it would be 10ⁿ-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 bⁿ-1. Using a 32-bit (n = 32) base-2 (b = 2) number, we see that the biggest value we can represent 2³²-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 2¹ or 2¹-1?

Monkhood

Answer 10

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 (2¹) values: 0 and 1. Last value is 1₂ = 1₁₀

Two bit integer can store only four (2²) values: 00, 01, 10 and 11. Last value is 11₂ = 3₁₀

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 2ⁿ-1

Example: One byte can store 2⁸ (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? ;-)

Spadefish

Answer 11

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 2³¹. And adding -1 we get 2³¹ - 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)

Alpert

Answer 12

In the field of computing we start counting from 0.

Telekinesis