Количество символов, которые можно закодировать n битами: 2ⁿ.
Наибольшее число, закодированное n битами: 2ⁿ – 1.
Наименьшее число, закодированное n битами: 2ⁿ⁻¹.
2⁵ = 32
2⁵ – 1 = 31
2⁽⁵⁻¹⁾ = 2⁴ = 16
Получается, что в этом 32-символьном алфавите наибольшее число — 31, а наименьшее — 16. Разве числа меньше 16 (1, 2, 3, 4, 5, 9...) не самые маленькие? Может ли кто-нибудь объяснить мне это подробно?

Здесь смешались две разные задачи:

1. Сколько разных значений можно закодировать n битами

2. Какие числа имеют ровно n бит в двоичной записи без ведущих нулей

Из-за этого и появляется противоречие.

1. n бит дают 2ⁿ разных комбинаций

Если у нас есть n бит, каждый бит может быть либо 0, либо 1.

Значит, всего комбинаций:

2ⁿ

Для 5 бит:

2⁵ = 32

То есть 5 битами можно закодировать 32 разных значения.

Эти комбинации такие:

00000
00001
00010
00011
00100
...
01111
10000
10001
...
11111

Всего их 32.

Если мы интерпретируем эти комбинации как беззнаковые целые числа, то получаем диапазон:

00000₂ = 0
00001₂ = 1
00010₂ = 2
...
01111₂ = 15
10000₂ = 16
...
11111₂ = 31

То есть 5 битами можно закодировать числа:

от 0 до 31

А если ноль не используется, то:

от 1 до 31

2. Почему тогда говорят, что наименьшее n-битное число — 2ⁿ⁻¹?

Фраза:

Наименьшее число, закодированное n битами: 2ⁿ⁻¹

часто означает не «наименьшее число, которое можно хранить в n битах», а другое:

наименьшее положительное число, двоичная запись которого действительно занимает ровно n бит без ведущих нулей.

Например, возьмём числа в двоичной системе:

1  = 1₂
2  = 10₂
3  = 11₂
4  = 100₂
5  = 101₂
8  = 1000₂
15 = 1111₂
16 = 10000₂
31 = 11111₂

Число 16 в двоичной записи:

10000₂

Это первое число, для записи которого нужно ровно 5 бит, если не писать ведущие нули.

Число 15:

1111₂

занимает только 4 бита.

Число 9:

1001₂

тоже занимает 4 бита.

Число 3:

11₂

занимает 2 бита.

Поэтому среди чисел, которые в обычной двоичной записи имеют ровно 5 бит, минимальное — это:

10000₂ = 16

А максимальное:

11111₂ = 31

То есть для чисел, двоичная запись которых имеет ровно 5 бит:

от 16 до 31

Их действительно 16 штук:

16, 17, 18, ..., 31

Главное различие

Есть две разные формулировки.

Вариант 1

«Какие числа можно представить с помощью 5 бит?»

Ответ:

00000₂ = 0
00001₂ = 1
00010₂ = 2
...
11111₂ = 31

То есть:

от 0 до 31

Здесь числа меньше 16, конечно, есть. Просто они записываются с ведущими нулями:

1  = 00001₂
2  = 00010₂
3  = 00011₂
4  = 00100₂
5  = 00101₂
9  = 01001₂
15 = 01111₂

Они занимают 5 бит в памяти или в коде, потому что мы специально дописываем нули слева.

Вариант 2

«Какие числа имеют ровно 5 бит в двоичной записи без ведущих нулей?»

Ответ:

10000₂ = 16
10001₂ = 17
...
11111₂ = 31

То есть:

от 16 до 31

Здесь числа меньше 16 не подходят не потому, что они «не существуют», а потому что их обычная двоичная запись короче 5 бит.

Например:

9 = 1001₂

Это 4-битная запись.

Но если нужно хранить число в поле длиной 5 бит, можно записать:

9 = 01001₂

Тогда это уже 5-битный код, но само число всё равно имеет значение 9.

Как это связано с 32-символьным алфавитом

Если у вас есть алфавит из 32 символов, каждому символу можно назначить один из 32 кодов:

00000
00001
00010
...
11111

Их можно пронумеровать так:

0, 1, 2, 3, ..., 31

Например:

А → 00000 → 0
Б → 00001 → 1
В → 00010 → 2
Г → 00011 → 3
...
последний символ → 11111 → 31

В этом случае наименьший код — это не 16, а 0:

00000

Или 1, если вы по какой-то причине решили не использовать нулевой код.

А число 16 — это только наименьшее число, которое в двоичной записи начинается так:

10000

и действительно требует 5 бит без ведущих нулей.

Коротко

Правильно так:

5 бит дают 2⁵ = 32 комбинации.
Если считать их беззнаковыми числами, диапазон: 0...31.
Максимальное значение: 2⁵ − 1 = 31.
Минимальное значение: 0.

А формула:

2ⁿ⁻¹

означает другое:

наименьшее число, для записи которого нужно ровно n бит без ведущих нулей

Для n = 5 это:

2⁴ = 16

То есть числа 1, 2, 3, 4, 5, 9 действительно меньше 16, но в обычной двоичной записи они занимают меньше 5 бит:

1 = 1₂
2 = 10₂
3 = 11₂
4 = 100₂
5 = 101₂
9 = 1001₂

А в 5-битном коде они просто записываются с нулями слева:

1 = 00001₂
2 = 00010₂
3 = 00011₂
4 = 00100₂
5 = 00101₂
9 = 01001₂