今天我需要一个简单的算法来检查一个数字是否是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;
}
但后来我想:如何检查log2x是否恰好是一个整数呢?当我检查2^63+1时，Math.Log()因为四舍五入而返回恰好63。我检查了2的63次方是否等于原来的数，结果是正确的，因为计算是双倍的，而不是精确的数字。
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。
有没有更好的算法?
如果一个数字只包含1个设置位，则它是2的幂。我们可以使用这个属性和泛型函数countSetBits来判断一个数字是否是2的幂。
这是一个c++程序:
int countSetBits(int n)
{
int c = 0;
while(n)
{
c += 1;
n = n & (n-1);
}
return c;
}
bool isPowerOfTwo(int n)
{
return (countSetBits(n)==1);
}
int main()
{
int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
return 0;
}
我们不需要显式地检查0是否是2的幂，因为它对0也返回False。
输出
Num:0 Set Bits:0 is power of two: 0
Num:1 Set Bits:1 is power of two: 1
Num:2 Set Bits:1 is power of two: 1
Num:3 Set Bits:2 is power of two: 0
Num:4 Set Bits:1 is power of two: 1
Num:5 Set Bits:2 is power of two: 0
Num:15 Set Bits:4 is power of two: 0
Num:16 Set Bits:1 is power of two: 1
Num:22 Set Bits:3 is power of two: 0
Num:32 Set Bits:1 is power of two: 1
Num:38 Set Bits:3 is power of two: 0
Num:64 Set Bits:1 is power of two: 1
Num:70 Set Bits:3 is power of two: 0
解决这个问题有一个简单的技巧:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
注意，这个函数对于0报告为真，因为0不是2的幂。如果你想排除这种情况，以下是方法:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
解释
首先，MSDN定义中的按位二进制&运算符:
二进制和操作符是为整型和bool类型预定义的。为
整型，&计算其操作数的逻辑位与。
对于bool操作数，&计算其操作数的逻辑与;那
Is，当且仅当它的两个操作数都为真时，结果为真。
现在让我们来看看这一切是如何发生的:
该函数返回布尔值(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的幂。
一些网站记录并解释了这一点和其他一些无聊的黑客:
http://graphics.stanford.edu/~seander/bithacks.html
(http://graphics.stanford.edu/ ~ seander / bithacks.html # DetermineIfPowerOf2)
http://bits.stephan-brumme.com/
(http://bits.stephan-brumme.com/isPowerOfTwo.html)
他们的祖父，小亨利·沃伦(Henry Warren, Jr.)写的《黑客的喜悦》(Hacker’s Delight):
http://www.hackersdelight.org/
正如Sean Anderson的页面解释的那样，表达式((x & (x - 1)) == 0)错误地表明0是2的幂。他建议使用:
(!(x & (x - 1)) && x)
为了纠正这个问题。
