描述 Description
Given an integer, write a function to determine if it is a power of two.
Example
For n=4, return true;
For n=5, return false;
Challenge
O(1) time
分析 Analysis
方法1（推荐）
最快速的方法 Time complexity = O(1)
(number & number - 1) == 0
将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0； 因此问题可以转化为判断1后面是否跟了n个0就可以了。
如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现为零。
原因：因为2的N次方换算是二进制为10……0这样的形式\(0除外\)。与上自己-1的位数，这们得到结果为0。例如。8的二进制为1000；8-1=7，7的二进制为111。两者相与的结果为0。计算如下：
1000
& 0111
-------
0000
方法2
同样快速但不是最好的方法 Time complexity = O(1)
2^k次方一定能被最大的2^32整除。毕竟除法最慢了。
Because the range of an integer = -2147483648 (-2^31) ~ 2147483647 (2^31-1), the max possible power of two = 2^30 = 1073741824.
(1) If n is the power of two, let n = 2^k, where k is an integer. We have 2^30 = (2^k) * 2^(30-k), which means (2^30 % 2^k) == 0.
(2) If n is not the power of two, let n = j*(2^k), where k is an integer and j is an odd number. We have (2^30 % j*(2^k)) == (2^(30-k) % j) != 0.
return n>0 && (1073741824 % n == 0);
方法3
使用bitcount计算有多少个1，只有一个1说明是2的幂次方。即一位一位地数。
Note: 一位一位地数就可以知道具体是多少次方了。
如果是2的幂，则二进制的所有位中，有且仅有一个1。
通用方法
方法1：最直接的方法就是不停地除以M，看最后的余数是否为1；O(logMn)?
while(n%M==0) n /= M;
方法2：M^k次方一定能被最大的M^maxk (<2^32)整除。O(1)。
maxPowerOfM = int(pow(m, (int)(log(0x7fffffff) / log(m)))) [数学计算相关算法 ]
maxPowerOfM% n == 0
方法3：利用对数换底公式logMn = logcn / logcM来做，那么如果n是M的幂数，则logMn一定是整数。O(1)的，但是一般比最优的方法慢一点。
Note:
1 如果logcM不精确的话，可能结果就不是整数了。所以c一般选择10，不能随便选！！！
2 n超出2**32也会出错。
3 lz有个问题没时间弄明白，log10及log2在计算机中是如何计算出来的，为什么log10能AC不会出错而log2会因为精度出错呢？？？
那么如果n是3的幂数，则log3n一定是整数，我们利用换底公式可以写为log3n = log10n / log103，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log10n / log103是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断。
当然python中可以直接指定底数为M来计算（但是应该也是通过换底公式做的），__import__('math').log(num, M)，所以要使用__import__('math').log10(num)/...。
方法4：M很大的话可以枚举 O(logMmaxnum)
for such kind of power questions, if we need to check many times, it might be a good idea to store the desired powers into an array first.
如3的幂次方
public boolean isPowerOfThree(int n) {
int[] allPowerOfThree = new int[]{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467};
return Arrays.binarySearch(allPowerOfThree, n) >= 0;
}
方法5：转换到M进制，看是否只有一个1
The idea is to convert the original number into radix-3 format and check if it is of format 10* where 0* means k zeros with k>=0.
如转换成3进制判断。
public boolean isPowerOfThree(int n) {
return Integer.toString(n, 3).matches("10*");
}
Note: 不过转换成M进制的过程很可能是辗转相除法得到的，类似方法1，所以lz觉得应该是O(n)的。
代码 Code
方法3
//时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n < 0) return false;
bool hasOne = false;
while (n > 0) {
if (n & 1) {
if (hasOne) {
return false;
}
else {
hasOne = true;
}
}
n >>= 1;
}
return hasOne;
}
};
方法1
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && !(n&(n-1));
}
};