e-olymp 622. Единицы

Единицы

На уроках информатики вас, наверное, учили переводить числа из одних систем счисления в другие и выполнять другие подобные операции. Пришло время продемонстрировать эти знания. Найдите количество единиц в двоичной записи заданного числа.

Входные данные

Одно целое число $n$ $(0 ≤ n ≤ 2 \cdot 10^{9})$.

Выходные данные

Вывести количество единиц в двоичной записи числа $n$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
20 2
0 0
1 1
5 2
2000000000 13

Код программы

Решение задачи

Алгоритм заключается в последовательном делении заданного числа $n$ на $2$ и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц $k$ равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас $k$. Если остаток равен единице то мы получим $k+1$ что нам и требуется.

Условие задачи на e-olimp
Код решения ideon