Сколько разных значений можно закодировать N битами?
В учебнике формула: количество вариантов = 2 в степени N, где N — число бит. Но я не понимаю, почему именно так. Если у меня 3 бита, почему получается 8 значений, а не, например, 6 (3 умножить на 2)? Объясните логику, а не просто формулу.
2 ответа
Каждый бит удваивает число вариантов, а не добавляет фиксированное количество. Поэтому степень, а не умножение.
Посмотри по шагам:
- 1 бит: 0, 1 → 2 варианта
- 2 бита: 00, 01, 10, 11 → 4 варианта
- 3 бита: 000, 001, 010, 011, 100, 101, 110, 111 → 8 вариантов
Каждый новый бит даёт два продолжения для каждой уже имеющейся комбинации — вот откуда удвоение. 2 → 4 → 8 → 16... Это и есть 2ᴺ.
Для 3 бит: 2³ = 8. Не 6, потому что биты не складываются, а перемножаются: 2·2·2.
Обратная задача тоже частая на экзамене: «сколько бит нужно, чтобы закодировать K разных значений?» — берёшь наименьшее N, при котором 2ᴺ ≥ K. Например, для 100 значений: 2⁶ = 64 мало, 2⁷ = 128 хватает → нужно 7 бит.