Как определить является ли число степенью двойки

Как проверить, является ли заданное число степенью двойки?

Как проверить, является ли заданное число степенью двойки. Например: 256 = 2^8 8 = 2^3 Как можно это осуществить в C#?

Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 21 фев 2021 в 12:19
37 1 1 золотой знак 2 2 серебряных знака 5 5 бронзовых знаков

Степень двойки делается простым регистровым сдвигом 2
21 фев 2021 в 12:33
Ага, либо воспользоваться школьными знаниями о логарифмах: взять логарифм по основанию два.
21 фев 2021 в 12:38
21 фев 2021 в 12:49
Для целых, как и в любом С-подобном языке — if ((x & (x — 1)) == 0) < // это степень двойки >
21 фев 2021 в 13:21
Хороший простой вопрос. Не вижу смысла минусовать или ставить флаг за закрытие ¯_(ヅ)_/¯
21 фев 2021 в 13:22

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

n > 0 && (n & (n - 1)) == 0 

Там по ссылке ещё много всяких битовых трюков.

Как это трюк работает? А вот как. Запишем число n в двоичной системе, и рассмотрим самую правую единицу в двоичном представлении числа n . У числа n — 1 будет на месте этой единицы ноль, а справа от него единицы:

n : xxxxxx1000 1 : 0000000001 n - 1 : xxxxxx0111 

а остальные двоичные цифры (обозначенные как x ) не поменяются. Поэтому после операции & получится вот что:

n&(n-1): xxxxxx0000 

Это число будет равно нулю тогда и только когда, когда все xxxxxx равны нулю. Единственный случай, где наше соображение не проходит — число 0: там нету «самой правой» единицы вовсе, так что это случай приходится рассматривать отдельно.

Проверить, является ли число степенью числа 8 или нет

Учитывая положительное число, проверьте, является ли оно степенью числа 8 или нет.

Подход 1

Простое решение состоит в том, чтобы вычислить log₈n на заданный номер 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)₁₆ = (10110110110110110110110110110110)₂

Ниже приведена реализация этой идеи на C++, Java и Python:

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

Формулировка. Дано натуральное число 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, иначе.

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

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

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

Биты, конъюнкция которых даст 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.

Код:

1. program PowerOfTwo;
2. var
3. n: integer;
4. begin
5. readln(n);
6. while n > 1 do begin
7. if n mod 2 = 1 then break;
8. n := n div 2
9. end;
10. writeln(n = 1)
11. end.

Определить, является ли данное число степенью двойки

Является ли данное число степенью двойки?
Формат входных данных
Вводится число.
Формат выходных данных
Напечатать YES, если оно является степенью двойки, Напечатать YES, если оно является степенью двойки, NO – иначе.
Примеры
input.txt output.txt
8 YES
22 NO

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Определить, является ли число степенью двойки
Такая проблема: в проге мне нужно задать количество чисел которые я введу (т.е создать массив под.

Определить, является ли число степенью двойки
По заданному положительному числу n < 2^64 определить, является ли оно степенью двойки. Решение.

Определить является ли число степенью двойки
Стоит задача Ввести число. Определить является ли оно степенью 2 (число 16 является, а 22 нет)

Определить, является ли число степенью двойки (циклы)
Вводится число. Определить, является ли оно степенью двойки. ( с помощью цикла) Думала.

3952 / 1807 / 184
Регистрация: 21.11.2009
Сообщений: 2,540
varkich, а что у вас не получается?
Определить, является ли число степенью двойки, очень просто:

1 2 3 4 5 6 7 8 9

bool PowerOfTwo(int &Value) { int InitValue = 1; while (InitValue  Value) InitValue *= 2; if (InitValue == Value) return true; return false; }

О том, как прикрутить чтение из файла, материала уйма. Пару строчек кода.

8864 / 6641 / 907
Регистрация: 14.02.2011
Сообщений: 23,372

Сообщение от MikeSoft

число степенью двойки, очень просто:
даже еще проще

1 2 3 4 5 6 7 8 9 10 11 12 13

bool VerifyDecimal(int value) { if(value0) return false; while((value%2)==0) { if((value/=2)==1) return true; } return false; }

1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
Где-то видел примерно такой код

1 2 3 4

bool is_exp_of_2(int n) { return ( n & (n - 1) ) == 0; }

47 / 46 / 26
Регистрация: 16.06.2012
Сообщений: 177

Сообщение от diagon

Где-то видел примерно такой код

1 2 3 4

bool is_exp_of_2(int n) { return ( n & (n - 1) ) == 0; }

Работает, если степень

is_exp_of_2(pow(2, 31)); // 0 is_exp_of_2(8589934591); // 1

is_exp_of_2(pow(2, 31)); // 0 is_exp_of_2(8589934591); // 1

1 2 3 4

bool is_exp_of_2(int n) { return ( n & (n - 1) ) == 0; }

1 2 3 4

bool is_exp_of_2(int n) { return ( n & (n - 1) ) == 0; }

1 2 3 4

int deg_of_2(long x) { return (x  0) ? 0 : (x & (x-1)) == 0; }

1 2 3 4 5 6 7 8

bool isPowerOfTwo(unsigned int x) { if (x == 0) { return false; } for (; x % 2 == 0; x /= 2); return (x == 1); }