如何检查一个数字是否是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的任意次幂，也成立。

n& (-n) = = n

注意:n=0失败，需要检查这样做的原因是: -n是n的2s补。-n将使n的最右集合位左边的每一位与n相比翻转。对于2的幂，只有一个集合位。

2016-05-29 17:45:11

其他回答

返回(i & -i) == i

2009-06-17 13:25:25

一些网站记录并解释了这一点和其他一些无聊的黑客:

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.)写的《黑客的喜悦》(Hacker’s Delight):

http://www.hackersdelight.org/

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

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

为了纠正这个问题。

2009-03-01 20:52:33

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

2009-07-21 20:29:18

    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

Mark gravell建议，如果你有。net Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

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

单指令，比(x != 0) && ((x & (x - 1)) == 0)快，但移植性较差。

2019-12-09 11:51:48

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

推荐文章

最新文章

标签