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

Question

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

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

但后来我想，检查一下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.

有更好的算法吗？

Answer 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)，并接受一个输入参数(在本例中为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 = 4011 = 3假设这些值被堆叠起来，就像基本加法一样。这个&运算符表示，如果两个值都等于1，则结果为1，否则为0。所以1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0，和0 & 1 = 0..所以我们计算一下：100011----000结果就是0。因此，我们回头看看返回语句现在转换为：return (4 != 0) && ((4 & 3) == 0);现在翻译为：return true && (0 == 0);return true && true;我们都知道true && true是简单的true，这表明，在我们的例子中，4是2的幂。