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

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

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

1. просто
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;
}

Но потом я подумал, а как насчет проверки, является ли число круглым? Но когда я проверил на 2 ^ 63 + 1, вернул ровно 63 из-за округления. Поэтому я проверил, равно ли 2 степени 63 исходному числу - и это так, потому что вычисление выполняется в s, а не в точных числах:log2 xMath.Logdouble

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.

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

Для этой проблемы есть простой трюк:

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. Для целочисленных типов & вычисляет логическое побитовое И своих операндов. Для булевых операндов & вычисляет логическое И своих операндов; то есть результат равен true, если и только если оба его операнда имеют значение true.

Теперь давайте посмотрим, как все это закончится:

Функция возвращает логическое значение (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 (4 != 0) && ((4 & 3) == 0);

Что теперь переводится как:

return true && (0 == 0);

return true && true;

Мы все знаем, что true && trueэто просто true, и это показывает, что для нашего примера 4 - это степень 2.

Некоторые сайты, которые документируют и объясняют этот и другие хитрые взломы:

• http://graphics.stanford.edu/~seander/bithacks.html
  ( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
• http://bits.stephan-brumme.com/
  ( http://bits.stephan-brumme.com/isPowerOfTwo.html )

И их дедушка, книга «Восхищение Хакера» Генри Уоррена-младшего :

• http://www.hackersdelight.org/

Как объясняет страница Шона Андерсона , выражение ((x & (x - 1)) == 0)неправильно указывает, что 0 - это степень 2. Он предлагает использовать:

(!(x & (x - 1)) && x)

чтобы исправить эту проблему.

return (i & -i) == i

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Недавно я написал статью об этом на http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Он включает подсчет битов, как правильно использовать логарифмы, классическую проверку «x &&! (X & (x - 1))» и другие.

Вот простое решение C ++ :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

Следующее дополнение к принятому ответу может быть полезно для некоторых людей:

Степень двойки, выраженная в двоичном виде, всегда будет выглядеть как 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

После публикации вопроса я подумал о следующем решении:

Нам нужно проверить, является ли ровно одна из двоичных цифр одной. Таким образом, мы просто сдвигаем число на одну цифру за раз и возвращаем, 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's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

Конечно, решение Грега намного лучше.

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

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

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

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

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

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

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))является истинным.

Число является степенью 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.

ВЫВОД

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

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

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

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

п & (- п) == п

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

пример

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число двоичных цифр

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

Марк Гравелл предложил это, если у вас есть .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Отдельная инструкция, быстрее, (x != 0) && ((x & (x - 1)) == 0)но менее переносимая.

В Си я проверил i && !(i & (i - 1)трюк и сравнил его с__builtin_popcount(i) помощью gcc в Linux с флагом -mpopcnt, чтобы убедиться, что используется инструкция процессора POPCNT. Моя тестовая программа посчитала число целых чисел от 0 до 2 ^ 31, которое было степенью двойки.

Сначала я подумал, что i && !(i & (i - 1)это на 10% быстрее, хотя я убедился, что POPCNT использовался в разборке, где я использовал__builtin_popcount .

Тем не менее, я понял, что я включил оператор if, и предсказание ветвления, вероятно, улучшилось в версии с битами. Я удалил if и POPCNT оказался быстрее, как и ожидалось.

Результаты:

Процессор Intel (R) Core (TM) i7-4771 с максимальной частотой 3,90 ГГц

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

16-ядерный процессор AMD Ryzen Threadripper 2950X, максимум 3,50 ГГц

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Обратите внимание, что здесь процессор Intel выглядит немного медленнее, чем AMD, но немного быстрее POPCNT; AMD POPCNT не дает такой поддержки.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Запустите тесты:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Я вижу, что многие ответы предлагают вернуть n &&! (N & (n - 1)), но по моему опыту, если входные значения отрицательны, он возвращает ложные значения. Здесь я поделюсь еще одним простым подходом, так как мы знаем, что у числа из двух чисел есть только один установленный бит, поэтому просто мы посчитаем количество установленных бит, это займет O (log N) времени.

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Проверьте эту статью, чтобы рассчитывать нет. из установленных бит

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

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