c# - 如何判断一个数是不是2的幂

Question

今天我需要一个简单的算法来检查一个数是否是 2 的幂。

算法需要:

1. 简单
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;
}

但后来我想:如何检查 log₂ x 是否恰好是一个整数？当我检查 2^63+1 时，Math.Log() 由于四舍五入而恰好返回 63。所以我检查了 2 的 63 次方是否等于原始数，确实如此，因为计算是在 double 中完成的，而不是精确的数字。

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。

有没有更好的算法？

Answer 1

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

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

请注意，此函数将为 0 报告 true，这不是 2 的幂。如果你想排除它，方法如下:

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

说明

首先是来自 MSDN 定义的按位二进制 & 运算符:

Binary & operators are predefined for the integral types and bool. For integral types, & computes the logical bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.

现在让我们来看看这一切是如何发生的:

该函数返回 bool 值 (true/false) 并接受一个 unsigned long 类型的传入参数(在本例中为 x)。为了简单起见，让我们假设有人传递了值 4 并像这样调用函数:

bool b = IsPowerOfTwo(4)

现在我们将每次出现的 x 替换为 4:

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

好吧，我们已经知道 4 != 0 的计算结果为真，到目前为止一切顺利。但是关于:

((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 的幂。