今天我需要一个简单的算法来检查一个数字是否是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。
有没有更好的算法?
以下对已接受答案的补充可能对某些人有用:
2的幂，当用二进制表示时，总是像1后面跟着n个0，其中n大于等于0。例:
Decimal Binary
1 1 (1 followed by 0 zero)
2 10 (1 followed by 1 zero)
4 100 (1 followed by 2 zeroes)
8 1000 (1 followed by 3 zeroes)
. .
. .
. .
等等。
当我们把这些数减1，它们就变成0后面跟着n个1，同样，n和上面一样。例:
Decimal Binary
1 - 1 = 0 0 (0 followed by 0 one)
2 - 1 = 1 01 (0 followed by 1 one)
4 - 1 = 3 011 (0 followed by 2 ones)
8 - 1 = 7 0111 (0 followed by 3 ones)
. .
. .
. .
等等。
说到关键
当我们对一个数字x做位与运算时会发生什么，x是a
2的幂，x - 1呢?
x的1与x - 1的0对齐，x的所有0与x - 1的1对齐，导致按位and的结果为0。这就是为什么上面提到的单行答案是正确的。
进一步增加了上述公认答案的美感
所以，我们现在有一个属性可供我们使用:
当我们用任何数减去1时，那么在二进制表示法中，最右边的1将变成0，而最右边1左边的所有0也将变成1。
这个性质的一个很棒的用途是求出一个给定数字的二进制表示中有多少个1 ?对于给定的整数x，简短而甜蜜的代码是:
byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);
从上面解释的概念可以证明数字的另一个方面是“每个正数都可以表示为2的幂的和吗?”
是的，每一个正数都可以表示成2的幂的和。对于任何数字，取其二进制表示。乘117路车。
The binary representation of 117 is 1110101
Because 1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have 117 = 64 + 32 + 16 + 0 + 4 + 0 + 1
一些网站记录并解释了这一点和其他一些无聊的黑客:
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)
为了纠正这个问题。
