在 C++ 中测试一个数字是否是 2 的幂的最简单方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/108318/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What's the simplest way to test whether a number is a power of 2 in C++?
提问by Ant
I need a function like this:
我需要这样的功能：
// 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);
Can anyone suggest how I could write this? Can you tell me a good web site where this sort of algorithm can be found?
谁能建议我怎么写这个？你能告诉我一个可以找到这种算法的好网站吗？
回答by Anonymous
(n & (n - 1)) == 0is best. However, note that it will incorrectly return true for n=0, so if that is possible, you will want to check for it explicitly.
(n & (n - 1)) == 0是最好的。但是，请注意，当 n=0 时它会错误地返回 true，因此如果可能，您需要明确检查它。
http://www.graphics.stanford.edu/~seander/bithacks.htmlhas a large collection of clever bit-twiddling algorithms, including this one.
http://www.graphics.stanford.edu/~seander/bithacks.html有大量巧妙的位旋转算法，包括这个。
回答by Adam Wright
A power of two will have just one bit set (for unsigned numbers). Something like
2 的幂将只设置一位（对于无符号数）。就像是
bool powerOfTwo = !(x == 0) && !(x & (x - 1));
Will work fine; one less than a power of two is all 1s in the less significant bits, so must AND to 0 bitwise.
会正常工作；一个小于 2 的幂在较低有效位中全为 1，因此必须 AND 到 0 按位。
As I was assuming unsigned numbers, the == 0 test (that I originally forgot, sorry) is adequate. You may want a > 0 test if you're using signed integers.
当我假设无符号数字时， == 0 测试（我最初忘记了，抱歉）就足够了。如果您使用有符号整数，您可能需要 > 0 测试。
回答by Matt Howells
Powers of two in binary look like this:
二进制中的 2 次幂如下所示：
1: 0001
2: 0010
4: 0100
8: 1000
Note that there is always exactly 1 bit set. The only exception is with a signed integer. e.g. An 8-bit signed integer with a value of -128 looks like:
请注意，始终只设置 1 位。唯一的例外是带符号整数。例如，值为 -128 的 8 位有符号整数如下所示：
10000000
So after checking that the number is greater than zero, we can use a clever little bit hack to test that one and only one bit is set.
因此，在检查数字大于零之后，我们可以使用一个聪明的小技巧来测试是否设置了一位且仅设置了一位。
bool is_power_of_2(int x) {
return x > 0 && !(x & (x?1));
}
For more bit twiddling see here.
欲了解更多信息，请参见此处。
回答by Raj Dixit
Approach #1:
方法#1：
Divide number by 2 reclusively to check it.
将数字除以 2 以进行检查。
Time complexity :O(log2n).
时间复杂度：O(log2n)。
Approach #2:
方法#2：
Bitwise AND the number with its just previous number should be equal to ZERO.
按位 AND 与前一个数字的数字应该等于零。
Example:Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.
示例：Number = 8 8 的二进制：1 0 0 0 7 的二进制：0 1 1 1 并且两个数字的按位与是 0 0 0 0 = 0。
Time complexity :O(1).
时间复杂度：O(1)。
Approach #3:
方法#3：
Bitwise XOR the number with its just previous number should be sum of both numbers.
按位异或数字与其前一个数字应该是两个数字的总和。
Example:Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise XOR of both the numbers is 1 1 1 1 = 15.
示例：Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 两个数字的按位异或为 1 1 1 1 = 15。
Time complexity :O(1).
时间复杂度：O(1)。
http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html
http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html
回答by Rob Wells
bool is_power_of_2(int i) {
if ( i <= 0 ) {
return 0;
}
return ! (i & (i-1));
}
回答by FReeze FRancis
for any power of 2, the following also holds.
对于任何 2 的幂，以下也成立。
n&(-n)==n
n&(-n)==n
NOTE: The condition is true for n=0 ,though its not a power of 2.
Reason why this works is:
-n is the 2s complement of n. -n will have every bit to the left of rightmost set bit of n flipped compared to n. For powers of 2 there is only one set bit.
注意：该条件对于 n=0 为真，尽管它不是 2 的幂。这样做的
原因是：
-n 是 n 的 2s 补码。-n 将使 n 的最右侧设置位左侧的每一位与 n 相比翻转。对于 2 的幂，只有一个设置位。
回答by F10PPY
This is probably the fastest, if using GCC. It only uses a POPCNT cpu instruction and one comparison. Binary representation of any power of 2 number, has always only one bit set, other bits are always zero. So we count the number of set bits with POPCNT, and if it's equal to 1, the number is power of 2. I don't think there is any possible faster methods. And it's very simple, if you understood it once:
如果使用 GCC，这可能是最快的。它只使用一个 POPCNT cpu 指令和一个比较。任何 2 的幂的二进制表示，始终只有一位设置，其他位始终为零。所以我们用 POPCNT 计算设置位的数量，如果它等于 1，这个数字就是 2 的幂。我认为没有任何可能的更快的方法。这很简单，如果你理解一次：
if(1==__builtin_popcount(n))
回答by Rakete1111
In C++20 there is std::ispow2which you can use for exactly this purpose if you don't need to implement it yourself:
在 C++20 中std::ispow2，如果您不需要自己实现它，您可以将其用于此目的：
#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));
回答by Margus
Following would be faster then most up-voted answer due to boolean short-circuiting and fact that comparison is slow.
由于布尔短路和比较缓慢的事实，以下将比大多数投票的答案更快。
int isPowerOfTwo(unsigned int x)
{
return x && !(x & (x – 1));
}
If you know that x can not be 0 then
如果你知道 x 不能为 0 那么
int isPowerOfTwo(unsigned int x)
{
return !(x & (x – 1));
}
回答by jww
What's the simplest way to test whether a number is a power of 2 in C++?
在 C++ 中测试一个数字是否是 2 的幂的最简单方法是什么？
If you have a modern Intel processor with the Bit Manipulation Instructions, then you can perform the following. It omits the straight C/C++ code because others have already answered it, but you need it if BMI is not available or enabled.
如果您拥有带有Bit Manipulation Instructions的现代英特尔处理器，那么您可以执行以下操作。它省略了直接的 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, and Clang signal BMI support with __BMI__. It's available in Microsoft compilers in Visual Studio 2015 and above when AVX2 is available and enabled. For the headers you need, see Header files for SIMD intrinsics.
GCC、ICC 和 Clang 信号 BMI 支持与__BMI__. 当AVX2 可用并启用时，它在 Visual Studio 2015 及更高版本的 Microsoft 编译器中可用。对于您需要的头文件，请参阅SIMD 内在函数的头文件。
I usually guard the _blsr_u64with an _LP64_in case compiling on i686. Clang needs a little workaround because it uses a slightly different intrinsic symbol nam:
我平时守卫_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
Can you tell me a good web site where this sort of algorithm can be found?
你能告诉我一个可以找到这种算法的好网站吗？
This website is often cited: Bit Twiddling Hacks.
这个网站经常被引用：Bit Twiddling Hacks。
