Задача № 39. Проверить, является ли натуральное число степенью двойки

Формулировка. Дано натуральное число n. Проверить, представляет ли оно собой натуральную степень числа 2.

Решение. Проще говоря, нам нужно ответить на вопрос: можно ли возвести число 2 в какую-либо натуральную степень (или в нулевую степень, так как 2⁰ = 1), чтобы получилось число n?

Вообще, для решения этой задачи существует достаточно красивое равенство, выполняющееся для всех натуральных степеней числа 2, позволяющее получить ответ с помощью одной единственной логической побитовой операции:

n and (n – 1) = 0

Обозначим его как (1).

Дело в том, что натуральная степень числа 2 с показателем p в двоичном виде всегда представляется как единица с p нулями справа. Это происходит потому, что двоичная запись этого числа в десятичном виде представляется как 1 * 2^p + 0 * 2^p–1 +... + 0 * 2¹ + 0 * 2⁰, где все пропущенные слагаемые имеют коэффициент 0, и из этой записи легко восстановить двоичное представление: 10...00, здесь нулей всего p. Поэтому если мы отнимем от любой степени двойки 1, то получим число 1...11, где всего p единиц (точнее говоря, это будет число 01...11). В итоге, если мы применим к этим двум числа побитовую конъюнкцию, то всегда будем получать результирующее число, равное 0.

Примечание: побитовая конъюнкция – это бинарная операция, которая эквивалента обычной конъюнкции, примененной к двоичным разрядам операндов (двух исходных чисел), стоящим на одинаковых позициях в двоичных представлениях этих чисел. При этом результатом применения побитовой конъюнкции является некое результирующее число, значение соответствующих битов которого зависит от значений битов исходных чисел: в соответствующем разряде будет находиться 1 тогда и только тогда, когда на этих позициях в обоих исходных числах стояли единичные биты, и 0, иначе.

Пример: выполним поразрядную конъюнкцию двоичных чисел 011001₂ и 101011₂ (при этом выпишем их так, чтобы соответствующие двоичные разряды стояли друг под другом):

Первый операнд: 011001₂

Второй операнд: 101011₂

Результат: 001001₂

Биты, конъюнкция которых даст 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 and (n – 1) гарантированно дает результат 0. Покажем это схематически еще раз:

Первый операнд: 100...00

Второй операнд: 011...11

Результат: 000...00

Однако мы также должны доказать, что никакое другое число n, кроме как степень двойки, не может дать 0 в результате выполнения операции n and (n – 1). Однако мы примем это утверждение без доказательства. В итоге тело программки может выглядеть так (для натурального n, которое также может быть нулем):

readln(n);

if n = 0 then n:= 3;

writeln(n and (n – 1) = 0);

Однако мы в качестве основного решения возьмем более простую идею: пусть данное число n является степенью двойки. Следовательно, его можно представить так: 2 ^p = 1 * 2 * 2 *... * 2 (здесь ровно p двоек). Разделив это выражение на 2 определенное количество раз, в результате мы получим число 1.

Если же число n не является степенью двойки, то на некотором шаге мы получим остаток при делении на 2. В связи с этим возникает алгоритм:

1) Вводим n;

2) В цикле с предусловием n > 1 работаем с n:

1. Если остаток от деления n на 2 равен 1 (n mod 2 = 1), то выходим из цикла;

2. Делим n на 2 (n:= n div 2);

3) Выводим на экран значение выражения n = 1 (если цикл завершился, то это условие истинно и n – степень двойки, а если нет – то на каком-то шаге мы получили остаток при делении на 2 и вышли через break);

Даже если ввести n, равное 0, то программа выдаст правильный ответ, так как не будет осуществлен вход в цикл (2) и на шаге (3) будет выведено значение выражения 0 = 1, равное false.

Код: