我需要这样的功能：
// return true if '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);
谁能建议我怎么写这个？
Ant
问问题
77019 次
16 回答
209
(n & (n - 1)) == 0是最好的。但是，请注意，对于 n=0，它将错误地返回 true，因此如果可能，您将需要明确检查它。
http://www.graphics.stanford.edu/~seander/bithacks.html有大量聪明的比特旋转算法，包括这个。
于 2008-09-20T14:45:50.410 回答
83
2 的幂将只设置一个位（对于无符号数）。就像是
bool powerOfTwo = !(x == 0) && !(x & (x - 1));
会正常工作；小于 2 的幂的 1 在低有效位中全为 1，因此必须按位与 0。
当我假设无符号数字时， == 0 测试（我最初忘记了，抱歉）就足够了。如果您使用有符号整数，您可能需要 > 0 测试。
于 2008-09-20T14:37:15.063 回答
52
二进制中 2 的幂如下所示：
1: 0001
2: 0010
4: 0100
8: 1000
请注意，总是恰好设置了 1 位。唯一的例外是有符号整数。例如，一个值为 -128 的 8 位有符号整数如下所示：
10000000
所以在检查了这个数字是否大于零之后，我们可以使用一个聪明的小技巧来测试一个并且只有一个位被设置。
bool is_power_of_2(int x) {
return x > 0 && !(x & (x−1));
}
更多小玩意请看这里。
于 2008-09-20T14:40:00.223 回答
16
方法#1：
将数字除以 2 隐蔽地检查它。
时间复杂度： O(log2n)。
方法#2：
按位与前一个数字的数字应等于零。
示例： Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 并且两个数字的按位与为 0 0 0 0 = 0。
时间复杂度： O(1)。
方法#3：
按位异或该数字与其前一个数字应该是两个数字的总和。
示例： Number = 8 Binary of 8: 1 0 0 0 Binary of 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
于 2016-01-20T01:58:28.393 回答
13
在 C++20 中std::has_single_bit，如果您不需要自己实现它，您可以将其用于此目的：
#include <bit>
static_assert(std::has_single_bit(16));
static_assert(!std::has_single_bit(15));
请注意，这要求参数是无符号整数类型。
于 2019-05-26T09:10:32.553 回答
8
bool is_power_of_2(int i) {
if ( i <= 0 ) {
return 0;
}
return ! (i & (i-1));
}
于 2008-09-20T14:39:28.350 回答
6
如果使用 GCC，这可能是最快的。它只使用一个 POPCNT cpu 指令和一个比较。任何 2 数的幂的二进制表示，始终只有一位设置，其他位始终为零。所以我们用 POPCNT 来计算设置的位数，如果它等于 1，则该数字是 2 的幂。我认为没有任何可能的更快的方法。这很简单，如果你理解一次：
if(1==__builtin_popcount(n))
于 2019-03-20T11:09:57.327 回答
6
对于 2 的任何幂，以下也成立。
n&(-n)==n
注意：n=0 的条件为真，尽管它不是 2 的幂。
它起作用的原因是：
-n 是 n 的 2s 补码。-n 将与 n 相比，将 n 的最右边设置位左侧的每一位翻转。对于 2 的幂，只有一个设置位。
于 2016-05-29T17:36:19.040 回答
2
由于布尔短路和比较缓慢的事实，跟随会比大多数投票的答案更快。
int isPowerOfTwo(unsigned int x)
{
return x && !(x & (x – 1));
}
如果你知道 x 不能为 0 那么
int isPowerOfTwo(unsigned int x)
{
return !(x & (x – 1));
}
于 2015-10-12T14:43:14.057 回答
2
return n > 0 && 0 == (1 << 30) % n;
于 2016-10-16T18:13:00.997 回答
1
这不是最快或最短的方法，但我认为它非常易读。所以我会做这样的事情：
bool is_power_of_2(int n)
int bitCounter=0;
while(n) {
if ((n & 1) == 1) {
++bitCounter;
}
n >>= 1;
}
return (bitCounter == 1);
}
这是有效的，因为二进制是基于 2 的幂。任何只有一位设置的数字必须是 2 的幂。
于 2008-09-20T14:40:33.763 回答
1
在 C++ 中测试一个数字是否是 2 的幂的最简单方法是什么？
如果您有一个带有位操作指令的现代 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__. 当AVX2 可用并启用时，它在 Visual Studio 2015 及更高版本的 Microsoft 编译器中可用。有关您需要的标头，请参阅SIMD 内在函数的标头文件。
我通常在 i686_blsr_u64上_LP64_编译以防万一。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。
于 2016-09-20T19:36:04.653 回答
0
这是另一种方法，在这种情况下使用|代替&：
bool is_power_of_2(int x) {
return x > 0 && (x<<1 == (x|(x-1)) +1));
}
于 2013-04-24T17:05:40.687 回答
-1
可以通过c++
int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}
于 2015-09-14T12:47:16.370 回答
-2
另一种方法（可能不是最快的）是确定 ln(x) / ln(2) 是否为整数。
于 2008-09-20T15:03:04.037 回答
-4
这是 T-SQL (SQL Server) 中的位移方法：
SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo
它比做对数四次要快得多（第一次设置得到十进制结果，第二组得到整数设置和比较）
于 2013-02-02T01:34:14.510 回答