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

Question

如何检查一个数字是否为2的幂今天，我需要一个简单的算法来检查一个数字是否是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的幂。