CSharp - 如果数字是2的幂如何检查?

  显示原文与译文双语对照的内容

今天我需要一个简单的算法来检查一个数字是否为 2的幂。

算法需要:

  1. 简单
  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;
}

为完整性,零不是两个的幂。 如果你想考虑边缘情况,下面是操作方法:


bool IsPowerOfTwo(ulong x)
{
 return (x!= 0) && ((x & (x - 1)) == 0);
}

说明

首先,在MSDN定义中使用按位二进制&运算符:

二元&运算符为整型和布尔类型预定义。 对于整型,&计算它的操作数的逻辑位和。 对于布尔操作数,&计算它的操作数的逻辑和值;也就是说,如果它的操作数是真的,则结果为真。

现在让我们看看这一切如何发挥作用:

函数返回布尔型( 真/假) 并接受一个输入参数为无符号长( 在本例中,)的参数。 为了简单起见,假设有人已经传递了值 4并调用了如下函数:


bool b = IsPowerOfTwo(4)

现在我们用 4替换每个出现的x:


return (4!= 0) && ((4 & (4-1)) == 0);

我们已经知道 4!= 0 evals为真,到目前为止很好。 但是:


((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的幂。

下面是一个简单的C++ 解决方案:


bool IsPowerOfTwo( unsigned int i )
{
 return std::bitset<32>(i).count() == 1;
}

发布问题后,我想到了以下解决方案:

我们需要检查是否恰好有一个二进制数字是一个。 所以我们只需一次将数字右移一个数字,然后返回 true 如果它等于 1. 如果在任何一点,我们都有一个奇数( (number & 1) == 1 ),我们知道结果是 false 。 这证明( 使用基准基准) 比原来的( 大) 值的速度稍微快一些,对于false或者小值,它的速度更快。


private static bool IsPowerOfTwo(ulong number)
{
 while (number!= 0)
 {
 if (number == 1)
 return true;

 if ((number & 1) == 1)
//number is an odd number and not 1 - so it's not a power of two.
 return false;

 number = number>> 1;
 }
 return false;
}


当然,greg的解决方案更好。

查找给定数字是否为 2的幂。


#include <math.h>

int main(void)
{
 int n,logval,powval;
 printf("Enter a number to find whether it is s power of 2n");
 scanf("%d",&n);
 logval=log(n)/log(2);
 powval=pow(2,logval);

 if(powval==n)
 printf("The number is a power of 2");
 else
 printf("The number is not a power of 2");

 getch();
 return 0;
}

...