如何检查数字是否为2的幂

Question

今天我需要一个简单的算法来检查一个数是否是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 ^ 63 + 1时,因为四舍五入而准确地返回了63.所以我检查了功率63的2是否等于原始数字 - 它是,因为计算是在s中完成而不是在确切的数字中:log2 xMath.Logdouble

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

这返回true给定的错误值:9223372036854775809.

有更好的算法吗？

Answer 1

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

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

注意,此功能将报告true的0,这是不是一个动力2.如果你想排除它,这是如何:

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

说明

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

二进制和运算符是为整数类型和bool预定义的.对于整数类型,&计算其操作数的逻辑按位AND.对于bool操作数,&计算其操作数的逻辑AND; 也就是说,当且仅当它的两个操作数都为真时,结果才为真.

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

该函数返回boolean(true/false)并接受一个unsigned long类型的传入参数(在本例中为x).让我们为了简单起见假设某人已经传递了值4并且调用了这样的函数:

bool b = IsPowerOfTwo(4)

现在我们将每次出现的x替换为4:

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

好吧,我们已经知道4!= 0 evals to true,到目前为止一直很好.但是关于:

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

这当然转化为:

((4 & 3) == 0)

但到底是4&3什么？

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

100 = 4
011 = 3

想象一下,这些价值就像基本的加法一样堆积起来.该&运营商表示,如果这两个值等于1,则结果为1,否则为0,所以1 & 1 = 1,1 & 0 = 0,0 & 0 = 0,和0 & 1 = 0.所以我们做数学:

100
011
----
000

结果只是0.所以我们回过头来看看我们的返回语句现在转换为:

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

现在翻译为:

return true && (0 == 0);

return true && true;

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

Answer 2

一些记录和解释这个以及其他一些杂乱无章的黑客的网站是:

• http://graphics.stanford.edu/~seander/bithacks.html
  (http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
• http://bits.stephan-brumme.com/
  (http://bits.stephan-brumme.com/isPowerOfTwo.html)

还有他们的祖父,小亨利·沃伦(Henry Warren,Jr.)写的"黑客的喜悦"一书:

• http://www.hackersdelight.org/

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

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

纠正这个问题.

Answer 3

return (i & -i) == i

Answer 4

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

Answer 5

我最近在http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/上写了一篇关于此的文章.它包括位计数,如何正确使用对数,经典的"x &&!(x&(x - 1))"检查等.

Answer 6

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

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

Answer 7

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

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

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

当然,Greg的解决方案要好得多.

Answer 8

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

Answer 9

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

当以二进制表示时,2的幂将总是看起来像1,然后是n个零,其中n大于或等于0. Ex:

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)
.        .
.        .
.        .

等等.

当我们1从这些数字中减去时,它们变为0,然后是n,并且n与上面相同.例如:

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时,会发生什么x,这是2的幂,并且x - 1？

x得到的一个与零的对齐x - 1和所有的零x对齐x - 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

Answer 10

现在在 .Net 6 中这非常容易。

using System.Numerics;

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

这是文档。

Answer 11

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

Answer 12

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

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

Answer 13

return ((x != 0) && !(x & (x - 1)));\n

\n\n

如果x是 2 的幂，则其唯一的 1 位位于位置n。这意味着x \xe2\x80\x93 1位置 中有一个 0 n。要了解原因，请回忆一下二进制减法的工作原理。当从 减 1 时x，借位会一直传播到位置n；位n变为 0，所有低位变为 1。现在，由于x没有与 共同的 1 位x \xe2\x80\x93 1，x & (x \xe2\x80\x93 1)因此为 0，且!(x & (x \xe2\x80\x93 1))为真。

\n