一道关于求2的幂次方的面试题，感兴趣的朋友可以进来坐坐

Question

     上次去面试，面试官（应该是个技术主管之类的）给我出了道关于求出2的幂次方的算法，当然是最快的算法，我的思想是：先把需要求的数转为二进制，然后看第一位是否是1，其他位是否是0就可以判断出来了。
   可惜的是我这个答案还并非是最快的，想看看高手们是如何想的。。最好有代码！

Answer 1

   Math.Pow();
调用一下最快了

Answer 2

总之就是调用Math里面的东西啦。也不用跟他废话

Answer 3

用循环来做不是一样的，或者就直接调用方法Math.Pow(2,n)

Answer 4

2的幂的判断，直接比亚，
定义dictionary
【2，4，8，16，32，64，128.】
把已知数向这里查。

Answer 5

可能上面的题目没有说明白，呵呵。。不好意思了各位！
具体点是这样的：先判断这个数是不是2的幂，如果是输出是2的几次幂？
用math里面的函数那还叫算法吗？其实他是让我用c写，可惜c我不怎么样我就用c#写了
我就是直接把数转换成二进制，判断第一个是不是1其他的是不是0就就可以知道这个数是不是2的幂，然后看转换之后的二进制是几位，就可以知道是2的多少次幂，但他说这不是最快最好的算法，让我再想想，可惜小弟太笨了想不出其他更好的的算法了

Answer 6

&1加右移位，直到为0，如果出现两次真，则返回-1(否)，否则返回以为次数。

Answer 7

       bool i(int l)
        {
            
             bool encountered = false;            while (l != 0)
            {
                if ((l &1) == 1)
                {
                    if (encountered)
                        return false;
                    else
                    {
                        encountered = true;
                    }
                }
                    l >>= 1;            }
            return encountered;
        }

Answer 8

private bool next(double x)
        { 
            double value = x / 2;            cnt++;            if (value == 1)
            {
                return true;
            }
            else if (value < 1)
            {
                return false;
            }            return next(value);        }

Answer 9

cnt就是幂数  是全局的

Answer 10

当递归次数特别大时容易出现无限递归异常  用栈可以解决这个问题Stack stack = new Stack();            // 入栈 n为任意输入数
            stack.Push(n);            while (stack.Count != 0)
            {
                // 顶部弹出
                double y = (double)stack.Pop();                double value = y / 2;                if (value < 1)
                { 
                    // 不是2的n次幂数
                    break;
                }
                else if (value > 1)
                {
                    // 继续循环
                    // 入栈
                    stack.Push(y);
                    stack.Push(value);
                }
                else
                {
                    // 是2的n次幂数
                    // 栈中元素数+最后出栈元素为幂次
                    cnt = stack.Count + 1;                    break;
                }
            }

Answer 11

jmghoul   兄台你这做出来的貌似是2的倍数啊，不是2的幂次方啊

Answer 12

负指数就把 x / 2  改成 x * 2   条件改成 > 1 和  == 1

Answer 13

负的关键是问题的输入不好表示。如果能给出输入，将l>>=1改为 l<<=1就行。

Answer 14

jmghoul  兄台，不好意思开始没注意看，呵呵。。很强大，可是按你说的负次幂貌似还有点问题，还请兄台再指教下！不胜感激。

Answer 15

jmghoul 兄台，搞定了。呵呵你的很强大也很便捷，不知道还有没有哪位高手有更效率的算法

Answer 16

判断n是否2的正整数次幂，只要判断(n-1)==(~n)是否成立。~n表示将n按位取反

Answer 17

自己想了个较快的计算n是2的多少次方的算法：
int f(int n)
{
    int m = ~n;
    int ret = 0;
    static int aiOneCount[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    if (m != n - 1)
    {
        return -1; // 表示n不是2的正整数次幂
    }
    for (;m;m>>=4)
    {
        ret += aiOneCount[m & 0x0f];
    }
    return ret;
}