Проверить, является ли число степенью числа 8 или нет
Учитывая положительное число, проверьте, является ли оно степенью числа 8 или нет.
Подход 1
Простое решение состоит в том, чтобы вычислить log8n на заданный номер n . Если он возвращает целочисленное значение, то мы можем сказать, что число является степенью числа 8.
Реализацию можно увидеть ниже на C++, Java и Python:
C++
using namespace std ;
// Возвращает true, если `n` является степенью числа 8
bool checkPowerOf8 ( unsigned n )
// найти `log8(n)`
double i = log ( n ) / log ( 8 ) ;
// вернуть true, если `log8(n)` является целым числом
return i — trunc ( i ) < 0.000001 ;
unsigned n = 512 * 64 ;
if ( checkPowerOf8 ( n ) ) <
cout << n << " is a power of 8" ;
cout << n << " is not a power of 8" ;
результат:
32768 is a power of 8
Java
class Main
// Возвращает true, если `n` является степенью числа 8
public static boolean checkPowerOf8 ( int n )
// найти `log8(n)`
double i = Math . log ( n ) / Math . log ( 8 ) ;
// вернуть true, если `log8(n)` является целым числом
return i — Math . floor ( i ) < 0.000001 ;
public static void main ( String [ ] args )
int n = 512 * 64 ;
if ( checkPowerOf8 ( n ) ) <
System . out . println ( n + " is a power of 8" ) ;
System . out . println ( n + " is not a power of 8" ) ;
результат:
32768 is a power of 8
Python
from math import floor , log
# Возвращает true, если `n` является степенью числа 8.
def checkPowerOf8 ( n ) :
# найти `log8(n)`
i = log ( n ) / log ( 8 )
# возвращает true, если `log8(n)` является целым числом
return i — floor ( i ) < 0.000001
if __name__ == '__main__' :
n = 512 * 64
if checkPowerOf8 ( n ) :
print ( n , 'is a power of 8' )
print ( n , 'is not a power of 8' )
результат:
32768 is a power of 8
Подход 2
Данный номер n является степенью числа 8, если это степень числа 2, и его единственный установленный бит присутствует в (0, 3, 6, … , 30) должность.
Как проверить степень двойки?
Мы также можем выражение (n & -n) == n чтобы проверить, является ли положительное целое число степенью 2 или нет. Для получения более подробной информации см. эта почта.
Как проверить положение установленного бита?
Чтобы проверить позицию установленного бита, мы можем использовать 0xB6DB6DB6 как маска. Маска 0xB6DB6DB6 всего 0 (0, 3, 6, … ,30) должность. Итак, если выражение !(n & 0xB6DB6DB6) верно, позиция установленного бита в n даже.
(0xB6DB6DB6)16 = (10110110110110110110110110110110)2
Ниже приведена реализация этой идеи на C++, Java и Python:
Является ли число степенью двойки?
Прошу помочь найти ошибку. Смотрю на код, рассуждаю, вроде всё должно работать. Варианты с функциями и for не рассматриваются. Хочу разобраться именно в этом примере.
1 2 3 4 5 6 7 8 9 10 11 12
x=int(input()) if x%2==0: i=0 while 2**ix: if 2**i==x: print(i) elif 2**i>x: print('НЕТ') else: i=i+1 else: print('НЕТ')
Лучшие ответы ( 3 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Проверить, является ли заданное натуральное число степенью двойки
Здравствуйте, форумчане. Есть следующее задание: Дано натуральное число N. Выведите слово.
Выведите слово YES, если число N является точной степенью двойки
Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или.
Написать функцию power_of_two, которая определяет является ли заданное число степенью двойки
# Написать функцию power_of_two, которая определяет является ли заданное число степенью двойки. #.
Проверить является ли число степенью тройки
def is_power_three(n): print(n) if n == 1: return ‘Є степенем трійки’ if n.
Проверить, является ли число a степенью числа b
Решите задачу одним циклом while, допускается применение условных операторов. Задано два числа a.
Проверить, является ли натуральное число степенью двойки
Формулировка. Дано натуральное число n. Проверить, представляет ли оно собой натуральную степень числа 2.
Решение. Проще говоря, нам нужно ответить на вопрос: можно ли возвести число 2 в какую-либо натуральную степень (или в нулевую степень, так как 2 0 = 1), чтобы получилось число n?
Вообще, для решения этой задачи существует достаточно красивое равенство, выполняющееся для всех натуральных степеней числа 2, позволяющее получить ответ с помощью одной единственной логической побитовой операции:
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, иначе.
Пример: выполним поразрядную конъюнкцию двоичных чисел 0110012 и 1010112 (при этом выпишем их так, чтобы соответствующие двоичные разряды стояли друг под другом):
Первый операнд: 0110012
Второй операнд: 1010112
Биты, конъюнкция которых даст 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
Однако мы также должны доказать, что никакое другое число n, кроме как степень двойки, не может дать 0 в результате выполнения операции n and (n – 1). Однако мы примем это утверждение без доказательства. В итоге тело программки может выглядеть так (для натурального 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:
3) Выводим на экран значение выражения n = 1 (если цикл завершился, то это условие истинно и n – степень двойки, а если нет – то на каком-то шаге мы получили остаток при делении на 2 и вышли через break);
Даже если ввести n, равное 0, то программа выдаст правильный ответ, так как не будет осуществлен вход в цикл (2) и на шаге (3) будет выведено значение выражения 0 = 1, равное false.
Код:
- program PowerOfTwo;
- var
- n: integer;
- begin
- readln(n);
- while n > 1 do begin
- if n mod 2 = 1 then break;
- n := n div 2
- end;
- writeln(n = 1)
- end.
Цикл while
Цикл while (“пока”) позволяет выполнить одну и ту же последовательность действий, пока проверяемое условие истинно. Условие записывается до тела цикла и проверяется до выполнения тела цикла. Как правило, цикл while используется, когда невозможно определить точное значение количества проходов исполнения цикла.
Синтаксис цикла while в простейшем случае выглядит так:
while условие: блок инструкций
При выполнении цикла while сначала проверяется условие. Если оно ложно, то выполнение цикла прекращается и управление передается на следующую инструкцию после тела цикла while . Если условие истинно, то выполняется инструкция, после чего условие проверяется снова и снова выполняется инструкция. Так продолжается до тех пор, пока условие будет истинно. Как только условие станет ложно, работа цикла завершится и управление передастся следующей инструкции после цикла.
Например, следующий фрагмент программы напечатает на экран квадраты всех целых чисел от 1 до 10. Видно, что цикл while может заменять цикл for . in range(. ) :
i = 1 while iВ этом примере переменная i внутри цикла изменяется от 1 до 10. Такая переменная, значение которой меняется с каждым новым проходом цикла, называется счетчиком. Заметим, что после выполнения этого фрагмента значение переменной i будет равно 11 , поскольку именно при i==11 условие i
Вот еще один пример использования цикла while для определения количества цифр натурального числа n :
n = int(input()) length = 0 while n > 0: n //= 10 length += 1В этом цикле мы отбрасываем по одной цифре числа, начиная с конца, что эквивалентно целочисленному делению на 10 ( n //= 10 ), при этом считаем в переменной length , сколько раз это было сделано.
В языке Питон есть и другой способ решения этой задачи: .
Инструкции управления циклом
После тела цикла можно написать слово else: и после него блок операций, который будет выполнен один раз после окончания цикла, когда проверяемое условие станет неверно:
i = 1 while iКазалось бы, никакого смысла в этом нет, ведь эту же инструкцию можно просто написать после окончания цикла. Смысл появляется только вместе с инструкцией break , использование которой внутри цикла приводит к немедленному прекращению цикла, и при этом не исполняется ветка else . Разумеется, инструкцию break осмыленно вызывать только из инструкции if , то есть она должна выполняться только при выполнении какого-то особенного условия.
Другая инструкция управления циклом — continue (продолжение цикла). Если эта инструкция встречается где-то посередине цикла, то пропускаются все оставшиеся инструкции до конца цикла, и исполнение цикла продолжается со следующей итерации.
Инструкции break , continue и ветка else: можно использовать и внутри цикла for . Тем не менее, увлечение инструкциями break и continue не поощряется, если можно обойтись без их использования. Вот типичный пример плохого использования инструкции break .
while True: length += 1 n //= 10 if n == 0: break