Подсчёт цифр, единиц и нулей

Учимся считать разряды, единицы и нули в двоичной записи и решать комбинаторные задачи через степени двойки.

Опорный факт. В двоичной системе число $2^{k}$ записывается как единица и $k$ нулей; всего различных $k$-разрядных двоичных наборов ровно $2^{k}$.

Это самый «формульный» урок раздела. Здесь экзамен проверяет, чувствуешь ли ты связь между степенями двойки и длиной двоичной записи. Типичные вопросы: сколько разрядов в двоичной записи числа; сколько в ней единиц или нулей; сколько всего чисел в заданном диапазоне обладают неким свойством. Всё это решается короткими формулами, если знать пару опорных фактов.

Зачем это нужно? Перебирать числа вручную на экзамене невозможно — диапазоны бывают огромными. Степени двойки превращают «посчитай все такие числа» в одно умножение или вычитание. Это экономит минуты и нервы.

Сколько разрядов в двоичной записи

Число $N$ в двоичной системе занимает $k$ разрядов, если оно попадает в диапазон от $2^{k-1}$ до $2^{k}-1$ включительно. Формально количество двоичных разрядов есть

$$ k = \lfloor \log_2 N \rfloor + 1. $$

Например, для $N = 100$: $2^{6} = 64 \le 100 \lt 128 = 2^{7}$, значит $k = 7$ разрядов. Действительно, $100 = 1100100_2$ — пересчитай цифры, их семь.

Степени двойки — таблица-памятка

Закономерность видна: $2^{k}$ — это единица и $k$ нулей, то есть запись из $k+1$ разряда. Запомнить степени двойки до $2^{10}=1024$ крайне полезно: они всплывают почти в каждой задаче.

Подсчёт единиц и нулей

Число вида $2^{k} - 1$ в двоичной системе — это $k$ единиц подряд. Например, $2^{4} - 1 = 15 = 1111_2$ (четыре единицы), $2^{8} - 1 = 255 = 11111111_2$ (восемь единиц). Это зеркальный факт к предыдущему и тоже постоянно используется.

Разбор задачи 1

Сколько значащих нулей в двоичной записи числа $132$?

Переведём: $132 = 128 + 4 = 2^{7} + 2^{2}$, значит $132 = 10000100_2$. В записи 8 разрядов, из них две единицы (в разрядах $2^7$ и $2^2$), остальные — нули. Нулей: $8 - 2 = 6$. «Значащие» здесь — все нули внутри записи, ведущих нулей у нормальной записи нет.

Разбор задачи 2

Сколько единиц в двоичной записи числа $2^{10} - 1$? По опорному факту это $1024 - 1 = 1023 = 1111111111_2$ — десять единиц. Никаких вычислений переводом не требуется, ответ читается прямо из формулы $2^{k}-1$.

Сколько чисел обладают свойством

Комбинаторная часть. Сколько существует $k$-разрядных двоичных чисел? Если разрешить ведущие нули, то каждый из $k$ разрядов независимо равен 0 или 1, и всего наборов

$$ 2^{k}. $$

Если же старший разряд обязан быть единицей (число именно $k$-значное, без ведущих нулей), то свободны только младшие $k-1$ разрядов, и таких чисел

$$ 2^{k-1}. $$

Разбор задачи 3

Сколько натуральных чисел от $1$ до $63$ включительно? Заметим, что $63 = 2^{6} - 1$. Значит, в этот диапазон попадают все ненулевые двоичные наборы длиной до 6 разрядов, и их ровно $2^{6} - 1 = 63$. Формула $2^{k}-1$ напрямую даёт количество натуральных чисел, не превосходящих $2^{k}-1$.

Разбор задачи 4

Сколько существует пятизначных двоичных чисел (старший разряд — единица)? По формуле $2^{k-1}$ при $k=5$ получаем $2^{4} = 16$. Это числа от $10000_2 = 16$ до $11111_2 = 31$, и их как раз $31 - 16 + 1 = 16$.

Как это работает

Проверим формулы и разборы программой: посчитаем разряды, единицы и нули у числа, а заодно убедимся, что в диапазоне $[16, 31]$ ровно 16 пятизначных двоичных чисел.

n = 132
bits = bin(n)[2:]          # двоичная запись без префикса 0b
ones = bits.count("1")
zeros = bits.count("0")
print(f"{n} = {bits}")
print("разрядов:", len(bits), "| единиц:", ones, "| нулей:", zeros)

# Сколько 5-значных двоичных чисел (старший бит = 1)
count = sum(1 for x in range(16, 32) if len(bin(x)[2:]) == 5)
print("Пятизначных двоичных чисел:", count, "= 2^4 =", 2 ** 4)

Вывод:

132 = 10000100
разрядов: 8 | единиц: 2 | нулей: 6
Пятизначных двоичных чисел: 16 = 2^4 = 16

Функция bin(n) даёт строку с префиксом 0b, поэтому мы отрезаем первые два символа срезом [2:]. Дальше count("1") и count("0") считают цифры. Результат точно совпал с ручным разбором: 8 разрядов, 2 единицы, 6 нулей, а пятизначных чисел ровно $2^4 = 16$.

Частые ошибки

• Считают ведущие нули. У натурального числа двоичная запись начинается с единицы; дописывать слева нули и считать их как «значащие» нельзя.
• Путают $2^{k}$ и $2^{k}-1$. Степень двойки — это единица и $k$ нулей, а на единицу меньше — это $k$ единиц подряд. Перепутав, ошибёшься в количестве разрядов.
• Забывают про границы диапазона. В задачах «от A до B» внимательно смотри, включаются ли концы; ошибка на единицу — типичная потеря балла.
• Считают $2^{k}$ вместо $2^{k-1}$ для чисел без ведущих нулей. Если старший разряд фиксирован единицей, свободных разрядов на один меньше.

Итоги

• Количество двоичных разрядов числа $N$ равно $\lfloor \log_2 N \rfloor + 1$; диапазон $k$-разрядных чисел — от $2^{k-1}$ до $2^{k}-1$.
• $2^{k}$ записывается как единица и $k$ нулей, а $2^{k}-1$ — как $k$ единиц подряд.
• Всего $k$-разрядных наборов $2^{k}$; чисел со старшим разрядом-единицей — $2^{k-1}$.
• Натуральных чисел, не превосходящих $2^{k}-1$, ровно $2^{k}-1$.
• Знание степеней двойки до $2^{10}=1024$ превращает перебор в устный счёт.