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

 偶尔看到一张老帖，是关于如何快速判断一个正整数是2的N次幂，

链接如下：
http://topic.csdn.net/u/20090118/14/4683a837-9426-40b7-a524-03e6df56abad.html

原文如下：
long N ＝ .........;

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

回帖里高效的方法是二分法，而且需要查表，效率还不够好

我想了个方法，大家看看（就假定是32的），

unsigned int x；

if (x && !(x & （x - 1))）
{
  //取第几位
  x--;
  //数1的个数，即第几位
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
  x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
  x = (x & 0x000000ff) + ((x >> 16) & 0x00000ff);
  return (int)x;
}
else
{
  return -1;
}

13 个解决方案

#1

n & (n - 1) == 0
就可以了

#2

1楼的，题目不只是要判断幂，而且要求出第几位。。。

#3

而且对于n=0的时候你的表达式也不成立

#4

该回复于2010-12-30 09:12:42被版主删除

#5

该回复于2010-12-30 09:09:59被版主删除

#6

俺发现俺居然回过那个帖- -b

#7

不懂。

#8

原来我也回过那个帖子呀！......

不好意思，没有仔细看LZ的程序，思路还是不错的，-1后数1的个数。
虽然原帖里面有不少汇编的实现，但个人感觉那是同算法无关的。
只说算法的话，应该还是6楼FM同志当年给出的那个%37比较有意思！

转一个bsr求log2的，虽然未必最快，但比较简洁。

inline int _log2(unsigned int r)
{
        __asm
        {
                bsr eax,r
        }
}

引用 6 楼 fancymouse 的回复:

俺发现俺居然回过那个帖- -b

#9

            int i = 128;//要判断的数字
            string str = Convert.ToString(i, 2);
            if (str != "0" && str[str.Length - 1] != '1')
            {
                Console.WriteLine("是2的n次幂");
            }

#10

这个问题没什么可纠缠的吧，最笨的方法，计算机也能很快完成啊，计算机表示一个数位数应该不会达到N吧
那得多大的数

#11

此乃神作，，一条汇编指令解决，这还不快的话，，，那就无语了，不考虑C#的效率

引用 8 楼 litaoye 的回复:

原来我也回过那个帖子呀！......

不好意思，没有仔细看LZ的程序，思路还是不错的，-1后数1的个数。
虽然原帖里面有不少汇编的实现，但个人感觉那是同算法无关的。
只说算法的话，应该还是6楼FM同志当年给出的那个%37比较有意思！

转一个bsr求log2的，虽然未必最快，但比较简洁。
C# code

inline int _log2(unsigned int r)
{
 ……

#12

还是很有用的，原作者说了大量频繁调用，还是很考虑效率的

引用 10 楼 luxihua 的回复:

这个问题没什么可纠缠的吧，最笨的方法，计算机也能很快完成啊，计算机表示一个数位数应该不会达到N吧
那得多大的数

#13

大量频繁调用,在计算机可以表达的数字范围内，2的n次方就那么有限的几十个，做个字典（哈希），可以在O(1)时间内判断出来。
2的n次方还有个特点就是2进制里高位是1低位都是0
利用位运算，也是秒杀的