Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

Задача № 39. Проверить, является ли натуральное число степенью двойки 
Формулировка. Дано натуральное число n. Проверить, представляет ли оно собой натураль-
ную степень числа 2. 
Решение. Проще говоря, нам нужно ответить на вопрос: можно ли возвести число 2 в какую-
либо натуральную степень (или в нулевую степень, так как 2
0
= 1)
, чтобы получилось число n? 
Вообще, для решения этой задачи существует достаточно красивое равенство, выполняюще-
еся для всех натуральных степеней числа 2, позволяющее получить ответ с помощью одной един-
ственной логической побитовой операции: 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
48 
n and (n – 1) = 0 
Обозначим его как (1). 
Дело в том, что натуральная степень числа 2 с показателем p в двоичном виде всегда пред-
ставляется как единица с p нулями справа. Это происходит потому, что двоичная запись этого числа 
в десятичном виде представляется как 1 * 2
p
+ 0 * 2
p–1
+ ... + 0 * 2
1
+ 0 * 2
0
, 
где все пропущенные 
слагаемые имеют коэффициент 0, и из этой записи легко восстановить двоичное представление: 
10...00, здесь нулей всего p. Поэтому если мы отнимем от любой степени двойки 1, то получим 
число 1...11, где всего p единиц (точнее говоря, это будет число 01...11). В итоге, если мы применим 
к этим двум числа побитовую конъюнкцию, то всегда будем получать результирующее число, рав-
ное 0. 
Примечание: побитовая конъюнкция – это бинарная операция, которая эквивалента обычной 
конъюнкции, примененной к двоичным разрядам операндов (двух исходных чисел), стоящим на 
одинаковых позициях в двоичных представлениях этих чисел. При этом результатом применения 
побитовой конъюнкции является некое результирующее число, значение соответствующих битов 
которого зависит от значений битов исходных чисел: в соответствующем разряде будет находиться 
1 тогда и только тогда, когда на этих позициях в обоих исходных числах стояли единичные биты, и 
0, иначе. 
Пример: выполним поразрядную конъюнкцию двоичных чисел 011001
2
и 101011
2 
(при этом 
выпишем их так, чтобы соответствующие двоичные разряды стояли друг под другом): 
Первый операнд:
01
1
00
1
2
Второй операнд:
10
1
01
1
2
Результат: 001001
2
Биты, конъюнкция которых даст 0, выделены красным цветом, а те, конъюнкция которых даст 
1 – 
синим. 
Так как 1-й разряд слева у первого числа равен 0, а у второго – 1, то в соответствующий первый 
разряд результата идет бит 0. 2-е разряды, соответственно, равны 1 и 0, и в результат снова идет бит 
0. 3-
и разряды у обоих чисел равны 1 (выделены синим цветом), поэтому в 3-й разряд результата 
идет 1 и так далее. 
Кстати, наша формула (1) пропускает число 0 в качестве степени двойки. Так как компиляторы 
языка Pascal (гарантированно называются Borland Delphi 7 и PascalABC) реализуют числовые типы 
данных в виде кольцевых отрезков (то есть, например, в типе byte после числа 255 следует число 0, 
а перед числом 0 – число 255), то в любом таком типе выражение (0 – 1) имеет некоторое ненулевое 
битовое представление (так как нулевое битовое представление имеет лишь число 0), а побитовая 
конъюнкция числа 0 и любого другого числа дает в результате число 0. 
Вообще, так как нам данное нам n является натуральным числом, число 0 вводиться не будет. 
Однако покажем, как отсечь 0 при проверке числа по формуле (1): можно осуществить проверку 
введенного числа на равенство нулю, и в случае равенства заменить его на какое-либо другое число, 
заведомо не являющееся степенью двойки, чтобы условие формулы (1) отработало правильно: 
if n = 0 then n := 3; 
Вообще, формула (1) требует доказательства в обе стороны: мы лишь доказали, что если n 
является степенью двойки, то есть n = 2
p
(где p – любое натуральное число или 0), то выражение n