Единицы
На уроках информатики вас, наверное, учили переводить числа из одних систем счисления в другие и выполнять другие подобные операции. Пришло время продемонстрировать эти знания. Найдите количество единиц в двоичной записи заданного числа.
Входные данные
Одно целое число $n$ $(0 ≤ n ≤ 2 \cdot 10^{9})$.
Выходные данные
Вывести количество единиц в двоичной записи числа $n$.
Тесты
| ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 20 | 2 |
| 0 | 0 |
| 1 | 1 |
| 5 | 2 |
| 2000000000 | 13 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { int k=0, n; Scanner in = new Scanner(System.in); n = in.nextInt(); while (n > 0){ k += (n % 2); n = n / 2; } System.out.print(k); } } |
Решение задачи
Алгоритм заключается в последовательном делении заданного числа $n$ на $2$ и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц $k$ равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас $k$. Если остаток равен единице то мы получим $k+1$ что нам и требуется.