如何检查是否一个数是2的幂 [英] How to check if a number is a power of 2
问题描述
今天我需要一种简单算法检查是否一个数是2的幂。
Today I needed a simple algorithm for checking if a number is a power of 2.
该算法需要：
- 简单
- 校正任何
ULONG值。
我想出了这个简单的算法：
I came up with this simple algorithm:
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;
}
不过转念一想，怎么样，如果检查日志 2 X 是一个确切的轮数？但是，当我检查了2 ^ 63 + 1，将Math.log 返回正好63由于四舍五入的原因。所以，我检查，如果2电源63等于原来的号码 - 这是因为计算是做双和没有确切的数字：
But then I thought, how about checking if log2 x is an exactly round number? But when I checked for 2^63+1, Math.Log returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in doubles and not in exact numbers:
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
这回真对于给定的错误的值： 9223372036854775809
This returned true for the given wrong value: 9223372036854775809.
有没有更好的算法？
推荐答案
有一个简单的技巧对于这个问题：
There's a simple trick for this problem:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
有关完整性，零不是二的幂。如果你要考虑到边缘的情况下，方法如下：
For completeness, zero is not a power of two. If you want to take into account that edge case, here's how:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
说明
首先按位二进制和放大器;从MSDN定义操作符：
Explanation
First and foremost the bitwise binary & operator from MSDN definition:
二元放大器;运营商pdefined为整型和布尔$ P $。对于 整型，＆安培;计算其操作数的逻辑位与。 对于bool操作数，及放大器;计算逻辑与的操作数;那 是，则结果为真，当且仅当两个操作数都为真。
Binary & operators are predefined for the integral types and bool. For integral types, & computes the logical bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.
现在，让我们来看看这一切是如何发挥出来：
Now let's take a look at how this all plays out:
该函数返回布尔型（真/假）和接受类型无符号长的一个传入确定参数（x，在这种情况下）。让我们为简单起见，假设有人通过了价值4，并呼吁像这样的功能：
The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:
bool b = IsPowerOfTwo(4)
现在我们替换x的每次出现与4：
Now we replace each occurrence of x with 4:
return (4 != 0) && ((4 & (4-1)) == 0);
嗯，我们已经知道，4！= 0 evals为true，到目前为止，一切顺利。但怎么样：
Well we already know that 4 != 0 evals to true, so far so good. But what about:
((4 & (4-1)) == 0)
这相当于本课程的：
This translates to this of course:
((4 & 3) == 0)
但究竟什么是 4安培; 3
的4二进制重新presentation是100和3的二进制重新presentation是011（记得＆安培;将这些数字的二进制重新presentation因此，我们有：
The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers. So we have:
100 = 4
011 = 3
想象一下，这些值被堆积起来很像小学加法。该＆安培; 运营商说，如果两个值等于1，则结果为1，否则为0，所以 1安培; 1 = 1 ， 1安培; 0 = 0 ， 0安培; 0 = 0 和 0安培; 1 = 0 。所以我们做数学题：
Imagine these values being stacked up much like elementary addition. The & operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:
100
011
----
000
其结果仅仅是0，所以，我们回去看看退货语句现在翻译为：
The result is simply 0. So we go back and look at what our return statement now translates to:
return (4 != 0) && ((4 & 3) == 0);
现在翻译为：
Which translates now to:
return true && (0 == 0);
return true && true;
我们都知道，真放;＆安培;真正的简直就是真，这说明我们的例子中，4是2的力量。
We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.
这篇关于如何检查是否一个数是2的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
