如何快速判断一个正整数是2的N次幂？

long N ＝ .........;

我想法是 N 保存的是一个2进制数， 如果这个2进制数中只有1位为1，其他位全是0，则返回第几位，反之返回－1。
但是这个算法有什么最好的吗？因为程序中会有无数次的调用，所以想写的精简并高效些。

165 个解决方案

#1

X和X-1同或一下是 0 ，就是，非0就不是。可以吗？

#2

是的话要返回N是2的几次幂。

#3

  //long a=0x40000000L;  
  if(a&&!(a & ~(a^(a-1)))) 
  {  for(int n=0;a;a>>=1,n++);
     cout<<"OK:"<<n<<"\n";
  } else cout<<"Fail!\n";

#4

2的N次只可能是32种可能，因为对于long来说是4个字节（即32位）
这里为扩大范围把long变为unsigned long，因为long是有符号的，最高位为1就是负数。

//伪代码如下
//in：一个整数
//out：如果是2的幂，则返回第几位为1，否则返回-1
int TellBit(long n)
{
    static unsigned long v={2^0, 2^1 2^2 ... 2^31};//静态数组，避免每次调用都分配内存
    int k = binary_search(v, n, 32);//二分查找（伪代码）
    return k;
}

时间复杂度：
在一个32个元素的数组里面进行二分查找的复杂度为log（32）=5 
即5次整数比较即可

#5

3楼的算法思想是什么？没有给说明，可读性不强。
时间复杂度是多少？

#6

如果(x & (x - 1)) == 0，则x是2的N次幂。
至于求第几位想不出好办法，我用枚举，因为int范围内只有31个这样的数。

#include <iostream>
using namespace std;
const int n = 31;
int a[n];
int cal(int x)
{
	if ((x & (x - 1)) == 0)
	{
		for (int i = 0; i < n; i++)
		{
			if (x == a[i])
			{
				return i;
			}
		}
	}
	return -1;
}
int main() 
{
	int i;
	a[0] = 1;
	for (i = 1; i < n; i++)
	{
		a[i] = a[i-1] << 1;
	}
	int x;
	while (cin>>x)
	{
		cout<<cal(x)<<endl;
	}
}

#7

这样的数31个，预先存到数组里，然后采用二分法进行查找，如果找到了，就说明是2的N次方，否则不是。

#8

cuixiping
的思路是对的,二分查找后,按照31个数字,最多查找Log31次,就是4次!
速度极快!

#9

引用 5 楼 tsasdf 的回复:

3楼的算法思想是什么？没有给说明，可读性不强。 
时间复杂度是多少？

保证能用，如果不要求n，只要算if就行了
找到后执行{ }内内容求n，复杂度32/2=16 * (1次移位， 1次加一 )

#10

引用 8 楼 superdullwolf 的回复:

cuixiping 
的思路是对的,二分查找后,按照31个数字,最多查找Log31次,就是4次! 
速度极快!

二分法并不快，原因每次二分的计算量太大。再说如果不是正好=2^n, 则二分搜索失败

#11

引用 6 楼 shyli 的回复:

如果(x & (x - 1)) == 0，则x是2的N次幂。 

零可以先排除掉

#12

int index[37];
for(int i=0,j=1;i<32;i++,j=(j<<1)%37)
  index[j] = i;
...
int query(int x)
{
   if(x ^ (x-1)) return index[x%37];
   else return -1;//failed to be 2^k
}

#13

囧了……if那里判断条件恰好反掉了。。。自己脑补改过来吧

#14

恩,相比二分,还是楼上的散列hash快!up一下!不愧是高手!

其实就是找一个尽量小的,从1-2^32 除以这个数余数都不相同的质数,没想到大于32的第一个质数就可以(不过我也没有用同余验证一下)

#15

p是质数就能保证a^0~a^p-1 mod p都不同，当(a,p)=1的时候

#16

这种问题要高效只有用汇编,一条指令BSF就解决了

#17

请问
int index[37]; 
for(int i=0,j=1;i <32;i++,j=(j < <1)%37) 
  index[j] = i; 

这句是什么意思？谢谢！

另外，我个人想法是否应写成一个通用的格式？不管参数是 int，long，还是更大的数，要是只限定最大32位的话用数组比较法是否也可以呢？
3楼的代码我正在理解中。

#18

总结：
 1楼 TobeTough， 首先提出 x 和 x-1 进行位运算的想法， 虽然同或不对
 3楼 Idealguy，  方法可行，但 if(a&&!(a & ~(a^(a-1)))) 可以简化成 if(a && !(a and (a-1))) 
 7楼 ShyLi，     使用了 if ((x & (x - 1)) == 0)的正确判断方法
12楼 FancyMouse，提出了mod(x,37)的可行的 Hash 方法， 速度具有优势

#19

(a,p)=1是什么意思呢?

p是质数似乎不能保证a^0~a^p-1 mod p都不同

至少对于本题,41,43,47都有同余的时候.

引用 15 楼 FancyMouse 的回复:

p是质数就能保证a^0~a^p-1 mod p都不同，当(a,p)=1的时候

#20

引用 10 楼 idealguy 的回复:

引用 8 楼 superdullwolf 的回复:
cuixiping 
的思路是对的,二分查找后,按照31个数字,最多查找Log31次,就是4次! 
速度极快! 
 

二分法并不快，原因每次二分的计算量太大。再说如果不是正好=2^n, 则二分搜索失败

为什么说计算量太大？我不知道你要算什么？
仅仅是比较两个整数的大小，有什么计算量大的？

二分搜索失败就是你代码的问题了，当二分已经搜到相邻两个数了(总的31个数内)，还没匹配到，就返回false退出。

将31个数字依次存在一个数组中，对数组二分查找。

#21

hash不错。

#22

>至少对于本题,41,43,47都有同余的时候
挑战数学定理的行为一般是算错了

#23

2^21 mod 41 = 2
2 mod 41 =2

不知道原定理是什么,可能还有些其他条件吧!

引用 22 楼 FancyMouse 的回复:

>至少对于本题,41,43,47都有同余的时候 
挑战数学定理的行为一般是算错了

#24

囧……a*n跑遍完系偶记成a^n跑遍完系了……

#25

呵呵,不过37确实是对的,而且64位的话67也是对的(再往后没验证了),挺有意思的一个规律,没准发现了什么新定理呢!

引用 24 楼 FancyMouse 的回复:

囧……a*n跑遍完系偶记成a^n跑遍完系了……

#26

引用 25 楼 litaoye 的回复:

呵呵,不过37确实是对的,而且64位的话67也是对的(再往后没验证了),挺有意思的一个规律,没准发现了什么新定理呢! 

对于大于32的质数p来说，如果2是p生成的乘法群中的原始根，那么就能确保这样的hash（不包含0值）是一一对应的（离散对数定理）~

#27

引用 25 楼 litaoye 的回复:

呵呵,不过37确实是对的,而且64位的话67也是对的(再往后没验证了),挺有意思的一个规律,没准发现了什么新定理呢! 
…… 

这不是什么新定理，只要找一个适当的且大于指定的数，让2是它的“原根”即可（数论术语）。
比如，32位系统，可选37；64位系统，可选67；128位系统，可选131...



[img=http://www.emath.ac.cn/image/logo_big.gif]学术性数学网站；知识与趣味相交融；提供原创数学工具软件。[/img]

#28

其实，这类题，若直接写汇编代码，
则可以更简单且更高效。



[img=http://www.emath.ac.cn/image/logo.gif]学术性数学网站；知识与趣味相交融；提供原创数学工具软件。[/img]   [img=http://www.emath.ac.cn/image/logo_bbs.gif]研讨数学的研究、发展及应用等问题，以及计算机在数学研发中的相互关系。[/img]

#29

比较高深,虽说是中文吧,但还没能完全看懂,不过重点词汇记住了"离散对数定理"，

下回再有类似的题，别人问我为什么的时候，我就说你连离散对数定理都不知道呀！

引用 26 楼 dlyme 的回复:

引用 25 楼 litaoye 的回复:
呵呵,不过37确实是对的,而且64位的话67也是对的(再往后没验证了),挺有意思的一个规律,没准发现了什么新定理呢! 
 
对于大于32的质数p来说，如果2是p生成的乘法群中的原始根，那么就能确保这样的hash（不包含0值）是一一对应的（离散对数定理）~ 

#30

原根是建立在欧拉定理（ ）之上的，其中 為歐拉函數，其值为与m互质的个数。如果能使该值等于Ordm(a)为使 成立的最小的正整数d相等，则称其为原根。
如果a为原根，则有性质 构成模 m 的简化剩余系

#31

原根偶不熟。不过原根目前只能暴力求吧……这里有个2位底差不多就是直接验证下。
换成这里的实际问题的话估计也只能是给定位数n求找到下一个2是mod m原根的m的期望复杂度之类问题……不过这个问题有点无聊。。。

#32

顺着贴子往下看，头越来越大。呵呵。高手们好多啊。

#33

1。用(x&(x-1))判断的话，x=0和1,都要排除
2。用%37的计算速度不一定比两分法的计算快，印象中整数求余是很慢的操作
3。我的代码，x是2的n次方时循环3-5次，不是时循环6次，每循环四次加减法，
所以应该改进成先按位运算判断，懒得改了

static unsigned long data[32]={2,2<<1,2<<2,2<<3,2<<4,2<<5,2<<6,2<<7,2<<8,2<<9,2<<10,
	2<<11,2<<12,2<<13,2<<14,2<<15,2<<16,2<<17,2<<18,2<<19,2<<20,
	2<<21,2<<22,2<<23,2<<24,2<<25,2<<26,2<<27,2<<28,2<<29,2<<30};

int GetN(unsigned long x)
{
	int nMin=0,nMax=30;
	int i=0;
	while (true)
	{
		i++;
		int nIndex=(nMin+nMax)/2;
		if (x==data[nIndex])
			return nIndex;

		if (x>data[nIndex])	
			if (nMin==nIndex)
				break;
			else
				nMin=nIndex;		
		else
			if(nMax==nIndex)
				break;
			else
				nMax=nIndex;
	}
	return -1;	
}

#34

hash的那个是什么原理？看不懂。。。

#35

回20楼， 
二分法对32位长整形，如只判断大小，则肯定要操作5次（每次含除法，赋值，间接寻址和1次比较），
如要中途满足条件退出，则平均要错做2.5次（每次含除法，赋值，间接寻址和2次比较（=，< 或 >））

直接移位比较法，平均16次操作（每次含 1次比较，移位，N++），感觉要差不多。但程序简单

至于那个运算错误问题，囧，是我没有看到前面那个2^n筛选, 以为直接做二分法了。

#36

引用 12 楼 FancyMouse 的回复:

int index[37];
for(int i=0,j=1;i <32;i++,j=(j < <1)%37)
index[j] = i;
...
int query(int x)
{
if(x ^ (x-1)) return index[x%37];
else return -1;//failed to be 2^k
}

妙啊妙啊～

#37

引用 35 楼 idealguy 的回复:

回20楼， 
二分法对32位长整形，如只判断大小，则肯定要操作5次（每次含除法，赋值，间接寻址和1次比较）， 
如要中途满足条件退出，则平均要错做2.5次（每次含除法，赋值，间接寻址和2次比较（=， < 或 >）） 

直接移位比较法，平均16次操作（每次含 1次比较，移位，N++），感觉要差不多。但程序简单 

至于那个运算错误问题，囧，是我没有看到前面那个2^n筛选, 以为直接做二分法了。

下面是两分法代码，平均计算次数是3+4循环*5计算 =23次，只有加减法和位移，
如果用直接比较的话，需要16循环*3计算=48次,差一倍呢

static unsigned long data[32]={2,2<<1,2<<2,2<<3,2<<4,2<<5,2<<6,2<<7,2<<8,2<<9,2<<10,
	2<<11,2<<12,2<<13,2<<14,2<<15,2<<16,2<<17,2<<18,2<<19,2<<20,
	2<<21,2<<22,2<<23,2<<24,2<<25,2<<26,2<<27,2<<28,2<<29,2<<30};

int GetN(unsigned long x)
{
	int nMin=0,nMax=30,nIndex，nData;

	if(x<2 || (x&(x-1))!=0)
		return -1;

	while (true)
	{	
		nIndex=(nMin+nMax)>>1;
		nData=data[nIndex];
		if (x==nData)
			break;

		if (x>nData)	
			nMin=nIndex;		
		else		
			nMax=nIndex;
	}
	return nIndex;
}

#38

贴一个我的算法,效率估计不高,高手分析下
struct type
{
unsigned long bit1:1;
unsigned long bit2:1;
unsigned long bit3:1;
unsigned long bit4:1;
unsigned long bit5:1;
unsigned long bit6:1;
unsigned long bit7:1;
unsigned long bit8:1;
unsigned long bit9:1;
unsigned long bit10:1;
unsigned long bit11:1;
unsigned long bit12:1;
unsigned long bit13:1;
unsigned long bit14:1;
unsigned long bit15:1;
unsigned long bit16:1;
unsigned long bit17:1;
unsigned long bit18:1;
unsigned long bit19:1;
unsigned long bit20:1;
unsigned long bit21:1;
unsigned long bit22:1;
unsigned long bit23:1;
unsigned long bit24:1;
unsigned long bit25:1;
unsigned long bit26:1;
unsigned long bit27:1;
unsigned long bit28:1;
unsigned long bit29:1;
unsigned long bit30:1;
unsigned long bit31:1;
unsigned long bit32:1;
};

int fun(unsigned long val)
{
struct type  *p;

if(0 == val)
return -1;
else if(1 == val)
return 0;

if(val & (val-1))
return -1;

p = (struct type  *)&(--val);

return p->bit1 + p->bit2 + p->bit3 + p->bit4 + p->bit5 + p->bit6 
              +p->bit7 + p->bit8 + p->bit9 + p->bit10+p->bit11 + p->bit12 
              +p->bit13 + p->bit14 + p->bit15 + p->bit16 + p->bit17 + p->bit18 
              + p->bit19 + p->bit20 +p->bit21 + p->bit22 + p->bit23 + p->bit24 
              + p->bit25 + p->bit26 + p->bit27 + p->bit28 + p->bit29 + p->bit30
              +p->bit31 + p->bit32;
}

#39

    if (N & (N-1))
    {
      int i = 0;
      int j = 1;
      while (j != N)
      {
        i ++;
        j <<= 1;
      } 
      return i;
    }
    else
      return (-1);

#40

上面错了
如果是一次用
 if (N & (N-1) == 0) 
    { 
      int i = 0; 
      int j = 1; 
      while (j != N) 
      { 
        i ++; 
        j < <= 1; 
      } 
      return i; 
    } 
    else 
      return (-1);
如果是X86机器， BSF指令
如果多次用
  Hash是王道

#41

哦

   不对
   hash涉及到了除法指令
   所以并不是总比循环快！！！！！！

#42

>除法指令并不是总比循环快！
哈哈哈哈

#43

说用一次除法比循环二分慢的同学，我觉得应该去重温下计算机组成课程，以及处理器的CPU时间表。

#44

高手年年有，牛年格外多

#45

给分吧，直接给4楼，其他人不用给。

#46

给分吧，直接给1楼，其他人不用给。

#47

搞错，1楼不行，还是二分查找吧

#48

不用数组二分法.

直接硬编码二分最快.

if (x > 0x8000)
{
if (x > 0xC000)
{
...
}
else if (x < 0xC000)
{
...
}
return true;
}
else if(x<0x8000)
{
...
}
return true;

#49

一直除二回去?

#50

我的想法是这样的：

1、虽然最基本的元件是Bit，但实际存储器是以Byte为基本单位的。

2、Long类型是四个Byte。分别是B3 B2 B1 B0。他们的值分别是Bxv。

3、判断Bx占用几个Bit可以用查表法。Bxt=Bt(Bxv)来快速判断。Bxv为0到255之间的一个数字，Bt是一个有255个元素的表，返回一个8位二进制数占用了多少Bit。

4、Long占用的bit数位=B3v+B2v+B1v+B0v=Bt(B3v)+Bt(B2v)+Bt(B1v)+Bt(B0v)。

具体做法是：

1、建立一个表bt()，它存储了从0到255对应值占用的Bit数。

2、将long转为4个byte。

3、累加Bt(B3v)+Bt(B2v)+Bt(B1v)+Bt(B0v)。