зачем нужно количество битов?

Question

Я нашел проблему в codeforces 579 / A:

Вы любитель бактерий. Вы хотите поднять некоторые бактерии в коробке.

Изначально коробка пуста. Каждое утро вы можете положить любое количество бактерии в коробку. И каждую ночь каждая бактерия в коробке будет разделить на две бактерии. Вы надеетесь увидеть ровно x бактерий в коробке в какой-то момент.

Какое минимальное количество бактерий нужно положить в коробку? через те дни?

Input Единственная строка, содержащая одно целое число x (1 ≤ x ≤ 109).

Выходные данные Единственная строка, содержащая одно целое число: ответ.

вход: 5 выход: 2 Примечание: для первого образца мы можем добавить один бактерия в коробке в первый день утром и на третье утро в коробке будет 4 бактерии. Теперь мы ставим еще один результат 5 в коробке. В процессе мы добавили 2 бактерии, поэтому ответ 2.

Мой вопрос: почему для решения этой проблемы используется число бит?

Answer 1

Каждый раз, когда вы вводите 1 бактерию, количество микробов будет через 2 ⁿ через n дней. Чтобы достичь числа N, вы должны увидеть его степень 2.

5 равно 2 ² + 2 ⁰ или 4 + 1.

, то есть в двоичном виде 5 равно 101, что является вашим планом инъекции!

Чтобы достичь 5,

• (1) добавить 1 бактерию
• (0) через день добавить 0 бактерий и
• (1) через день добавьте 1 бактерию

Максимально допустимое число - 109 или 1101101 в двоичном виде. Чтобы достичь 109, добавьте 1, затем 1 через день, затем 0, затем 1 ...

слева

• первый 1 даст 2 ⁶ через 6 дней (64)
• второй 1 даст 2 ⁵ через 5 дней (32)
• третья 1 даст 2 ³ через 3 дня (8)
• тогда ... 5 (4 + 1)

Наконец, чтобы узнать, сколько бактерий вам нужно ввести, просто посчитайте число 1 в целевом двоичном числе. То есть количество битов установлено.

Вы можете задаться вопросом, почему не вводить больше 1 в какой-то день? Поскольку проблема не ограничена количеством дней, вы будете «использовать» меньше бактерий, позволяя им размножаться. Это сила возведения в степень!

Answer 2

Любые бактерии, помещенные в данный день, становятся бактериями раз, два, четыре, восемь и так далее. Например, не станет трех. Это всегда степень двойки. Итак, если желаемое число не является степенью двойки, вам нужно сделать это как сумму степеней двойки. Минимальное количество добавлений в такой сумме таково, что никакая степень двойки не повторяется, каждая степень используется 0 или 1 раз. Представление числа как такой суммы степеней двух в основном преобразует его в двоичное представление, а подсчет использованных степеней двух - это двоичные цифры, установленные в единицу.