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

一尘不染

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

algorithm

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

但是后来我想，如何检查log2 x一个确切的整数呢？但是当我检查2 ^ 63 + 1时，Math.Log由于
四舍五入而恰好返回了63 。所以我检查了63的2的幂是否等于原始数字-是的，因为计算是用doubles而不是精确的数字完成的：

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。

有没有更好的算法？

阅读 191

2020-07-28

共1个答案

一尘不染

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

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

注意，此功能将报告true的0，这是不是一个动力2。
如果您要排除此情况，请按以下步骤操作：

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

Explanation

首先是MSDN定义中的按位二进制和运算符：

已为整数类型和布尔预定义了二进制和运算符。对于整数类型，＆计算其操作数的逻辑按位与。对于布尔操作数，＆计算其操作数的逻辑与；也就是说，当且仅当两个操作数都为真时，结果才为真。

现在，让我们看看这一切如何进行：

该函数返回布尔值（true / false），并接受一个
unsigned long类型的传入参数（在这种情况下为x）。为了简单起见，让我们
假设有人已经传递了值4并像下面这样调用了函数：

bool b = IsPowerOfTwo(4)

Now we replace each occurrence of x with 4:

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

好了，我们已经知道4！= 0等于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语句现在转换为：

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

现在翻译成：

return true && (0 == 0);



return true && true;

众所周知，这true && true很简单true，这表明在我们的示例中4是2的幂。

2020-07-28