Where does the "2" in 2^n come from when computing max memory size? n=n-bit

Solution 1:

2 comes from the nature of binary numbers, where there are exactly 2 possible states per digit.

When calculating the number of values a given number of digits can contain, the calculation is always Options^Instances. Options represent the set of possible choices a digit could have, and Instances represents the number of digits being used (length, width, and size are common synonyms).

Likewise, to calculate the range of values that could be stored, it is 0 -> (Options^Instances) - 1.

Note that digit values are always natural numbers, so we're not worried about negative numbers or decimals or anything more exotic. Those concepts build atop digit values to augment their meaning, but the underlying value representation is unchanged. 3, -3, and 3.3 all express different meanings, but they all use the digit value 3 in the same way with the same rules.

So a 2-bit number can express 4 possible values, ranging from 0 to 2^2-1 (0-3). Ie. the set of possible values is {00, 01, 10, 11}.

a digit of binary contains 2 options, so it is Base-2. Most common number systems in use these days have 10 options per digit (0-9), so they are Base-10. Other common bases include Octal (base-8) and Hexadecimal (base-16).

This concept isn't even limited to numbers, but any well designed set of values. If I wanted to calculate the the number of possible 8-character passwords consisting of all lower case Latin letters, it would be 26^8. If I added capital letters, it would be 52^8. If I then added numbers, it would be 62^8. For binary numbers however, since it can only be 0 or 1, it's always 2^n.

Bit-size refers to the number of bits used to store a value (the "Instances" variable). For a real-world example, the game No Man's Sky uses a 32-bit number to represent money, so you can never get more than ‭4,294,967,295 money. That's because it's the maximum value you can express in 32 bits.

Solution 2:

Here's an attempt at "explain it like I'm 5" type of answer.

A single bit has two states: 0 and 1. Using a single bit I can store two values:

0
1

By adding a single bit we can store four values. Let's ignore that they are binary numbers, just keep in mind that they are distinct values:

00
01
10
11

Add another one and we have eight values:

000
001
010
011
100
101
110
111

Why are they doubling? Imagine you're prepending the new bit to the left. If the bit is 0, you get previous set of four values but prefixed by 0. If it's 1, you get previous set of four values prefixed by 1. That's 8 total: 4 previous values times 2 possible states of the added bit.

 previous bits  |    previous bits
 ↓↓             |    ↓↓
000             |   100
001             |   101
010             |   110
011             |   111
↑               |   ↑
new '0' bit     |   new '1' bit

Here's a graphical version, if you don't like ASCII art:

If we had three possible states for the prepended "bit" ("trit"?), let's say A, B and C, we'd triple the number of possible values:

 previous bits  |    previous bits  |    previous bits
 ↓↓             |    ↓↓             |    ↓↓
A00             |   B00             |   C00
A01             |   B01             |   C01
A10             |   B10             |   C10
A11             |   B11             |   C11
↑               |   ↑               |   ↑
new 'A' bit     |   new 'B' bit     |   new 'C' bit

So adding a new bit to the value multiplies number of possible values by number of states this new bit can have. First bit has 2 states (0 and 1), so a 1-bit number has 2 values. Second bit has two states:

2 × 2 = 4
↑   ↑
↑    number of 2nd bit's states
↑
 number of 1st bit's states

Third bit has two states too:

4 × 2 = 8
↑   ↑
↑    number of 3rd bit's states
↑
 number of previous values

Same with the fourth bit:

8 × 2 = 16
↑   ↑
↑    number of 4th bit's states
↑
 number of previous values

We can expand the 8 in this formula to our previous calculations:

((2 × 2) × 2) × 2 = 16
  ↑   ↑    ↑    ↑
  ↑   ↑    ↑     number of 4th bit's states
  ↑   ↑    ↑
  ↑   ↑     number of 3rd bit's states
  ↑   ↑
  ↑    number of 2nd bit's states
  ↑
   number 1st bit's states

As you can see, to get the number of possible values, you have to multiply numbers of states of particular bits. Since all of our bits have 2 states, we can simplify multiplying 2's n times to a simply 2ⁿ.

Solution 3:

Let me complement the existing answers with an analogy: How many different numbers (let's call them addresses) can you build with an n-digit number?

Let's try:

• 2 digits can build addresses from 00 to 99, which are 100 addresses.
• 3 digits can build addresses from 000 to 999, which are 1000 addresses.
• ...
• In general, n digits can build 10^n addresses.

That's because one (decimal) digit has 10 possible states (0-9, latin decem = ten).

Bits are like digits, except that they only have 2 states (0 and 1). Hence, n bits can build 2^n addresses.