如何检查一个数字是否是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。

有没有更好的算法?

当前回答

    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

其他回答

返回(i & -i) == i

2009-06-17 13:25:25

科特林：

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

2022-05-11 21:11:18

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

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

2013-04-25 13:51:51

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

推荐文章

最新文章

标签