问题描述
今天我需要一个简单的算法来检查一个数字是否是 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;
}
但后来我想,如何检查 log x
是否是一个整数?但是当我检查 2^63+1 时,由于四舍五入,Math.Log
返回的正好是 63.所以我检查了 2 的 63 次方是否等于原始数字 - 确实如此,因为计算是在 double
s 中完成的,而不是精确的数字:
But then I thought, how about checking if log 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 double
s 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;
}
对于给定的错误值,这返回了 true
: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;
}
注意,这个函数会为0
报告true
,这不是2
的幂.如果您想排除它,方法如下:
Note, this function will report true
for 0
, which is not a power of 2
. If you want to exclude that, 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:
二进制 &运算符是为整数类型和 bool 预定义的.为了整数类型,&计算其操作数的逻辑按位与.对于布尔操作数,&计算其操作数的逻辑与;那即,当且仅当其两个操作数都为真时,结果为真.
现在让我们看看这一切是如何进行的:
Now let's take a look at how this all plays out:
该函数返回布尔值 (true/false) 并接受一个 unsigned long 类型的传入参数(在本例中为 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)
现在我们用 4 替换每次出现的 x:
Now we replace each occurrence of x with 4:
return (4 != 0) && ((4 & (4-1)) == 0);
我们已经知道 4 != 0 评估为真,到目前为止一切顺利.但是呢:
Well we already know that 4 != 0 evals to true, so far so good. But what about:
((4 & (4-1)) == 0)
这当然可以转化为:
((4 & 3) == 0)
但是4&3
究竟是什么?
4 的二进制表示是 100,而 3 的二进制表示是 011(记住 & 采用这些数字的二进制表示).所以我们有:
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.所以我们回去看看我们的 return 语句现在转换成什么:
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);
现在翻译成:
return true && (0 == 0);
return true && true;
我们都知道true &&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的幂的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!