Единицы
На уроках информатики вас, наверное, учили переводить числа из одних систем счисления в другие и выполнять другие подобные операции. Пришло время продемонстрировать эти знания. Найдите количество единиц в двоичной записи заданного числа.
Входные данные
Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].
Выходные данные
Вывести количество единиц в двоичной записи числа [latex]n[/latex].
Тесты
| Входные данные | Выходные данные |
|---|---|
| 20 | 2 |
| 0 | 0 |
| 1 | 1 |
| 5 | 2 |
| 2000000000 | 13 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { int k=0, n; cin >> n; while (n > 0){ k += (n % 2); n = n / 2; } cout << k; return 0; } |
Решение задачи
Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.
Условие задачи на e-olimp
Код решения ideon
Теперь хорошо