Проверка, является ли число степенью двойки, с помощью одной побитовой операции
Допустим, дано положительное целое число
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 и n-1, то самый значимый бит в их двоичном представлении сохранится только в том случае, если у n есть другие единицы помимо самого значимого бита. Когда n — это степень двойки, в его двоичном представлении лишь одна единица, и при вычитании 1 у n-1 этот бит становится 0, а остальные биты — 1.
В иных случаях (как 6, 67, 144 и т.д.), двоичное представление содержит несколько единиц. При вычитании 1 у такого числа самый значимый бит не исчезает.Входные данные
В первой строке входных данных содержится одно целое число
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