在C++中测试一个数字是2的幂是最简单的方法是什么？

Question

我需要一个这样的函数:

// 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);

任何人都可以建议我怎么写这个？你能告诉我一个可以找到这种算法的好网站吗？

Answer 1

(n & (n - 1)) == 0是最好的.但是,请注意,对于n = 0,它将错误地返回true,因此如果可能,您将需要显式检查它.

http://www.graphics.stanford.edu/~seander/bithacks.html有很多聪明的比特算法,包括这个算法.

Answer 2

2的幂将只设置一位(对于无符号数).就像是

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

工作正常; 一个小于2的幂是一个在较低有效位中的1,所以必须AND到0按位.

当我假设无符号数字时,== 0测试(我原先忘了,对不起)就足够了.如果使用有符号整数,则可能需要> 0测试.

Answer 3

二进制的两个幂看起来像这样:

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));
}

有点麻烦,请看这里.

Answer 4

方法#1:

将数字除以2以进行检查.

时间复杂度: O(log2n).

方法#2:

按位AND与前一个数字的数字应该等于ZERO.

示例: Number = 8二进制8:1 0 0 0二进制7:0 1 1 1和两个数字的按位AND为0 0 0 0 = 0.

时间复杂度: O(1).

方法#3:

按位XOR数字与其前一个数字应该是两个数字的总和.

示例: Number = 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

Answer 5

在 C++20 中std::ispow2，如果您不需要自己实现它，您可以将其用于此目的：

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

Answer 6

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

Answer 7

如果使用 GCC，这可能是最快的。它只使用一个 POPCNT cpu 指令和一个比较。任何 2 的幂的二进制表示，始终只有一位设置，其他位始终为零。所以我们用 POPCNT 计算设置位的数量，如果它等于 1，这个数字就是 2 的幂。我认为没有任何可能的更快的方法。这很简单，如果你理解一次：

if(1==__builtin_popcount(n))

Answer 8

对于2的任何幂，以下条件也成立。

n＆（-n）== n

注意：该条件对于n = 0时为真，尽管不是2的幂。这样做的
原因是：
-n是n的2s补码。与n相比，-n将n的最右置位的每一位的左边翻转。对于2的幂，只有一个置1位。