Какой самый простой способ проверить, является ли число в C ++ степенью двойки?

Мне нужна такая функция:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

Кто-нибудь может подсказать, как я мог это написать? Можете ли вы назвать мне хороший веб-сайт, где можно найти такой алгоритм?

(n & (n - 1)) == 0лучший. Однако обратите внимание, что он неправильно вернет истину для n = 0, поэтому, если это возможно, вы захотите проверить это явно.

http://www.graphics.stanford.edu/~seander/bithacks.html содержит большую коллекцию умных алгоритмов перестановки битов, включая этот.

При степени двойки будет установлен только один бит (для чисел без знака). Что-то типа

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Будет работать нормально; на единицу меньше степени двойки - это все единицы в младших битах, поэтому побитовое И должно быть равно 0.

Поскольку я предполагал беззнаковые числа, тест == 0 (который я изначально забыл, извините) подходит. Если вы используете целые числа со знаком, вам может потребоваться проверка> 0.

Степени двойки в двоичном формате выглядят так:

1: 0001
2: 0010
4: 0100
8: 1000

Обратите внимание, что всегда установлен ровно 1 бит. Единственное исключение - целое число со знаком. например, 8-битное целое число со знаком со значением -128 выглядит так:

10000000

Итак, после проверки того, что число больше нуля, мы можем использовать небольшой хитрый прием, чтобы проверить, что установлен только один бит.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

Чтобы узнать больше, смотрите здесь .

Подход №1:

Разделите число на 2, чтобы проверить это.

Временная сложность: O (log2n).

Подход №2:

Побитовое И число с его предыдущим числом должно быть равно НУЛЮ.

Пример: Число = 8 Двоичное из 8: 1 0 0 0 Двоичное из 7: 0 1 1 1 и побитовое И для обоих чисел равно 0 0 0 0 = 0.

Временная сложность: O (1).

Подход № 3:

Побитовое исключающее ИЛИ число с его предыдущим числом должно быть суммой обоих чисел.

Пример: Число = 8 Двоичное из 8: 1 0 0 0 Двоичное из 7: 0 1 1 1, а побитовое исключающее ИЛИ обоих чисел равно 1 1 1 1 = 15.

Временная сложность: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

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

п & (- п) == п

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

Вероятно, это самый быстрый вариант при использовании GCC. Он использует только инструкцию процессора POPCNT и одно сравнение. Двоичное представление любого числа степени двойки всегда имеет только один установленный бит, остальные биты всегда равны нулю. Итак, мы подсчитываем количество установленных битов с помощью POPCNT, и если оно равно 1, то число равно степени 2. Я не думаю, что есть какие-либо возможные более быстрые методы. А это очень просто, если вы однажды поняли:

if(1==__builtin_popcount(n))

В C ++ 20 есть то, std::ispow2что вы можете использовать именно для этой цели, если вам не нужно реализовывать это самостоятельно:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));

Следующее будет быстрее, чем ответ, получивший наибольшее количество голосов, из-за логического короткого замыкания и того факта, что сравнение идет медленно.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

Если вы знаете, что x не может быть 0, тогда

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

return n > 0 && 0 == (1 << 30) % n;

Какой самый простой способ проверить, является ли число в C ++ степенью двойки?

Если у вас есть современный процессор Intel с инструкциями по обработке битов , вы можете выполнить следующее. Он опускает прямой код C / C ++, потому что на него уже ответили другие, но он вам нужен, если BMI недоступен или включен.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC, ICC и Clang поддерживают BMI сигналов с __BMI__. Он доступен в компиляторах Microsoft в Visual Studio 2015 и выше, когда доступен и включен AVX2. . Чтобы узнать, какие заголовки вам нужны, см. Заголовочные файлы для встроенных функций SIMD .

Я обычно охранник _blsr_u64с _LP64_в случае компиляции на i686. Clang нуждается в небольшом обходном пути, потому что он использует немного другой внутренний символ nam:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

Можете ли вы назвать мне хороший веб-сайт, где можно найти такой алгоритм?

Этот сайт часто цитируют: Bit Twiddling Hacks .

Это не самый быстрый и не самый короткий способ, но я думаю, что он очень удобочитаемый. Я бы сделал что-то вроде этого:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

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

Вот еще один метод, в данном случае |вместо &:

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

Возможно через c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Я знаю, что это очень старый пост, но я подумал, что было бы интересно разместить его здесь.

От Code-Golf SE (так что вся заслуга авторам ): Showcase of Languages

(Абзац про C , подпункт Длина 36 сниппет )

bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}

Другой способ (возможно, не самый быстрый) - определить, является ли ln (x) / ln (2) целым числом.

Это метод битового сдвига в T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

Это намного быстрее, чем выполнение логарифмирования четыре раза (первый набор для получения десятичного результата, второй набор для получения целочисленного набора и сравнения)