Задача
Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:
- читает натуральное число $n$,
- вычисляет позиции $1$ в двоичном представлении $n$,
- выводит результат.
Входные данные
В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.
Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.
Выходные данные
Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.
Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.
Тесты
|
Входные данные
|
Выходные данные |
| $3$ $17$ $7$ $5$ |
$0$ $4$ $0$ $1$ $2$ $0$ $2$ |
| $4$ $1945$ $1337$ $1000000$ $999999$ |
$0$ $3$ $4$ $7$ $8$ $9$ $10$ $0$ $3$ $4$ $5$ $8$ $10$ $6$ $9$ $14$ $16$ $17$ $18$ $19$ $0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$ |
| $10$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ |
$0$ $1$ $0$ $1$ $2$ $0$ $2$ $1$ $2$ $0$ $1$ $2$ $3$ $0$ $3$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); int d; d = Integer.parseInt(params1[0]); for (int j = 0; j < d; ++j){ String[] params2 = bufferedReader.readLine().split(" "); int n; boolean w = false; n = Integer.parseInt(params2[0]); for (int i = 0; n>0; ++i){ if (n % 2 == 1){ if(w){ System.out.print(" "); } w = true; System.out.print(i); } n /= 2; } System.out.print("\n"); } } } |
Решение задачи
Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com