Power of K问题

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

要求判断一个整数是否是2的幂次方，最简单的办法就是不断除以2，判断最后出现的数字是不是1。

但是这样过程过于复杂，而且没有用到位操作的知识。所以我们写出几个2的幂次方数进行观察。

1   1
2   10
4   100
8   1000
16  10000
32  100000

由位操作的知识我们可以得到一个结论，如果一个数是2的幂次方，那么其二进制表示中只有首位存在一个1，其余均为0.

所以如果我们让n&(n-1)并且得到的值为0，我们就可以确认只有首位为1，其余均为0.那么这道题就找到了解决方案，代码如下:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&!(n&(n-1));
    }
};

326. Power of Three

Given an integer, write a function to determine if it is a power of three.

这道题有些变化，要求判断一个整数是否是3的幂次方。

3的幂次方似乎没有什么特殊的性质（反正我没看出来），所以我们就要利用一下数学知识了，即:如果一个数是3的整数幂次方，那么其以3为底的对数必然是一个整数。

所以这个问题转化为判断一个运算结果是否是整数，在C++中，判断整数的方法是:num-(int)num==0

但是这里需要注意一点，C++中的内建函数log，其底数是e，也就是自然对数。所以我们需要利用一下换底公式，但如果直接利用换底公式又会遇到另一个问题。

当n=243时:

log(243) = 5.493061443340548    log(3) = 1.0986122886681098
   ==> log(243)/log(3) = 4.999999999999999

这是一个很尴尬的问题，243应该是3的5次幂，但在这里我们对3取对数后却没有得到5，而是一个十分接近5的浮点数。这是什么原因呢？

这是因为在计算机中，log(3)的计算值实际上比真值要略大一些，就导致了这个比值变小了。

要消除这个误差，我们需要用常用对数(內建)来计算以3为底的对数。代码如下:

class Solution {
public:
    bool isPowerOfThree(int n) {
        double res=log10(n)/log10(3);
        return (res-(int)(res))==0? true:false;
    }
}; 

当然这道题也有一个投机取巧的算法，不推荐:

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && (1162261467 % n == 0);
    }
}; 

因为1162261467是32位int的范围中最大的3的幂次方数。

(然而你都知道3的幂次方有哪些数了你还算啥呀？！)

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example: Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

这次要求判断4的幂次方，我们很容易想到，一个数如果是4的幂次方，那么它一定也是2的幂次方，反之则不然。

所以我们可以先找出全部2的幂次方，再观察4的幂次方有哪些特殊的性质。

1   0000 0001
4   0000 0100
16  0001 0000

2   0000 0010
8   0000 1000

通过观察，我们发现2的幂次方和4的幂次方都是只有一个1，但是如果是4的幂次方那么1一定出现在奇数位上，所以我们需要取出其奇数位上的1(如果有的话)。

所以我们构造一个只有奇数位上有1，其余位上都为0的数字，我们想到了0x5==（0101）B，那么考虑int类型，我们采用0x 5555 5555==‭01010101010101010101010101010101‬来取出需要的位。

代码如下:

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num>0&&!(num&(num-1))&&(num&(0x55555555));
    }
};

另外，4的幂次方还有一个性质，即减1以后可以被3整除，利用此法也可以进行判断，不再赘述。

这些题给我们一个警示，计算机在进行一些精密的计算时有时候会有一些我们意想不到的误差。

我们对计算机的理解还远远不够，所以，每时每刻都要Stay hungry，Stay Foolish.