Решение: Подсчёт единиц в двоичной записи
Ниже на пяти языках программирования записан алгоритм. Получив на вход число $x$, этот алгоритм печатает два числа: $L$ и $M$. В цикле алгоритм делит $x$ на 2 с отбрасыванием остатка, увеличивая $M$ на 1 при каждом делении, а $L$ — на 1, если остаток от деления на 2 равен 1. Найдите наименьшее число $x$, при вводе которого алгоритм печатает сначала 3, а потом 9.
Решение по шагам
4 шагаПри последовательном целочисленном делении положительного числа на 2 количество выполненных делений равно количеству разрядов в его двоичной записи. Поэтому $M=9$ означает, что число должно быть 9-разрядным.
Остаток при делении на 2 равен очередному двоичному разряду числа. Следовательно, $L=3$ означает, что в двоичной записи должно быть ровно три единицы.
Чтобы получить наименьшее 9-разрядное число с тремя единицами, ставим единицу в старшем разряде и две единицы в самых младших разрядах:
Переводим это число в десятичную систему:
Где здесь ошибаются
Путают количество итераций с количеством единиц в двоичной записи.
Выбирают не минимальное 9-разрядное число с тремя единицами.
Забывают, что старший двоичный разряд должен быть равен 1.