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

今天我需要一个简单的算法来检查一个数字是否是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;
}

但后来我想:如何检查log2x是否恰好是一个整数呢?当我检查2^63+1时，Math.Log()因为四舍五入而返回恰好63。我检查了2的63次方是否等于原来的数，结果是正确的，因为计算是双倍的，而不是精确的数字。

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。

有没有更好的算法?

当前回答

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

const isPowerOfTwo = (number) => { 让结果= false; For(令I = 1;I <= 6;我+ +){ if (number ===数学。Pow (2, i)) { 结果= true; ｝｝返回结果; }; console.log (isPowerOfTwo (16)); console.log (isPowerOfTwo (10));

2021-07-24 18:56:48

其他回答

假设1是2的幂，也就是2的0次方

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

  return false;
}

2022-10-07 13:57:27

试试这个使用mod 2的函数

def is_power_of_two(n):
    if n == 0:
        return False
    while n != 1:
        if n % 2 != 0:
            return False
        n = n // 2
    return True

2022-11-14 17:11:14

有很多答案和发布的链接解释了为什么n & (n-1) == 0适用于2的幂，但我找不到任何解释为什么它不适用于非2的幂，所以我只是为了完整起见添加了这个。

对于n = 1(2^0 = 1) 1 & 0 = 0，没问题。

对于奇数n > 1, 1至少有2位(最左位和最右位)。现在n和n-1只差最右位，所以它们的&和至少在最左位有一个1，所以n & (n-1) != 0:

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

现在即使n不是2的幂，我们也至少有2位1(最左和非最右)。在这里，n和n-1最多相差1位，所以它们的&和也至少在最左边有一个1:

        right-most 1 bit of n
                 v
n:          1xxxx100..00 for even n
n-1:        1xxxx011..11
            ------------
n & (n-1):  1xxxx000..00 != 0

2022-05-14 03:13:45

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

2014-02-14 02:37:22

现在在。net 6中非常简单。

using System.Numerics;

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

这里是文档。

2021-10-25 16:13:43

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

推荐文章

最新文章

标签