如何检查一个数字是否是 2 的幂

How to check if a number is a power of 2

提问人:configurator 提问时间:3/2/2009 最后编辑:Vivek Nunaconfigurator 更新时间:9/18/2023 访问量:384502

问:

今天我需要一个简单的算法来检查一个数字是否是 2 的幂。

该算法需要:

  1. 简单
  2. 对任何值进行更正。ulong

我想出了这个简单的算法:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

但后来我想:检查对数2 x 是否正好是一个整数怎么样?当我检查 2^63+1 时,由于四舍五入,正好返回了 63。所以我检查了 2 的 63 次方是否等于原始数字,它是,因为计算是以 s 而不是精确数字完成的。Math.Log()double

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

对于给定的错误值,将返回此值:。true9223372036854775809

有没有更好的算法?

C# 算法 math .net-core

评论

1赞 Joe Brown 11/24/2011
我认为当 2 的幂之和时,解决方案可能会返回误报,例如 .(x & (x - 1))X8 + 16
48赞 vlsd 11/24/2011
所有数字都可以写成 2 的幂和,这就是为什么我们可以用二进制表示任何数字。此外,您的示例不会返回误报,因为 11000 和 10111 = 10000 != 0。
2赞 Samie Bencherif 12/8/2018
@JoeBrown 它没有任何误报。事实上,表达式返回的 2 次幂的任意和中的较大者。
1赞 Vivek Nuna 12/21/2021
现在在 .net 6 中非常简单 stackoverflow.com/a/69711480/6527049
0赞 gautam1168 12/1/2022
不是每个 2 的幂都只有一个固定位吗?2^0 = 1 , 2^1 = 10, 2^2 = 100, 2^3 = 1000 等等 那么我们不能只检查是否只有一个设置位吗?2 ^x = 总和(0 x 2^习) + (1 x 2 ^ x) + 总和(0 x 2 ^xj)

答:

1509赞 Greg Hewgill 3/2/2009 #1

这个问题有一个简单的技巧:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

请注意,此函数将报告 ,它不是 的幂。如果要排除该内容,请按以下步骤操作:true02

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

解释

首先是MSDN定义的按位二进制和运算符:

二进制和运算符是为整型和布尔值预定义的。为 整型,并计算其操作数的逻辑按位 AND。 对于布尔操作数,& 计算其操作数的逻辑 AND;那 是,当且仅当其两个操作数都为真时,结果为真。

现在让我们来看看这一切是如何发生的:

该函数返回布尔值 (true / false) 并接受一个类型为 unsigned long 的传入参数(在本例中为 x)。为了简单起见,我们假设有人传递了值 4 并调用了该函数,如下所示:

bool b = IsPowerOfTwo(4)

现在我们用 4 替换每个出现的 x:

return (4 != 0) && ((4 & (4-1)) == 0);

好吧,我们已经知道 4 != 0 计算为 true,到目前为止一切顺利。但是呢:

((4 & (4-1)) == 0)

这当然可以转化为这一点:

((4 & 3) == 0)

但究竟是什么?4&3

4 的二进制表示是 100,3 的二进制表示是 011(记住 & 取这些数字的二进制表示)。所以我们有:

100 = 4
011 = 3

想象一下,这些值的堆叠就像基本加法一样。运算符说,如果两个值都等于 1,则结果为 1,否则为 0。所以 、 、 和 。因此,我们进行数学计算:&1 & 1 = 11 & 0 = 00 & 0 = 00 & 1 = 0

100
011
----
000

结果只是 0。因此,我们回过头来看看我们的 return 语句现在翻译为什么:

return (4 != 0) && ((4 & 3) == 0);

现在翻译为:

return true && (0 == 0);
return true && true;

我们都知道这很简单,这表明对于我们的例子,4 是 2 的幂。true && truetrue

评论

67赞 configurator 3/2/2009
@Kripp:数字将为二进制形式 1000...000。当你 -1 时,它将是 0111...111 的形式。因此,这两个数字的二进制 和 结果是 000000。对于非二的幂,这不会发生,因为例如 1010100 会变为1010011,从而导致(续...
50赞 configurator 3/2/2009
...导致二进制和之后的 1010000。唯一的误报是 0,这就是为什么我会使用: return (x != 0) && ((x & (x - 1)) == 0);
7赞 Thomas L Holaday 3/2/2009
克里普,考虑 (2:1, 10:1) (4:3, 100:11) (8:7, 1000:111) (16:15, 10000:1111) 看到模式了吗?
15赞 Greg Hewgill 3/2/2009
@ShuggyCoUk:二的补码是负数的表示方式。由于这是一个无符号整数,因此负数的表示无关紧要。此技术仅依赖于非负整数的二进制表示。
4赞 configurator 10/23/2010
@SoapBox - 什么更常见?零或非零数不是二的幂?如果没有更多的背景信息,这是一个你无法回答的问题。反正这真的,真的无关紧要。
10赞 configurator 3/2/2009 #2

发布问题后,我想到了以下解决方案:

我们需要检查二进制数字中的一个是否恰好是 1。因此,我们只需将数字一次向右移动一位数字,如果它等于 1,则返回。如果在任何时候我们得到一个奇数(),我们知道结果是。这证明(使用基准)比(大)真值的原始方法略快,而假值或小值则快得多。true(number & 1) == 1false

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

当然,格雷格的解决方案要好得多。

108赞 Michael Burr 3/2/2009 #3

一些记录和解释这一点和其他一些有点扭捏的技巧的网站是:

还有他们的爷爷,小亨利·沃伦 (Henry Warren, Jr.) 的《黑客的喜悦》一书

正如 Sean Anderson 的页面所解释的那样,该表达式错误地表示 0 是 2 的幂。他建议使用:((x & (x - 1)) == 0)

(!(x & (x - 1)) && x)

来纠正该问题。

评论

9赞 Michael Bray 9/28/2016
0 是 2 的幂...2 ^ -inf = 0。;) ;) ;)
4赞 Jeppe Stig Nielsen 3/4/2018
由于这是一个 C# 标记的线程,因此值得指出的是,最后一个表达式(Sean Anderson 的)在 C# 中是非法的,因为只能应用于布尔类型,并且还要求两个操作数都是布尔值-(除了用户定义的运算符使其他事情成为可能,但这与 .!&&ulong
1赞 Peter Cordes 9/19/2020
catonmat.net/low-level-bit-hacks 通过 8 位示例解释了一些相关的 bithacks。例如,用 隔离最右边的 1 位。此测试只是清除最低设定位的特例。y = x & (-x)
50赞 Andreas Petersson 6/17/2009 #4

return (i & -i) == i

评论

2赞 Andreas Petersson 7/22/2009
任何提示为什么这会或不会起作用?我仅在 Java 中检查了它的正确性,其中只有带符号的 ints/longs。如果它是正确的,这将是更好的答案。更快+更小
8赞 Michael Carman 8/15/2009
它利用了 2 补码表示法的属性之一:要计算数字的负值,请执行按位否定并将结果加 1。其中设置的最低有效位也将在 中设置。下面的位将为 0(在两个值中),而上面的位将相对于彼此反转。因此,will 的值是 中最低有效设置位(是 2 的幂)。如果具有相同的值,则这是唯一设置的位。当为 0 时,它失败,原因与 0 相同。i-ii & -iiiii & (i - 1) == 0
7赞 R.. GitHub STOP HELPING ICE 9/4/2010
如果是无符号类型,则二进制补码与它无关。您只是在利用模块化算术和按位 and 的属性。i
4赞 bobobobo 11/15/2011
如果(返回 ),则不起作用。它应该是i==0(0&0==0)truereturn i && ( (i&-i)==i )
-1赞 user134548 7/22/2009 #5
private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

评论

0赞 configurator 7/22/2009
尝试9223372036854775809数字。它有效吗?我认为不会,因为四舍五入错误。
1赞 Kirschstein 3/31/2010
@configurator 922337203685477580_9_ 对我来说看起来不像是 2 的幂;)
1赞 Erich Mirabal 3/31/2010
@Kirschstein:这个数字给了他一个误报。
7赞 configurator 4/1/2010
Kirschstein:在我看来也不像。不过,它看起来确实像一个函数......
25赞 Matt Howells 11/27/2009 #6
bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

评论

4赞 Steven 1/27/2015
这个解决方案更好,因为如果负数能够传入,它也可以处理负数。(如果 long 而不是 ulong)
0赞 chris Frisina 4/1/2020
在这种情况下,为什么小数会以 2 的幂传递?
3赞 udhaya 3/31/2010 #7

找出给定的数字是否是 2 的幂。

#include <math.h>

int main(void)
{
    int n,logval,powval;
    printf("Enter a number to find whether it is s power of 2\n");
    scanf("%d",&n);
    logval=log(n)/log(2);
    powval=pow(2,logval);

    if(powval==n)
        printf("The number is a power of 2");
    else
        printf("The number is not a power of 2");

    getch();
    return 0;
}

评论

0赞 configurator 4/1/2010
或者,在 C# 中:return x == Math.Pow(2, Math.Log(x, 2));
5赞 R.. GitHub STOP HELPING ICE 9/4/2010
破碎。存在重大的浮点舍入问题。如果你想使用浮点,请使用而不是讨厌的东西。frexplog
22赞 deft_code 8/26/2010 #8

下面是一个简单的 C++ 解决方案:

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

评论

10赞 deft_code 9/5/2010
在 GCC 上,这会编译为一个名为 的 GCC 内置 .不幸的是,一个处理器系列还没有一个汇编指令来执行此操作 (x86),因此它是最快的位计数方法。在任何其他体系结构上,这是单个汇编指令。__builtin_popcount
3赞 phuclv 3/16/2017
@deft_code 更新的 x86 微架构支持popcnt
0赞 Peter Cordes 9/19/2020
lea eax, [rdi-1] + test/jnz实现比 / 便宜一些,特别是如果您不需要将情况处理为不计算在内。i & (i-1) == 0popcntcmp/jei==0
0赞 displayName 10/17/2020
感谢您提及 C++ 并将其链接到 C++ 的维基百科页面。如果没有它,那将是非常令人困惑的。/秒
7赞 abelenky 9/4/2010 #9
bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

评论

1赞 Mariano Desanze 9/4/2010
这是吗?我想这是作为布尔值返回的。c#c++x
1赞 abelenky 9/4/2010
我确实把它写成 C++。让它成为 C# 是微不足道的:bool isPow2 = ((x & ~(x-1))==x)?x!=0 : 假;
3赞 jerrymouse 1/12/2012 #10

如果一个数字只包含 2 个设定位,则它是 1 的幂。我们可以使用此属性和泛型函数来查找一个数字是否为 2 的幂。countSetBits

这是一个 C++ 程序:

int countSetBits(int n)
{
        int c = 0;
        while(n)
        {
                c += 1;
                n  = n & (n-1);
        }
        return c;
}

bool isPowerOfTwo(int n)
{        
        return (countSetBits(n)==1);
}
int main()
{
    int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
    for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
        printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
    return 0;
}

我们不需要显式检查 0 是否为 2 的幂,因为它也返回 0 的 False。

输出

Num:0   Set Bits:0   is power of two: 0
Num:1   Set Bits:1   is power of two: 1
Num:2   Set Bits:1   is power of two: 1
Num:3   Set Bits:2   is power of two: 0
Num:4   Set Bits:1   is power of two: 1
Num:5   Set Bits:2   is power of two: 0
Num:15  Set Bits:4   is power of two: 0
Num:16  Set Bits:1   is power of two: 1
Num:22  Set Bits:3   is power of two: 0
Num:32  Set Bits:1   is power of two: 1
Num:38  Set Bits:3   is power of two: 0
Num:64  Set Bits:1   is power of two: 1
Num:70  Set Bits:3   is power of two: 0

评论

0赞 James Khoury 1/13/2012
当函数的返回类型为“ulong”时,将 C 作为“int”返回?使用 a 代替 ?我个人看不出原因,但它似乎有效。编辑:- 不......对于大于 !?whileif0
0赞 jerrymouse 1/13/2012
@JamesKhoury我正在编写一个 c++ 程序,所以我错误地返回了一个 int。然而,这是一个小小的错别字,不值得投反对票。但我不明白您评论的其余部分“使用 while 而不是 if”和“对于大于 1 的任何内容,它将返回 0”的原因。我添加了主存根来检查输出。AFAIK 这是预期的输出。如果我错了,请纠正我。
4赞 bugs king 2/15/2012 #11
bool isPowerOfTwo(int x_)
{
  register int bitpos, bitpos2;
  asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
  asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
  return bitpos > 0 && bitpos == bitpos2;
}

评论

0赞 Peter Cordes 9/19/2020
bitpos > 0如果您试图排除 .输入 具有一个设置位,并导致 BSF 和 BSR 产生 的位位置结果。您没有初始化读写输出,因此您没有任何保证的行为。(BSF 和 BSR 在 input=0 时保持目标不变;AMD 对此进行了记录,英特尔实现了它,但仅将结果记录为未定义的值。也许 ,在 asm 语句有用之前,因此它们在 input=0 时不匹配。x_ == 0x_ = 10"+r"x_ == 0bitpos = 0bitpos2 = 32
0赞 Peter Cordes 9/19/2020
我还建议从输入约束中删除。你希望编译器选择一个寄存器,因为你要读取它两次。第二个 asm 语句可以安排成 output=input,这样编译器就可以根据需要为输入和输出选择相同的寄存器。"m"
0赞 Craig McQueen 11/29/2023
ASM 不跨平台兼容。您甚至没有提到这适用于哪个处理器家族。
5赞 sudeepdino008 9/20/2012 #12
int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

这真的很快。检查所有 2^32 个整数大约需要 6 分 43 秒。

5赞 Prakash Jat 12/21/2012 #13
return ((x != 0) && !(x & (x - 1)));

如果是 2 的幂,则其唯一的 1 位就位。这意味着位置为 0。要了解原因,请回想一下二进制减法的工作原理。当从 中减去 1 时,借用一直传播到位置;位变为 0,所有较低的位变为 1。现在,由于没有 1 位与 共有 ,为 0,并且为 true。xnx – 1nxnnxx – 1x & (x – 1)!(x & (x – 1))

3赞 Chethan 4/25/2013 #14

这是我设计的另一种方法,在这种情况下,使用 而不是:|&

bool is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

评论

0赞 configurator 4/26/2013
你需要这里的位吗?(x > 0)
0赞 Chethan 4/26/2013
@configurator,是的,否则 is_power_of_2(0) 将返回 true
10赞 Rezo Megrelidze 2/14/2014 #15
    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

这里有一个通用的算法,用于确定一个数字是否是另一个数字的幂。

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }
2赞 Khaled.K 7/28/2015 #16

0000 0001    Yes
0001 0001    No

算法

  1. 使用位掩码,将变量划分为二进制NUM

  2. IF R > 0 AND L > 0: Return FALSE

  3. 否则,将变为非零NUM

  4. IF NUM = 1: Return TRUE

  5. 否则,请转到步骤 1

复杂性

时间 ~ 其中是二进制位数O(log(d))d

29赞 displayName 9/4/2015 #17

以下已接受答案的附录可能对某些人有用:

当以二进制表示时,2 的幂将始终看起来像 1 后跟 n 个零,其中 n 大于或等于 0。前任:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

等等。

当我们从这些数字中减去时,它们变为 0,后跟 n 个数字,n 再次与上述相同。前任:1

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

等等。

直击症结

当我们对一个数字进行按位 AND 时会发生什么,这是一个 2 的幂,以及 ?xx - 1

x 中的一个与 x - 1 的零对齐,x 的所有零与 x - 1 的 1 对齐,导致按位 AND 结果为 0。这就是我们上面提到的单行答案是正确的。


进一步增加了上面公认的答案的美感——

因此,我们现在有一个财产可供我们支配:

当我们从任何数字中减去 1 时,那么在二进制表示中,最右边的 1 将变为 0,最右边的 1 右边的所有零现在将变成 1。

这个属性的一个很棒的用途是找出 - 给定数字的二进制表示中存在多少个 1?对于给定的整数,要做到这一点的简短而甜蜜的代码是:x

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

从上面解释的概念中可以证明的数字的另一个方面是“每个正数都可以表示为 2 的幂和吗?

是的,每个正数都可以表示为 2 的幂和。对于任何数字,取其二进制表示。例如:取号码。117

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

评论

0赞 Michi 5/24/2017
是的,以 0 为例,并在该二进制表示中对其进行数学运算。它造成了一种混乱。
0赞 lesterfernandez 9/18/2023
对于“财产”,你的意思是说“......最右边的 1 右边的所有零现在都会变成 1“?
1赞 displayName 9/18/2023
@lesterfernandez:你是对的!
4赞 Freeze Francis 5/30/2016 #18

对于 2 的任意幂,以下也成立。

n&(-n)==n

注意:n=0 失败,因此需要检查它
这样做的原因是:
-n 是 n 的 2s 补码。 与 n 相比,-n 将翻转 n 的最右边设置位左边的每个位。对于 2 的幂,只有一个固定位。

评论

0赞 GSerg 9/7/2021
这个答案是 7 年前发布的
1赞 rhodan 7/6/2017 #19

改进@user134548的答案,无需位算术:

public static bool IsPowerOfTwo(ulong n)
{
    if (n % 2 != 0) return false;  // is odd (can't be power of 2)

    double exp = Math.Log(n, 2);
    if (exp != Math.Floor(exp)) return false;  // if exp is not integer, n can't be power
    return Math.Pow(2, exp) == n;
}

这适用于:

IsPowerOfTwo(9223372036854775809)

评论

0赞 phuclv 2/22/2020
浮点运算比简单的按位表达式慢得多
1赞 jbat100 12/9/2019 #20

如果你有.NET Core 3,System.Runtime.Intrinsics.X86.Popcnt.PopCount,Mark gravell建议这样做

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

单指令,速度快但便携性较差。(x != 0) && ((x & (x - 1)) == 0)

评论

0赞 phuclv 2/22/2020
你确定它比 ?我对此表示怀疑,尤其是在 popcnt 不可用的旧系统上(x != 0) && ((x & (x - 1)) == 0)
0赞 eraoul 2/23/2020
它不是更快。我刚刚在现代 Intel CPU 上对此进行了测试,并验证了反汇编中使用的 POPCNT(当然,在 C 代码中,而不是 .NET)。POPCNT 通常用于计算比特,但对于单比特的情况,比特旋转技巧仍然快 10%。
0赞 eraoul 2/23/2020
哎呀,我把它拿回来了。我正在循环测试,我认为分支预测是“作弊”。POPCNT 确实是在单个时钟周期内运行的单个指令,如果可用,速度会更快。
0赞 eraoul 2/23/2020 #21

在 C 语言中,我测试了这个技巧,并将其与 进行了比较,在 Linux 上使用 gcc,并使用 -mpopcnt 标志以确保使用 CPU 的 POPCNT 指令。我的测试程序计算了区间 [0, 2^31] 中 # 的整数,这些整数是 2 的幂。i && !(i & (i - 1)__builtin_popcount(i)

起初我以为这快了 10%,尽管我验证了我使用的拆卸中使用了 POPCN。i && !(i & (i - 1)__builtin_popcount

但是,我意识到我包含了一个 if 语句,分支预测在 bit twiddling 版本上可能做得更好。正如预期的那样,我删除了 if 和 POPCNT 最终更快。

结果:

Intel(R) Core(TM) i7-4771 CPU 最大 3.90GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

AMD Ryzen Threadripper 2950X 16 核处理器,最大 3.50GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

请注意,这里的英特尔 CPU 似乎比 AMD 稍慢,但 POPCNT 要快得多;AMD POPCNT 没有提供那么多的提升。

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to (not including) 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

运行测试:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

评论

0赞 chux - Reinstate Monica 2/25/2023
注释是和循环,建议调和。更好的是:遍历所有 32 位值。2 up to 2^31fori = 0; i < 1<<30;
0赞 eraoul 2/26/2023
谢谢 -- 不错的收获。我现在不想重新运行它并重新计算值,因为我无法方便地访问原始 CPU,但您是对的,注释(或代码)是错误的;固定。我不确定为什么我早早停下来而不是做所有 32 位值,我猜只是懒惰。我喜欢你建议的更改:我会用for (unsigned long i = 0; i < 1<<30; i++)for (unsigned long i = 0; i <= 0xFFFFFFFF; i++) {
0赞 chux - Reinstate Monica 2/26/2023
请注意,使用 32 位 时,始终为 true。unsigned longi <= 0xFFFFFFFF
0赞 Anil Gupta 6/9/2020 #22

我看到很多答案都建议返回 n && !(n & (n - 1)) 但根据我的经验,如果输入值为负数,则返回 false 值。 我将在这里分享另一种简单的方法,因为我们知道两个数字的幂只有一个设置位,所以简单地我们将计算设置位的数量,这将花费 O(log N) 时间。

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

查看本文以计算设置位数

评论

0赞 Cato 10/7/2022
输入为 ulong,因此它不是负数
0赞 Marcus Moo 7/9/2020 #23

这也是另一种方法

package javacore;

import java.util.Scanner;

public class Main_exercise5 {
    public static void main(String[] args) {
        // Local Declaration
        boolean ispoweroftwo = false;
        int n;
        Scanner input = new Scanner (System.in);
        System.out.println("Enter a number");
        n = input.nextInt();
        ispoweroftwo = checkNumber(n);
        System.out.println(ispoweroftwo);
    }
    
    public static boolean checkNumber(int n) {
        // Function declaration
        boolean ispoweroftwo= false;
        // if not divisible by 2, means isnotpoweroftwo
        if(n%2!=0){
            ispoweroftwo=false;
            return ispoweroftwo;
        }
        else {
            for(int power=1; power>0; power=power<<1) {
                if (power==n) {
                    return true;
                }
                else if (power>n) {
                    return false;
                }
            }
        }
        return ispoweroftwo;
    }
}
1赞 ABHISHEK PARMAR 8/5/2020 #24

在这种方法中,您可以检查整数中是否只有 1 个设置位,并且整数是否> 0 (C++)。

bool is_pow_of_2(int n){
    int count = 0;
    for(int i = 0; i < 32; i++){
        count += (n>>i & 1);
    }
    return count == 1 && n > 0;
}

0赞 Aleksandar Biševac 7/25/2021 #25

如果该数字是 2 的幂,则返回 64 值(您可以在 for 循环条件中更改它(“6”代表 2^6 是 64);

const isPowerOfTwo = (number) => {
  let result = false;
  for (let i = 1; i <= 6; i++) {
    if (number === Math.pow(2, i)) {
      result = true;
    }
  }
  return result;
};

console.log(isPowerOfTwo(16));
console.log(isPowerOfTwo(10));

6赞 Vivek Nuna 10/26/2021 #26

现在在 .Net 6 中非常简单。

using System.Numerics;

bool isPow2 = BitOperations.IsPow2(64); // sets true

这是文档。

2赞 Uche Igbokwe 2/25/2022 #27

.NET 6 中有一个衬垫

// IsPow2 evaluates whether the specified Int32 value is a power of two.
Console.WriteLine(BitOperations.IsPow2(128));            // True
1赞 velocity 5/5/2022 #28

我一直在阅读 Random.nextInt(int bound) 的文档,并看到了这段很好的代码,它检查参数是否是 2 幂,它说(代码的一部分):

if ((bound & -bound) == bound) // ie, bouns is a power of 2   

让我们来测试一下

for (int i=0; i<=8; i++) {
  System.out.println(i+" = " + Integer.toBinaryString(i));
}

>>
0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000
// the left most 0 bits where cut out of the output

for (int i=-1; i>=-8; i--) {
  System.out.println(i+" = " + Integer.toBinaryString(i));
}

>>
-1 = 11111111111111111111111111111111
-2 = 11111111111111111111111111111110
-3 = 11111111111111111111111111111101
-4 = 11111111111111111111111111111100
-5 = 11111111111111111111111111111011
-6 = 11111111111111111111111111111010
-7 = 11111111111111111111111111111001
-8 = 11111111111111111111111111111000

你注意到什么了吗?
幂 2 数在正二进制表示和负二进制表示中具有相同的位,如果我们做一个逻辑 AND,我们得到相同的数字:)

for (int i=0; i<=8; i++) {
  System.out.println(i + " & " + (-i)+" = " + (i & (-i)));
}

>>
0 & 0 = 0
1 & -1 = 1
2 & -2 = 2
3 & -3 = 1
4 & -4 = 4
5 & -5 = 1
6 & -6 = 2
7 & -7 = 1
8 & -8 = 8
1赞 Dr.jacky 5/12/2022 #29

科特林

fun isPowerOfTwo(n: Int): Boolean {
    return (n > 0) && (n.and(n-1) == 0)
}

fun isPowerOfTwo(n: Int): Boolean {
    if (n == 0) return false
    return (n and (n - 1).inv()) == n
}

inv 反转此值中的位。


注意:
log2 解决方案不适用于大数字,例如 536870912 ->

import kotlin.math.truncate
import kotlin.math.log2

fun isPowerOfTwo(n: Int): Boolean {
    return (n > 0) && (log2(n.toDouble())) == truncate(log2(n.toDouble()))
}

评论

0赞 FrankM 5/2/2023
对于无符号整数,也可以使用。n.countOneBits() == 1
0赞 WaterGenie 5/14/2022 #30

There were a number of answers and posted links explaining why the works for powers of 2, but I couldn't find any explanation of why it doesn't work for non-powers of 2, so I'm adding this just for completeness.n & (n-1) == 0

For n = 1 (2^0 = 1), 1 & 0 = 0, so we are fine.

For odd n > 1, there are at least 2 bits of 1 (left-most and right-most bits). Now n and n-1 will only differ by the right-most bit, so their &-sum will at least have a 1 on the left-most bit, so :n & (n-1) != 0

n:          1xxxx1  for odd n > 1
n-1:        1xxxx0
            ------
n & (n-1):  1xxxx0 != 0

Now for even n that is not a power of 2, we also have at least 2 bits of 1 (left-most and non-right-most). Here, n and n-1 will differ up to the right-most 1 bit, so their &-sum will also have at least a 1 on the left-most bit:

        right-most 1 bit of n
                 v
n:          1xxxx100..00 for even n
n-1:        1xxxx011..11
            ------------
n & (n-1):  1xxxx000..00 != 0
0赞 Cato 10/7/2022 #31

I'm assuming 1 is a power of two, which it is, it's 2 to the power of zero

 bool IsPowerOfTwo(ulong testValue)
 {
  ulong bitTest = 1;
  while (bitTest != 0)
  {
    if (bitTest == testValue) return true;
    bitTest = bitTest << 1;
  }

  return false;
}