Какой самый простой способ проверить, является ли число степенью 2 в 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);
Кто-нибудь может подсказать, как я мог написать это? Можете ли вы сказать мне хороший веб-сайт, где можно найти такой алгоритм?
14 ответов
(n & (n - 1)) == 0 лучший. Однако обратите внимание, что он будет неверно возвращать true для 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));
}
Для получения дополнительной информации смотрите здесь.
В C++20 есть std::ispow2 который вы можете использовать именно для этой цели, если вам не нужно реализовывать это самостоятельно:
#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));
Подход № 1:
Разделите число на 2, чтобы проверить это.
Временная сложность: O (log2n).
Подход № 2:
Побитовое И число с только что предыдущим номером должно быть равно нулю.
Пример: Число = 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 по сравнению с n. Для степеней 2 есть только один установленный бит.
Последующее будет быстрее, чем ответ с наибольшим количеством голосов из-за логического короткого замыкания и факта, что сравнение медленное.
int isPowerOfTwo(unsigned int x)
{
return x && !(x & (x – 1));
}
Если вы знаете, что х не может быть 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
}
Поддержка BMI сигналов GCC, ICC и Clang с __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));
}
Другой способ (возможно, не самый быстрый) - определить, является ли ln(x) / ln(2) целым числом.
Я знаю, что это очень старый пост, но я подумал, что было бы интересно разместить его здесь.
От Code-Golf SE (так что вся заслуга авторам): Showcase of Languages
(Абзац про C, подпункт Длина 36 сниппет)
bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}
Можно через с ++
int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}
Это метод сдвига битов в T-SQL (SQL Server):
SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo
Это намного быстрее, чем делать логарифм четыре раза (первый набор для получения десятичного результата, второй набор для получения целого числа и сравнения)