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

Question

Сегодня мне нужен был простой алгоритм проверки, является ли число степенью 2.

Алгоритм должен быть:

1. Simple
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;
}

Но тогда я подумал, а как насчет проверки, является ли log<sub>2</sub> 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.

Есть ли лучший алгоритм?

Answer 1

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

Это действительно быстро. Проверка всех 2 ^ 32 целых чисел занимает около 6 минут и 43 секунды.

Answer 2

Найти, является ли данное число степенью 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;
}

Answer 3

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.

Answer 4

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;
}

Answer 5

Число является степенью 2, если оно содержит только 1 установленный бит. Мы можем использовать это свойство и обобщенную функцию countSetBits, чтобы определить, является ли число степенью 2 или нет.

Это программа на C ++:

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

Answer 6

Вот другой метод, который я разработал, в данном случае используя | вместо &:

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));
}

Answer 7

Улучшение ответа @ 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)

Answer 8

для любой степени 2 также имеет место следующее.

п & (- п) == п

ПРИМЕЧАНИЕ: сбой при n = 0, поэтому необходимо проверить его
Причина, по которой это работает:
-n является дополнением 2s от n. -n будет иметь каждый бит слева от крайнего правого установленного бита n по сравнению с n. Для степеней 2 есть только один установленный бит.

Answer 9

Пример

0000 0001    Yes
0001 0001    No

Алгоритм

1. Используя битовую маску, разделите NUM переменную в двоичном виде

2. IF R > 0 AND L > 0: Return FALSE

3. В противном случае NUM становится ненулевым

4. IF NUM = 1: Return TRUE

5. В противном случае перейдите к шагу 1

Сложность

Время ~ O(log(d)), где d - количество двоичных цифр

Answer 10

Эта программа в 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