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

小编典典

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

all

今天我需要一个简单的算法来检查一个数字是否是 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 2 x 是否是一个整数？当我检查 2^63+1 时，Math.Log()由于四舍五入而返回正好 63。所以我检查了 2 的
63 次方是否等于原始数字，因为计算是在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。

有更好的算法吗？

阅读 104

2022-03-04

共1个答案

小编典典

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

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

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

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

解释

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

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

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

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

bool b = IsPowerOfTwo(4)

现在我们用 4 替换每次出现的 x：

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

2022-03-04