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

585

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

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

конфигуратор
источник
1
Я думаю, что решение (x & (x - 1))может возвращать ложные срабатывания, когда Xэто сумма степеней двух, например 8 + 16.
Джо Браун
32
Все числа могут быть записаны как сумма степеней двух, поэтому мы можем представить любое число в двоичном виде. Кроме того, ваш пример не возвращает ложное срабатывание, потому что 11000 & 10111 = 10000! = 0.
vlsd
1
@JoeBrown У него нет ложных срабатываний. Фактически выражение возвращает большую из любой суммы двух степеней двух.
Сэми Бенчериф

Ответы:

1220

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

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.

Грег Хьюгилл
источник
56
@Kripp: число будет иметь двоичную форму 1000 ... 000. Когда вы -1, это будет иметь вид 0111 ... 111. Таким образом, двоичное число двоичного числа и результат будет 000000. Это не произойдет для не-двойки, так как, например, 1010100 станет 1010011, что приведет к (продолжение ...)
конфигуратор
47
... В результате 1010000 после двоичного и. Единственный ложный положительный результат будет 0, поэтому я бы использовал: return (x! = 0) && ((x & (x - 1)) == 0);
конфигуратор
6
Крипп, подумай (2: 1, 10: 1) (4: 3, 100: 11) (8: 7, 1000: 111) (16:15, 10000: 1111) Видите образец?
Thomas L Holaday
13
@ShuggyCoUk: два дополняют то, как представлены отрицательные числа. Поскольку это целое число без знака, представление отрицательных чисел не имеет значения. Этот метод основан только на двоичном представлении неотрицательных целых чисел.
Грег Хьюгилл
4
@ SoapBox - что чаще встречается? Нули или ненулевые числа, которые не являются степенью двойки? Это вопрос, на который вы не можете ответить без некоторого дополнительного контекста. И это действительно, действительно, не имеет значения в любом случае.
конфигуратор
97

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

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

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

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

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

Майкл Берр
источник
4
0 - это степень 2 ... 2 ^ -инф = 0.;););)
Майкл Брей,
4
Поскольку это поток с тегами C # , стоит указать, что последнее выражение (Шона Андерсона) является недопустимым в C #, поскольку !может применяться только к логическим типам, а &&также требует, чтобы оба операнда были логическими (за исключением пользовательских операторов) сделать другие вещи возможными, но это не имеет отношения к ulong.)
Джепп Стиг Нильсен
40

return (i & -i) == i

Андреас Петерссон
источник
2
любой намек, почему это будет или не будет работать? Я проверил его правильность только в Java, где есть только подписанные int / long. если это правильно, это будет лучший ответ. быстрее + ​​меньше
Андреас Петерссон
7
Он использует одно из свойств двухпопулярной нотации: для вычисления отрицательного значения числа вы выполняете побитовое отрицание и добавляете 1 к результату. Младший значащий бит, iкоторый установлен, также будет установлен в -i. Биты ниже этого будут 0 (в обоих значениях), в то время как биты выше этого будут инвертированы относительно друг друга. Следовательно, значение i & -iбудет самым младшим установленным битом i(который является степенью двойки). Если iимеет то же значение, то это был единственный установленный бит. Это не удается, когда i0 по той же причине, чтоi & (i - 1) == 0 и.
Майкл Карман
6
Если iэто тип без знака, дополнение к двойке не имеет к нему никакого отношения. Вы просто используете в своих интересах свойства модульной арифметики и побитовых и.
R .. GitHub СТОП ПОМОГАЕТ ЛЬДУ
2
Это не работает, если i==0(возвращает, (0&0==0)который есть true). Так и должно бытьreturn i && ( (i&-i)==i )
бобобобо
22
bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}
Мэтт Хауэллс
источник
3
Это решение лучше, потому что оно может также иметь дело с отрицательным числом, если отрицательный смог пройти. (Если длинный вместо ulong)
Стивен
Почему в этом случае десятичное число является степенью двойки?
Крис Фрисина
17

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

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}
deft_code
источник
8
на gcc это компилируется до единственного встроенного gcc __builtin_popcount. К сожалению, в одном семействе процессоров пока нет ни одной инструкции по сборке для этого (x86), поэтому это самый быстрый метод подсчета битов. На любой другой архитектуре это отдельная инструкция по сборке.
deft_code
3
@deft_code Поддержка новых архитектур x86popcnt
phuclv
13

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

Степень двойки, выраженная в двоичном виде, всегда будет выглядеть как 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
показать имя
источник
@Michi: я где-то утверждал, что 0 - положительное число? Или степень 2?
displayName
Да, поместив 0 в качестве примера и сделав это с математикой внутри этого двоичного представления. Это создает путаницу.
Мичи
1
Если добавление двух чисел вводит вас в заблуждение, полагая, что они должны быть положительными, я ничего не могу с этим поделать. Кроме того, 0 были показаны в представлении, чтобы подразумевать, что эта степень 2 пропускается в этом числе. Любой, кто знает основы математики, знает, что добавление 0 означает отсутствие добавления чего-либо.
displayName
10

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

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

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

конфигуратор
источник
10
    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;
    }
Раз Мегрелидзе
источник
6
bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;
abelenky
источник
1
Это c#? Я предполагаю, что это так же, c++как xвозвращается как bool.
Мариано Дезанце
1
Я написал это как C ++. Сделать это на C # тривиально: bool isPow2 = ((x & ~ (x-1)) == x)? х! = 0: ложь;
Абеленки
4

Найдите, является ли данное число степенью 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;
}
udhaya
источник
Или в C #: return x == Math.Pow (2, Math.Log (x, 2));
конфигуратор
4
Сломанный. Страдает от основных проблем округления с плавающей точкой. Используйте, frexpа не противные logвещи, если вы хотите использовать с плавающей запятой.
R .. GitHub ОСТАНОВИТЬСЯ ПОМОЩЬ ЛЬДУ
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;
}
король ошибок
источник
4
int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

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

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

Пракаш Джат
источник
3

Число является степенью 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
JerryMouse
источник
возвращая c как 'int', когда функция имеет тип возвращаемого значения 'ulong'? Используя whileвместо if? Я лично не вижу причины, но это, кажется, работает. РЕДАКТИРОВАТЬ: - нет ... он вернет 1 для чего-то большего, чем 0!?
Джеймс Хоури
@JamesKhoury Я писал программу на C ++, поэтому я по ошибке вернул int. Однако это были небольшие опечатки и не заслуживали снижения. Но я не могу понять причину оставшейся части вашего комментария «используя while вместо if» и «он вернет 1 для всего, что больше 0». Я добавил основной заглушкой, чтобы проверить вывод. AFAIK его ожидаемый результат. Поправь меня, если я ошибаюсь.
Jerrymouse
3

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

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));
}
Chethan
источник
Вам нужно (x > 0)немного здесь?
Конфигуратор
@configurator, да, в противном случае is_power_of_2 (0) вернет true
Chethan
3

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

п & (- п) == п

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

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

Khaled.K
источник
1

Улучшение ответа @ 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)
Rhodan
источник
Операции с плавающей точкой намного медленнее, чем простое побитовое выражение
phuclv
1

Марк Гравелл предложил это, если у вас есть .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)но менее переносимая.

jbat100
источник
ты уверен что это быстрее чем (x != 0) && ((x & (x - 1)) == 0)? Я сомневаюсь, что, особенно на старых системах, где popcnt недоступен
phuclv
Это не быстрее. Я только что проверил это на современном процессоре Intel и проверил POPCNT, используемый при разборке (предоставлено, в C-коде, а не .NET). POPCNT быстрее подсчитывает биты в целом, но для однобитного случая трюк с переворотом битов все еще быстрее на 10%.
эраул
Ой, я забираю это обратно. Я тестировал в цикле, где я думаю, что предсказание ветвления было "обманом". POPCNT - это действительно одна инструкция, которая выполняется за один такт и работает быстрее, если она у вас есть.
eraoul
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
eraoul
источник
0

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

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

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

Анил Гупта
источник
-1
private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}
user134548
источник
Попробуйте это для номера 9223372036854775809. Это работает? Я думаю, что нет, из-за ошибок округления.
конфигуратор
1
@configurator 922337203685477580_9_ не похож на степень 2 для меня;)
Киршштейн
1
@Kirschstein: это число дало ему ложное срабатывание.
Эрих Мирабал
7
Киршштейн: Для меня это тоже не похоже. Это похоже на функцию ...
Конфигуратор
-2

Эта программа в 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
K_holla
источник
1
этот вопрос помечен C #, и ваше решение также очень медленное по сравнению с предыдущими решениями [
phuclv