如何检查一个数是否是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。 所以我检查了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 。
有更好的算法吗？
这个问题有一个简单的窍门：
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操作数，＆计算其操作数的逻辑与; 也就是说，当且仅当它的两个操作数都为真时，结果才为真。
现在让我们来看看这一切如何发挥：
该函数返回布尔值（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（记住＆采用这些数字的二进制表示）。 所以我们有：
100 = 4
011 = 3
想象一下，这些价值观叠加起来很像基本的加法。 &运算符表示如果两个值都等于1，那么结果为1，否则为0.所以1 & 1 = 1 1 & 0 = 0 0 & 0 = 0 0 & 1 = 0 。 所以我们做数学：
100
011
----
000
结果只是0.因此，我们回过头来看看我们的返回语句现在转化为：
return (4 != 0) && ((4 & 3) == 0);
现在转化为：
return true && (0 == 0);
return true && true;
我们都知道true && true是true ，这表明对于我们的例子来说，4是2的幂。
一些记录和解释这个以及其他一些捣乱黑客的网站是：
（http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2）
（http://bits.stephan-brumme.com/isPowerOfTwo.html）
还有他们的祖父，亨利·沃伦小说“黑客的喜悦”一书。
正如Sean Anderson的页面所解释的，表达式((x & (x - 1)) == 0)错误地表明0是2的幂。他建议使用：
(!(x & (x - 1)) && x)
纠正这个问题。
return (i & -i) == i
上一篇: How to check if a number is a power of 2
下一篇: how to turn windows service on if its off. control it from webapplication