我们如何有效地确定一个数字是否是2的力量？

判断一个数是否为2的幂

问题描述

判断给定数字是否为2的幂需要一个既简单又准确的算法。作者提出了两种算法，但在使用对数计算时遇到了舍入问题。

第一种算法

第一种算法IsPowerOfTwo 使用简单的循环，通过位移来检查2的幂：

<code class="language-c#">private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}</code>

此方法简单易懂，对于任何ulong值都能完美运行。

第二种算法

第二种算法IsPowerOfTwo_2 依赖于对数计算：

<code class="language-c#">private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}</code>

然而，由于舍入问题，此算法无法正确处理值9223372036854775809。

改进后的算法

<code class="language-c#">bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}</code>

算法解释

这种改进后的算法巧妙地利用了位运算：

• 位运算符& 检查对应位置的两个位是否都为1。
• 从数字中减去1会将所有1翻转为0，将所有0翻转为1。
• 如果数字是2的幂，则其二进制表示只会有一个1位。
• 当数字与(x - 1)进行位与运算时，除了最右边的1位之外的所有位都将为0。
• 因此，如果结果为0，则该数字是2的幂。

排除零

<code class="language-c#">bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}</code>

为了排除零（零不被认为是2的幂），添加了附加条件(x != 0)。

以上是我们如何有效地确定一个数字是否是2的力量？的详细内容。更多信息请关注PHP中文网其他相关文章！