Как проверить, является ли число мощностью 2
Сегодня мне нужен простой алгоритм для проверки того, является ли число мощностью 2.
Алгоритм должен быть:
- Простой
- Корректно для любого значения
ulong.
Я придумал этот простой алгоритм:
private bool IsPowerOfTwo(ulong number)
{
if (number == 0)
return false;
for (ulong power = 1; power > 0; power = power << 1)
{
// This for loop used shifting for powers of 2, meaning
// that the value will become 0 after the last shift
// (from binary 1000...0000 to 0000...0000) then, the 'for'
// loop will break out.
if (power == number)
return true;
if (power > number)
return false;
}
return false;
}
Но потом я подумал, как насчет проверки того, является ли log2 x точно круглым числом? Но когда я проверил 2 ^ 63 + 1, Math.Log вернул ровно 63 из-за округления. Итак, я проверил, соответствует ли 2 мощности 63 исходному числу, и это потому, что вычисление выполняется в double, а не в точном числе:
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
Это возвращало true для данного неправильного значения: 9223372036854775809.
Есть ли лучший алгоритм?
Ответы
Ответ 1
Там простой трюк для этой проблемы:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
Обратите внимание: эта функция будет сообщать значение true для 0, что не является значением 2. Если вы хотите исключить это, вот как:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
объяснение
Прежде всего, побитовый двоичный оператор из определения MSDN:
Бинарные и операторы предопределены для интегральных типов и bool. Для интегральных типов & вычисляет логическое побитовое И его операндов. Для операндов bool и вычисляет логический AND своих операндов; то есть результат верен тогда и только тогда, когда оба его операнда верны.
Теперь давайте посмотрим, как все это происходит:
Функция возвращает boolean (true/false) и принимает один входящий параметр типа unsigned long (x, в этом случае). Для простоты предположим, что кто-то прошел значение 4 и назвал функцию так:
bool b = IsPowerOfTwo(4)
Теперь мы заменяем каждое вхождение x на 4:
return (4 != 0) && ((4 & (4-1)) == 0);
Ну, мы уже знаем, что 4! = 0 оценивает истину, пока что так хорошо. Но что насчет:
((4 & (4-1)) == 0)
Это, конечно же, означает:
((4 & 3) == 0)
Но что такое 4&3?
Бинарное представление 4 равно 100, а двоичное представление 3 равно 011 (помните, что & берет двоичное представление этих чисел). Таким образом, мы имеем:
100 = 4
011 = 3
Представьте, что эти значения сложены как элементарное дополнение. Оператор & говорит, что если оба значения равны 1, то результат равен 1, иначе оно равно 0. Итак, 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0 и 0 & 1 = 0. Итак, мы делаем математику:
100
011
----
000
Результат - просто 0. Итак, мы вернемся и посмотрим, что теперь означает наш оператор return:
return (4 != 0) && ((4 & 3) == 0);
Это переводит теперь:
return true && (0 == 0);
return true && true;
Мы все знаем, что true && true просто true, и это показывает, что для нашего примера 4 - это сила 2.
Ответ 2
Некоторые сайты, которые документируют и объясняют этот и другие хитрые взломы:
И их дедушка, книга "Восхищение Хакера" Генри Уоррена-младшего:
Как объясняет страница Шона Андерсона, выражение ((x & (x - 1)) == 0) неверно указывает, что 0 - это степень 2. Он предлагает использовать:
(!(x & (x - 1)) && x)
чтобы исправить эту проблему.
Ответ 3
return (i & -i) == i
Ответ 4
bool IsPowerOfTwo(ulong x)
{
return x > 0 && (x & (x - 1)) == 0;
}
Ответ 5
Я недавно написал статью об этом в http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/. Он охватывает подсчет бит, правильное использование логарифмов, классическую проверку "x &! (X и (x - 1))" и другие.
Ответ 6
Здесь простое решение C++:
bool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}
Ответ 7
После публикации вопроса я подумал о следующем решении:
Нам нужно проверить, является ли одна из двоичных цифр одной. Поэтому мы просто сдвигаем число справа на одну цифру за раз и возвращаем true, если оно равно 1. Если в какой-либо точке мы получаем нечетное число ((number & 1) == 1), мы знаем, что результат false. Это подтвердилось (с использованием эталона) несколько быстрее, чем исходный метод для (больших) значений истины и намного быстрее для ложных или малых значений.
private static bool IsPowerOfTwo(ulong number)
{
while (number != 0)
{
if (number == 1)
return true;
if ((number & 1) == 1)
// number is an odd number and not 1 - so it not a power of two.
return false;
number = number >> 1;
}
return false;
}
Конечно, решение Грега намного лучше.
Ответ 8
bool IsPowerOfTwo(int n)
{
if (n > 1)
{
while (n%2 == 0)
{
n >>= 1;
}
}
return n == 1;
}
И вот общий алгоритм для выяснения, является ли число степенью другого числа.
bool IsPowerOf(int n,int b)
{
if (n > 1)
{
while (n % b == 0)
{
n /= b;
}
}
return n == 1;
}
Ответ 9
Следующее дополнение к принятому ответу может быть полезно для некоторых людей:
Степень двойки, выраженная в двоичном виде, всегда будет выглядеть как 1, за которым следуют n нулей, где n больше или равно 0. Пример:
Decimal Binary
1 1 (1 followed by 0 zero)
2 10 (1 followed by 1 zero)
4 100 (1 followed by 2 zeroes)
8 1000 (1 followed by 3 zeroes)
. .
. .
. .
и так далее.
Когда мы вычитаем 1 из таких чисел, они становятся 0, за которыми следуют n и снова n такое же, как указано выше. Пример:
Decimal Binary
1 - 1 = 0 0 (0 followed by 0 one)
2 - 1 = 1 01 (0 followed by 1 one)
4 - 1 = 3 011 (0 followed by 2 ones)
8 - 1 = 7 0111 (0 followed by 3 ones)
. .
. .
. .
и так далее.
Подойдя к сути
Что происходит, когда мы делаем побитовое И для числа x, которое является степенью 2, а x - 1?
Один из x выравнивается с нулем x - 1 и все нули x выравниваются с нулями x - 1, в результате чего побитовое И приводит к 0. И вот как мы получили ответ из одной строки, упомянутый выше: право.
Дальнейшее добавление к красоте принятого ответа выше -
Итак, теперь у нас есть недвижимость:
Когда мы вычтем 1 из любого числа, то в двоичном представлении крайний правый 1 станет 0, а все нули до этого самого правого 1 станут 1
Одним из удивительных применений этого свойства является выяснение - сколько единиц присутствует в двоичном представлении данного числа? Короткий и приятный код для этого целого числа x:
byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);
Другой аспект чисел, который может быть доказан из концепции, объясненной выше: "Может ли каждое положительное число быть представлено как сумма степеней 2?" ,
Да, каждое положительное число может быть представлено как сумма степеней 2. Для любого числа возьмите его двоичное представление. Пример: взять номер 117.
The binary representation of 117 is 1110101
Because 1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have 117 = 64 + 32 + 16 + 0 + 4 + 0 + 1
Ответ 10
bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;
Ответ 11
Найти, если заданное число является степенью 2.
#include <math.h>
int main(void)
{
int n,logval,powval;
printf("Enter a number to find whether it is s power of 2\n");
scanf("%d",&n);
logval=log(n)/log(2);
powval=pow(2,logval);
if(powval==n)
printf("The number is a power of 2");
else
printf("The number is not a power of 2");
getch();
return 0;
}
Ответ 12
bool isPowerOfTwo(int x_)
{
register int bitpos, bitpos2;
asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
return bitpos > 0 && bitpos == bitpos2;
}
Ответ 13
int isPowerOfTwo(unsigned int x)
{
return ((x != 0) && ((x & (~x + 1)) == x));
}
Это очень быстро. Для проверки всех 2 ^ 32 целых чисел требуется около 6 минут и 43 секунды.
Ответ 14
return ((x != 0) && !(x & (x - 1)));
Если x - это мощность двух, то его 1-й бит находится в положении n. Это означает, что x – 1 имеет 0 в позиции n. Чтобы понять, почему, вспомните, как работает двоичное вычитание. При вычитании 1 из x заимствование распространяется до положения n; бит n становится 0, а все нижние биты становятся равными 1. Теперь, поскольку x не имеет 1 бита, общего с x – 1, x & (x – 1) равно 0, а !(x & (x – 1)) - true.
Ответ 15
Число - это значение 2, если оно содержит только 1 бит набора. Мы можем использовать это свойство и общую функцию countSetBits, чтобы определить, имеет ли число значение 2 или нет.
Это программа на С++:
int countSetBits(int n)
{
int c = 0;
while(n)
{
c += 1;
n = n & (n-1);
}
return c;
}
bool isPowerOfTwo(int n)
{
return (countSetBits(n)==1);
}
int main()
{
int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
return 0;
}
Нам не нужно явно проверять, что 0 является степенью 2, так как он также возвращает False для 0.
OUTPUT
Num:0 Set Bits:0 is power of two: 0
Num:1 Set Bits:1 is power of two: 1
Num:2 Set Bits:1 is power of two: 1
Num:3 Set Bits:2 is power of two: 0
Num:4 Set Bits:1 is power of two: 1
Num:5 Set Bits:2 is power of two: 0
Num:15 Set Bits:4 is power of two: 0
Num:16 Set Bits:1 is power of two: 1
Num:22 Set Bits:3 is power of two: 0
Num:32 Set Bits:1 is power of two: 1
Num:38 Set Bits:3 is power of two: 0
Num:64 Set Bits:1 is power of two: 1
Num:70 Set Bits:3 is power of two: 0
Ответ 16
Вот еще один метод, который я разработал в этом случае, используя | вместо &:
bool is_power_of_2(ulong x) {
if(x == (1 << (sizeof(ulong)*8 -1) ) return true;
return (x > 0) && (x<<1 == (x|(x-1)) +1));
}
Ответ 17
Пример
0000 0001 Yes
0001 0001 No
Алгоритм
-
Используя битовую маску, разделите NUM переменную в двоичном
-
IF R > 0 AND L > 0: Return FALSE
-
В противном случае NUM становится ненулевым
-
IF NUM = 1: Return TRUE
-
В противном случае перейдите к Шагу 1
Сложность
Время ~ O(log(d)), где d - число двоичных цифр
Ответ 18
для любой степени 2, справедливо также следующее.
п & (- п) == п
ПРИМЕЧАНИЕ: сбой при n = 0, поэтому необходимо проверить его
Причина, почему это работает:
-n - 2s-дополнение к n. -n будет иметь каждый бит слева от самого правого набора бит n flipped по сравнению с n. Для степеней 2 существует только один бит набора.
Ответ 19
Улучшение ответа @user134548 без арифметики бит:
public static bool IsPowerOfTwo(ulong n)
{
if (n % 2 != 0) return false; // is odd (can't be power of 2)
double exp = Math.Log(n, 2);
if (exp != Math.Floor(exp)) return false; // if exp is not integer, n can't be power
return Math.Pow(2, exp) == n;
}
Это отлично подходит для:
IsPowerOfTwo(9223372036854775809)
Ответ 20
Эта программа в java возвращает "true", если число является степенью 2 и возвращает "false", если ее значение не равно 2
// To check if the given number is power of 2
import java.util.Scanner;
public class PowerOfTwo {
int n;
void solve() {
while(true) {
// To eleminate the odd numbers
if((n%2)!= 0){
System.out.println("false");
break;
}
// Tracing the number back till 2
n = n/2;
// 2/2 gives one so condition should be 1
if(n == 1) {
System.out.println("true");
break;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
PowerOfTwo obj = new PowerOfTwo();
obj.n = in.nextInt();
obj.solve();
}
}
OUTPUT :
34
false
16
true
Ответ 21
private static bool IsPowerOfTwo(ulong x)
{
var l = Math.Log(x, 2);
return (l == Math.Floor(l));
}
Ответ 22
return i> 0 && (i ^ -i) == (-i << 1);
Не нашел такого ответа. Пусть это будет мое
Ответ 23
public static IsPowerOf(int num, int powerOf)
{
var logOfNum = Math.Round(Math.Log(num, powerOf), 10);
// Check for Integral.
return (logOfNum % 1) == 0;
}
