如何检查一个数字是否是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(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

2009-11-26 16:37:51

其他回答

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

如果x是2的幂，它唯一的1位在位置n。这意味着x - 1在位置n有一个0。要了解原因，请回忆一下二进制减法是如何工作的。当x减去1时，借位一直传播到位置n;位n变为0，所有低位变为1。现在，由于x和x - 1没有共同的1位，x & (x - 1)为0，并且!(x & (x - 1))为真。

2012-12-21 11:49:06

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

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

检查这篇文章数不清。固定位的

2020-06-09 14:51:59

科特林：

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

返回(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

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

推荐文章

最新文章

标签