Проверка, является ли число степенью двойки, с помощью одной побитовой операции
Допустим, дано положительное целое число n. Нужно определить, является ли оно степенью двойки. Это можно сделать, используя всего одну побитовую операцию. Если рассмотреть двоичное представление числа, которое является степенью двойки, то в нем присутствует ровно одна 1, а все остальные биты равны 0.
Число 2^n | Двоичное представление |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Случайное число | Двоичное представление |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Это следует из определения двоичного представления. Каждая позиция с единицей вносит вклад соответствующей степени двойки (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Поскольку в числе, являющемся степенью двойки, есть только одна единица, других степеней двойки в сумме быть не может. Следовательно, задача сводится к тому, чтобы проверить, есть ли в двоичном представлении n ровно одна 1.
Простой способ сделать это — выполнить побитовое & между n и n-1. Если результат равен 0 ⇒ число является степенью двойки.
Для любого числа, которое не является степенью двойки, результат n & (n-1) будет отличен от 0:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
Зато для степеней двойки это всегда 0:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Входные данные
В первой строке входных данных содержится одно целое число n (2 ≤ n ≤ ).
Выходные данные
Программа должна вывести Yes, если n является степенью двойки, и No в противном случае.
Примеры
Input | Output |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB