Мне нужна такая функция:
// 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 лучше. Однако обратите внимание, что он неверно вернет true для n = 0, поэтому, если это возможно, вам нужно будет явно проверить его.
http://www.graphics.stanford.edu/~seander/bithacks.html имеет большую коллекцию умных алгоритмов бит-скручивания, включая этот.
Сила двух будет иметь только один бит (для беззнаковых чисел). Что-то вроде
bool powerOfTwo = !(x == 0) && !(x & (x - 1));
Будет работать нормально; один меньше, чем у двух, это все 1s в менее значимых битах, поэтому AND должен 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:
Побитовое И число с его только предыдущим номером должно быть равно ZERO.
Пример: Число = 8 Двоичный код 8: 1 0 0 0 Двоичный номер 7: 0 1 1 1 и побитовый И обоих чисел равен 0 0 0 0 = 0.
Сложность времени: O (1).
Подход № 3:
Побитовое XOR число с его только предыдущим номером должно быть суммой обоих чисел.
Пример: Число = 8 Двоичный код 8: 1 0 0 0 Бинарный номер 7: 0 1 1 1 и побитовый XOR обоих чисел равен 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));
}
для любой степени 2, справедливо также следующее.
ПРИМЕЧАНИЕ. Условие истинно для n = 0, хотя его значение не равно 2.
Причина, почему это работает:
-n - 2s-дополнение к n. -n будет иметь каждый бит слева от самого правого набора бит n flipped по сравнению с n. Для степеней 2 существует только один бит набора.
return n > 0 && 0 == (1 << 30) % n;
После этого будет быстрее, чем большинство опрошенных ответов из-за булевого короткого замыкания и факта медленного сравнения.
int isPowerOfTwo(unsigned int x)
{
return x && !(x & (x – 1));
}
Если вы знаете, что x не может быть 0, то
int isPowerOfTwo(unsigned int x)
{
return !(x & (x – 1));
}
Какой самый простой способ проверить, является ли число степенью 2 в 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);
}
Это работает, поскольку двоичный файл основан на степенях двух. Любое число с только одним набором бит должно иметь мощность два.
Это самый быстрый:
if(1==__builtin_popcount(n))
Вот еще один метод, в данном случае используя | вместо &:
bool is_power_of_2(int x) {
return x > 0 && (x<<1 == (x|(x-1)) +1));
}
Это возможно с помощью С++
int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}
В С++ 20 есть std::ispow2 который вы можете использовать именно для этой цели, если вам не нужно реализовывать его самостоятельно:
#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));
Еще один способ (возможно, не самый быстрый) - определить, является ли 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
Это намного быстрее, чем выполнение логарифма четыре раза (сначала установите, чтобы получить десятичный результат, 2-й набор, чтобы получить целочисленное множество и сравнить)