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

and (n – 1) 
гарантированно дает результат 0. Покажем это схематически еще раз: 
Первый операнд:
100...00 
Второй операнд:
011...11 
Результат: 000...00 
Однако мы также должны доказать, что никакое другое число n, кроме как степень двойки, не 
может дать 0 в результате выполнения операции n and (n – 1). Однако мы примем это утверждение 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
49 
без доказательства. В итоге тело программки может выглядеть так (для натурального 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. 
Код: 
1.
program PowerOfTwo; 
2.
3.
var 
4.
n: integer; 
5.
6.
begin 
7.
readln(n); 
8.
while n > 1 do begin 
9.
if n mod 2 = 1 then break; 
10.
n := n div 2 
11.
end; 
12.
writeln(n = 1) 
13.
end.